树状数组

下标记得是从1开始，本节点id通过加lowbit可以访问到父节点的id，用于点修。
本节点id减去lowbit则是查看左边第一个比自己高一级的节点id，比如7会查到6，6会查到4，这样子累加此三个的值就可以得到前七个的前缀和。

int treeArr[M] = {0}; // start from 1
int lowbit(int x) {
    return x & (-x);
}
void change(int i, int x){  // add x on ith arrry
    while (i < M) {
        treeArr[i] += x;
        i += lowbit(i);
    }
}

int query(int i){
    int sum=0;
    while(i >= 1) {
        sum += treeArr[i];
        i -= lowbit(i);
    }
    return sum;
}

例题（from acwing1267）

NK 中学组织同学们去五云山寨参加社会实践活动，按惯例要乘坐火车去。
由于 NK 中学的学生很多，在火车开之前必须清点好人数。
初始时，火车上没有学生，当同学们开始上火车时，年级主任从第一节车厢出发走到最后一节车厢，每节车厢随时都有可能有同学上下。
年级主任走到第 m 节车厢时，他想知道前 m 节车厢上一共有多少学生。
他没有调头往回走的习惯，也就是说每次当他提问时，m 总会比前一次大。

输入格式

第一行两个整数 n,k，表示火车共有 n节车厢以及 k个事件。
接下来有 k行，按时间先后给出 k个事件，每行开头都有一个字母 A，B或 C。
如果字母为 A，接下来是一个数 m，表示年级主任现在在第 m 节车厢；
如果字母为 B，接下来是两个数 m,p，表示在第 m 节车厢有 p 名学生上车；
如果字母为 C，接下来是两个数 m,p，表示在第 m 节车厢有 p 名学生下车。
学生总人数不会超过 10^5。

输出格式

对于每个事件 A，输出一行，一个整数，表示年级主任的问题的答案。

#include<iostream>
using namespace std;
const int M = 500003;
// Binary Indexed Trees
int treeArr[M] = {0}; // start from 1
int lowbit(int x) {
    return x & (-x);
}
void change(int i, int x){  // add x on ith arrry
    while (i < M) {
        treeArr[i] += x;
        i += lowbit(i);
    }
}

int query(int i){
    int sum=0;
    while(i >= 1) {
        sum += treeArr[i];
        i -= lowbit(i);
    }
    return sum;
}

int main(){
    int n,k;
    cin>>n>>k;
    for (int i=0; i<k; i++) {
        char c;
        int a, b;
        cin>>c;
        if (c == 'A') {
            cin>>a;
            cout<<query(a)<<endl;
        } else if (c =='B') {
            cin>>a>>b;
            change(a, b);
        } else {
            cin>>a>>b;
            change(a, -b);
        }
    }
    return 0;
}