#O1044. 树状数组

树状数组

题目描述

给定长度为 nn 的序列 aa,执行 qq 次操作:

  • 1 x y:令 ax←ax+ya_x \leftarrow a_x + y;
  • 2 l r:求 ∑i=lrai\sum\limits_{i=l}^{r} a_i。

题目类型

树状数组

输入格式

第一行两个整数 n,qn, q。

第二行 nn 个整数,表示初始序列。

接下来 qq 行,每行形如 1 x y 或 2 l r。

输出格式

对每个 2 l r 操作输出一行一个整数。

样例 #1

样例输入 #1

5 3
1 2 3 4 5
2 1 5
1 1 10
2 1 2

样例输出 #1

15
13

数据规模与约定

数据范围 说明
1≤n,q≤2×1051 \le n, q \le 2 \times 10^5 长度与操作数
−106≤ai,y≤106-10^6 \le a_i, y \le 10^6 数值范围
  • 用树状数组维护前缀和,答案用 long long。