P3374【模板】树状数组

树状数组其实就是快速计算区间值（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;
   }
}