树状数组模板

一维树状数组：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n,m;
 7 int a[500005];
 8 
 9 int lowbit(int x)
10 {
11     return x&(-x);
12 }
13 
14 void update(int x,int k)
15 {
16     while(x<=n)
17     {
18         a[x]+=k;
19         x+=lowbit(x);
20     }
21 }
22 
23 int sum(int x)
24 {
25     int ans=0;
26     while(x)
27     {
28         ans+=a[x];
29         x-=lowbit(x);
30     }
31     return ans;
32 }
33 
34 int main()
35 {
36     scanf("%d%d",&n,&m);
37     for(int i=1;i<=n;i++)
38     {
39         int x;
40         scanf("%d",&x);
41         update(i,x);
42     }
43     for(int i=1;i<=m;i++)
44     {
45         int z,x,y;
46         scanf("%d%d%d",&z,&x,&y);
47         if(z==1) update(x,y);
48         else printf("%d
",sum(y)-sum(x-1));
49     }
50     return 0;
51 }

树状数组拓展：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n,m;
 7 int a[500005];
 8 
 9 int lowbit(int x)
10 {
11     return x&(-x);
12 }
13 
14 void update(int x,int k)
15 {
16     while(x<=n)
17     {
18         a[x]+=k;
19         x+=lowbit(x);
20     }
21 }
22 
23 int sum(int x)
24 {
25     int ans=0;
26     while(x)
27     {
28         ans+=a[x];
29         x-=lowbit(x);
30     }
31     return ans;
32 }
33 
34 int main()
35 {
36     scanf("%d%d",&n,&m);
37     int last=0,now;
38     for(int i=1;i<=n;i++)
39     {
40         scanf("%d",&now);
41         update(i,now-last);
42         last=now;
43     }
44     for(int i=1;i<=m;i++)
45     {
46         int z,x,y,k;
47         scanf("%d",&z);
48         if(z==1)
49         {
50             scanf("%d%d%d",&x,&y,&k);
51             update(x,k);
52             update(y+1,-k);
53         }
54         else
55         {
56             scanf("%d",&x);
57             printf("%d
",sum(x));
58         }
59     }
60     return 0;
61 }