【模板】树状数组

 1 #include<cstring>
 2 #define MAX 100000
 3 
 4 //数组c为树状数组，MAX为数状数组大小
 5 int c[MAX];
 6 
 7 //lowbit函数
 8 int lowbit(int x)
 9 {
10     return x&(-x);
11 }
12 
13 //树状数组求和函数，求c[1]+c[2]+…+c[x]
14 //注意如果题目中可能出现x=0的情况，这里会出现死循环而TLE，改进方法是将原数据全部+1
15 int sum(int x)
16 {
17     int ret=0;
18 
19     while(x>0)
20     {
21         ret+=c[x];
22         x-=lowbit(x);
23     }
24 
25     return ret;
26 }
27 
28 //树状数组的更新操作，即在某一个元素上加之后进行的更新操作
29 void add(int x,int t)
30 {
31     while(x<=MAX)
32     {
33         c[x]+=t;
34         x+=lowbit(x);
35     }
36 }
37 
38 int main()
39 {
40     //树状树组的初始化即从1到n执行一遍add操作
41 
42     return 0;
43 }