[模板]树状数组

1 int main(){
2     int x;
3     while(1){
4         x = read();
5         printf("%d&%d == %d
",x,-x,x&-x);
6     }
7     
8 return 0;
9 }

x&-x

为什么单点加时要+x&-x?

——因为令y = x+（x&-x）,则x区间的值包含于y点的更大区间中

为什么查询时要-x&-x？

——因为令y = x-（x&-x），则[0,y]+x=[0,x]

代码：

 1 int a[10010];
 2 int n;
 3 
 4 void add(int x,int y){
 5     for(;x <= n;x += x&-x)a[x] += y;
 6 }
 7 
 8 int ask(int x){
 9     int ans = 0;
10     for(;x;x -= x&-x)ans += a[x];
11     return ans;
12 }
13 
14 int main(){
15     n = read();
16     rep(i,1,n)add(i,read());
17     while(1){
18         int l = read(),r = read();
19         printf("%d
",ask(r)-ask(l-1));
20     }
21     
22 return 0;
23 }