#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)。

来源

人工命题 · 三方对比实验