LG#P3374. 【模板】树状数组 1

【模板】树状数组 1

P3374 【模板】树状数组 1

题目描述

\hspace{15pt}给定一个长度为 nn 的整数数列 a1,a2,…,ana_1, a_2, \dots, a_n,你需要依次处理 mm 次操作。操作共有下面两种:

∙ \hspace{23pt}\bullet\,将数列中的某一个数加上一个给定的整数;

∙ \hspace{23pt}\bullet\,求出数列中某一个区间内所有数的和。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦5×105)n, m \left(1 \leqq n, m \leqq 5 \times 10^5\right) 分别代表数列的长度和操作次数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(-2^{31} \leqq a_i < 2^{31}\right)$ 代表数列的初始值。

\hspace{15pt}此后 mm 行,每行先输入一个整数 op(1≦op≦2)op \left(1 \leqq op \leqq 2\right) 代表操作类型,随后在同一行继续输入:

∙ \hspace{23pt}\bullet\,若 op=1op = 1,输入两个整数 $x, k \left(1 \leqq x \leqq n;\ -2^{31} \leqq k < 2^{31}\right)$,表示将第 xx 个数加上 kk;

∙ \hspace{23pt}\bullet\,若 op=2op = 2,输入两个整数 x,y(1≦x≦y≦n)x, y \left(1 \leqq x \leqq y \leqq n\right),表示询问区间 [x,y]\left[x, y\right] 内所有数的和。

\hspace{15pt}保证在任意时刻,数列中任意子区间(包括长度为 11 和 nn 的子区间)内所有数之和都在 [−231,231)\left[-2^{31}, 2^{31}\right) 范围内。

输出格式

\hspace{15pt}对于每次 op=2op = 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 解释

\hspace{15pt}数列的初始值为 {1,5,4,2,3}\{1, 5, 4, 2, 3\}。

∙ \hspace{23pt}\bullet\,操作 "1 1 3"\texttt{"1 1 3"}:将第 11 个数加上 33,数列变为 {4,5,4,2,3}\{4, 5, 4, 2, 3\};

∙ \hspace{23pt}\bullet\,操作 "2 2 5"\texttt{"2 2 5"}:区间 [2,5]\left[2, 5\right] 内所有数之和为 5+4+2+3=145 + 4 + 2 + 3 = 14;

∙ \hspace{23pt}\bullet\,操作 "1 3 -1"\texttt{"1 3 -1"}:将第 33 个数加上 −1-1,数列变为 {4,5,3,2,3}\{4, 5, 3, 2, 3\};

∙ \hspace{23pt}\bullet\,操作 "1 4 2"\texttt{"1 4 2"}:将第 44 个数加上 22,数列变为 {4,5,3,4,3}\{4, 5, 3, 4, 3\};

∙ \hspace{23pt}\bullet\,操作 "2 1 4"\texttt{"2 1 4"}:区间 [1,4]\left[1, 4\right] 内所有数之和为 4+5+3+4=164 + 5 + 3 + 4 = 16。

\hspace{15pt}因此依次输出 1414 和 1616。

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 解释

\hspace{15pt}数列的初始值为 {2,−1,3,5,0,−4}\{2, -1, 3, 5, 0, -4\}。

∙ \hspace{23pt}\bullet\,操作 "1 2 4"\texttt{"1 2 4"}:将第 22 个数加上 44,数列变为 {2,3,3,5,0,−4}\{2, 3, 3, 5, 0, -4\};

∙ \hspace{23pt}\bullet\,操作 "2 1 3"\texttt{"2 1 3"}:区间 [1,3]\left[1, 3\right] 内所有数之和为 2+3+3=82 + 3 + 3 = 8;

∙ \hspace{23pt}\bullet\,操作 "2 2 6"\texttt{"2 2 6"}:区间 [2,6]\left[2, 6\right] 内所有数之和为 3+3+5+0+(−4)=73 + 3 + 5 + 0 + (-4) = 7;

∙ \hspace{23pt}\bullet\,操作 "1 4 -6"\texttt{"1 4 -6"}:将第 44 个数加上 −6-6,数列变为 {2,3,3,−1,0,−4}\{2, 3, 3, -1, 0, -4\};

∙ \hspace{23pt}\bullet\,操作 "2 3 5"\texttt{"2 3 5"}:区间 [3,5]\left[3, 5\right] 内所有数之和为 3+(−1)+0=23 + (-1) + 0 = 2;

∙ \hspace{23pt}\bullet\,操作 "2 1 6"\texttt{"2 1 6"}:区间 [1,6]\left[1, 6\right] 内所有数之和为 2+3+3+(−1)+0+(−4)=32 + 3 + 3 + (-1) + 0 + (-4) = 3。

\hspace{15pt}因此依次输出 8,7,2,38, 7, 2, 3。

提示

\hspace{15pt}本题的数据分为以下三档:

∙ \hspace{23pt}\bullet\,对于 30%30\% 的数据,1≦n≦81 \leqq n \leqq 8,1≦m≦101 \leqq m \leqq 10;

∙ \hspace{23pt}\bullet\,对于 70%70\% 的数据,1≦n,m≦1041 \leqq n, m \leqq 10^4;

∙ \hspace{23pt}\bullet\,对于 100%100\% 的数据,1≦n,m≦5×1051 \leqq n, m \leqq 5 \times 10^5。