P3374 【模板】树状数组 1
题目描述
给定一个长度为 n 的整数数列 a1,a2,…,an,你需要依次处理 m 次操作。操作共有下面两种:
∙将数列中的某一个数加上一个给定的整数;
∙求出数列中某一个区间内所有数的和。
输入格式
第一行输入两个整数 n,m(1≦n,m≦5×105) 分别代表数列的长度和操作次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(-2^{31} \leqq a_i < 2^{31}\right)$ 代表数列的初始值。
此后 m 行,每行先输入一个整数 op(1≦op≦2) 代表操作类型,随后在同一行继续输入:
∙若 op=1,输入两个整数 $x, k \left(1 \leqq x \leqq n;\ -2^{31} \leqq k < 2^{31}\right)$,表示将第 x 个数加上 k;
∙若 op=2,输入两个整数 x,y(1≦x≦y≦n),表示询问区间 [x,y] 内所有数的和。
保证在任意时刻,数列中任意子区间(包括长度为 1 和 n 的子区间)内所有数之和都在 [−231,231) 范围内。
输出格式
对于每次 op=2 的操作,新起一行输出一个整数,代表该次询问的答案。
测试样例
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
14
16
样例 1 解释
数列的初始值为 {1,5,4,2,3}。
∙操作 "1 1 3":将第 1 个数加上 3,数列变为 {4,5,4,2,3};
∙操作 "2 2 5":区间 [2,5] 内所有数之和为 5+4+2+3=14;
∙操作 "1 3 -1":将第 3 个数加上 −1,数列变为 {4,5,3,2,3};
∙操作 "1 4 2":将第 4 个数加上 2,数列变为 {4,5,3,4,3};
∙操作 "2 1 4":区间 [1,4] 内所有数之和为 4+5+3+4=16。
因此依次输出 14 和 16。
6 6
2 -1 3 5 0 -4
1 2 4
2 1 3
2 2 6
1 4 -6
2 3 5
2 1 6
8
7
2
3
样例 2 解释
数列的初始值为 {2,−1,3,5,0,−4}。
∙操作 "1 2 4":将第 2 个数加上 4,数列变为 {2,3,3,5,0,−4};
∙操作 "2 1 3":区间 [1,3] 内所有数之和为 2+3+3=8;
∙操作 "2 2 6":区间 [2,6] 内所有数之和为 3+3+5+0+(−4)=7;
∙操作 "1 4 -6":将第 4 个数加上 −6,数列变为 {2,3,3,−1,0,−4};
∙操作 "2 3 5":区间 [3,5] 内所有数之和为 3+(−1)+0=2;
∙操作 "2 1 6":区间 [1,6] 内所有数之和为 2+3+3+(−1)+0+(−4)=3。
因此依次输出 8,7,2,3。
提示
本题的数据分为以下三档:
∙对于 30% 的数据,1≦n≦8,1≦m≦10;
∙对于 70% 的数据,1≦n,m≦104;
∙对于 100% 的数据,1≦n,m≦5×105。