题目：树状数组1 : 单点修改，区间查询

题目描述

给定长度为 $n$ 的数列 $a_1, a_2, \dots, a_n$，需处理 $q$ 个操作，操作分为两类：

1. 修改操作：1 i x → 将第 $i$ 个元素 $a_i$ 加上 $x$；
2. 查询操作：2 l r → 求区间和 $\sum_{k=l}^r a_k$（即 $a_l + a_{l+1} + \dots + a_r$）。

输入格式

• 第一行：两个整数 $n, q$（$1 < n, q \leq 10^6$），表示数列长度和操作数；
• 第二行：$n$ 个整数 $a_1, a_2, \dots, a_n$（初始数列，$|a_i| \leq 10^6$）；
• 接下来 $q$ 行：每行一个操作，格式为 1 i x 或 2 l r（保证 $1 \leq l \leq r \leq n$，$|x| \leq 10^6$）。

输出格式

对于每个 查询操作（类型2），输出一行，为对应区间的和。

样例

输入：

3 2  
1 2 3  
1 2 0  
2 1 3  

输出：

6  

解释：

• 初始数列：[1, 2, 3]；
• 操作 1 2 0：$a_2$ 加 0（无变化）；
• 操作 2 1 3：求和 $1+2+3=6$。

数据范围与挑战

• 数据规模：$n, q \leq 10^6$，要求 高效算法（需 $O(n \log n)$ 时间复杂度）。
• 核心考点：树状数组（Fenwick Tree） 的应用（支持单点修改和区间查询）。