数列操作 (树状数组/线段树 模板题)

题目描述

给定一个长度为 $n$ 的整数数列，需要支持以下两种操作共 $m$ 次：

1. 修改操作：将数列中第 $a$ 个元素的值加上 $b$。
2. 查询操作：求子数列 $[a, b]$ 的连续和。

数列的元素个数最多为 $10^5$，操作次数最多为 $10^5$。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示数列的长度和操作的次数。
第二行包含 $n$ 个整数，表示初始的数列。
接下来 $m$ 行，每行包含三个整数 $k, a, b$，含义如下：

• 若 $k = 0$，表示查询子数列 $[a, b]$ 的连续和。
• 若 $k = 1$，表示将第 $a$ 个元素的值加上 $b$。

输出格式

对于每个 $k = 0$ 的查询操作，输出一行一个整数，表示对应的子数列 $[a, b]$ 的连续和。

输入输出样例

样例输入

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

样例输出

11
30
35

样例说明

初始数列：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

1. 1 1 5：第 1 个元素加 5，数列变为 [6, 2, 3, 4, 5, 6, 7, 8, 9, 10]
2. 0 1 3：查询区间 $[1, 3]$ 的和，即 $6 + 2 + 3 = 11$
3. 0 4 8：查询区间 $[4, 8]$ 的和，即 $4 + 5 + 6 + 7 + 8 = 30$
4. 1 7 5：第 7 个元素加 5，数列变为 [6, 2, 3, 4, 5, 6, 12, 8, 9, 10]
5. 0 4 8：查询区间 $[4, 8]$ 的和，即 $4 + 5 + 6 + 12 + 8 = 35$

数据范围与约定

• 对于 $100\%$ 的数据：$1 \le n, m \le 10^5$
• 数列中每个元素的绝对值不超过 $10^4$
• 每次操作加上的数值 $b$ 的绝对值不超过 $10^4$
• 保证查询操作的区间合法，即 $1 \le a \le b \le n$

提示

本题是经典的 单点修改 + 区间查询 问题，可以使用以下数据结构解决：

• 树状数组（Fenwick Tree）：时间复杂度 $O(\log n)$ 每次操作，常数小，代码简洁
• 线段树（Segment Tree）：时间复杂度 $O(\log n)$ 每次操作，功能更强大

注意答案可能超过 32 位整数范围，建议使用 64 位整数 (long long ) 存储。

本题为树状数组/线段树的模板题，适合初学者练习。