【模板】树状数组

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define MAX 100000
 5 
 6 using namespace std;
 7 
 8 //数组c为树状数组，MAX为数状数组大小
 9 int c[MAX];
10 
11 //lowbit函数
12 int lowbit(int x)
13 {
14     return x&(-x);
15 }
16 
17 //树状数组求和函数，求c[1]+c[2]+…+c[x]
18 int sum(int x)
19 {
20     int ret=0;
21 
22     while(x>0)
23     {
24         ret+=c[x];
25         x-=lowbit(x);
26     }
27 
28     return ret;
29 }
30 
31 //树状数组的更新操作，即在某一个元素上加之后进行的更新操作
32 void add(int x,int t)
33 {
34     while(x<=MAX)
35     {
36         c[x]+=t;
37         x+=lowbit(x);
38     }
39 }
40 
41 int main()
42 {
43     //树状树组的初始化即从1到n执行一遍add操作
44 
45     return 0;
46 }