NYOJ 116士兵杀敌（二）（树状数组）（插点问线）

 二叉索引数（树状数组）

【任务】
对于数组A[1..n]，在O(logn)的时间内完成以下任务：
（1） Add（x，d）：让A[x]增加 d；
（2） Query（L，R）：计算A[L]+...+A[R]的和；
（这题可作为树状数组的模板）

 1 #include<cstdio>
 2 #define Max 1000005
 3 int C[Max];
 4 int N,M;
 5 int lowbit(int x)
 6 {
 7     return x & -x;
 8 }
 9 int sum(int i)//计算前i项和
10 {
11     int ret = 0;
12     while(i>0)
13     {
14         ret += C[i];
15         i -= lowbit(i);
16     }
17     return ret;
18 }
19 void add(int x,int n)//A[x]元素增加n，即C[x]的前x项和加n
20 {
21     while(x <= N)
22     {
23         C[x] += n;
24         x += lowbit(x);
25     }
26 }
27 
28 int main()
29 {
30 　　 //freopen("in.txt","r",stdin);
31     int i,a,b;
32     char s[9];
33     scanf("%d%d",&N,&M);
34     for(i=1; i<=N; i++)
35     {
36         scanf("%d",&a);
37         add(i,a);
38     }
39     for(i=0; i<M; i++)
40     {
41         scanf("%s%d%d",s,&a,&b);    
42         if(s[0] == 'A')
43             add(a,b);
44         else
45             printf("%d
",sum(b)-sum(a-1));
46     }
47     return 0;
48 }

View Code