树状数组其实就是快速计算区间值（log级别）的方法
例如：
arr[1] = arr[1]
arr[2] = arr[1] + arr[2]
arr[3] = arr[3]
arr[4] = arr[1] + arr[2] + arr[3] + arr[4]
arr[5] = arr[5]
arr[6] = arr[5] + arr[6]
arr[7] = arr[7]
arr[8] = arr[1] + arr[2] + arr[3] + arr[4] + arr[5] + arr[6] + arr[7] + arr[8]
形如一个满二叉树，只要画出来就能理解加法规则, 在这种情况下，需要求区间和arr[1]~arr[7] 只需要计算：arr[4] + arr[6] + arr[7]就行了。
代码中的预备知识由wiki提供的树状数组的基础。
#include <iostream>
using namespace std;
#define LSB(_a) ((_a) & -(_a))
#define SIZE 100005
int n, m;
int A[SIZE];
int lowbit(int k) {
return k & -k;
}
int sum(int i) {
int sum = 0;
while (i > 0)
sum += A[i], i -= LSB(i);
return sum;
}
void add(int i, int k) {
while (i <= n)
A[i] += k, i += LSB(i);
}
int main() {
int value;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> value;
add(i, value);
}
while (m > 0) {
int x, y, z;
cin >> x >> y >> z;
if (x == 1) {
add(y, z);
}
if (x == 2) {
cout << sum(z) - sum(y - 1) << endl;
}
m -= 1;
}
}
