#MYD6. 单点加与区间和
单点加与区间和
题目描述
维护一个长度为 n 的整数序列 a_1, …, a_n,支持 q 次操作:
1 x v:将 a_x 增加 v;2 l r:查询 Σ_{i=l}^{r} a_i 的值。
输入格式
第一行两个整数 n 和 q。第二行 n 个整数 a_i。接下来 q 行,每行形如 1 x v 或 2 l r。
输出格式
对每个操作 2,输出一行一个整数。
数据范围
1 ≤ n, q ≤ 100000,0 ≤ a_i ≤ 10^9,1 ≤ x ≤ n,1 ≤ v ≤ 10^4,1 ≤ l ≤ r ≤ n。任意时刻序列元素不超过 2×10^9。
样例
5 4
1 2 3 4 5
2 1 5
1 3 10
2 3 3
2 2 5
15
13
24
说明/提示
树状数组或线段树模板题。
解析
思路:树状数组维护前缀和;单点加即差分更新,区间和 = S(r) − S(l−1)。线段树亦可。
复杂度:O((n+q) log n)。
来源
人工命题 · 三方对比实验