树状数组

 1 int lowbit(int x)
 2 {
 3     return x & (-x);
 4 }
 5 
 6 int sum(int x)
 7 {
 8     int ret = 0;
 9     while(x > 0)
10     {
11         ret += tmp[x]; x -= lowbit(x);
12     }
13     return ret; 
14 } 
15 
16 void add(int x, int d)
17 {
18      while(x <= ｎ）
19     {
20          tmp[x] += d; x += lowbit(x);
21     }
22 }
23 void init()
24 {
25    for(int i = 1; i <= n; ++i)
26       add(i,a[i]);
27 }