树状数组单点更新和区间查询

浏览数：19 / 时间：2015年06月08日

这里是最基本的操作。

单操作时间复杂度O(logN),空间复杂度O(N).

 1 #include <fstream>
 2 #include <iostream>
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 
 7 int n,m;
 8 int a[100002],tree[100002];
 9 
10 void build();//建树状数组
11 int read(int pos);//求 sum[1,pos]的答案
12 void update(int pos,int val);//把a[pos]加上v
13 
14 int main()
15 {
16     //freopen("D:\\input.in","r",stdin);
17     //freopen("D:\\output.out","w",stdout);
18     int bo,t1,t2;
19     scanf("%d %d",&n,&m);
20     for(int i=1;i<=n;i++)
21         scanf("%d",&a[i]);
22     build();
23     for(int i=1;i<=m;i++)
24     {
25         scanf("%d%d%d",&bo,&t1,&t2);
26         if(bo)
27             update(t1,t2);
28         else
29             printf("%d\n",read(t2)-read(t1-1));
30     }
31     return 0;
32 }
33 void build()
34 {
35     tree[0]=0;
36     for(int i=1;i<=n;i++)
37     {
38         tree[i]=a[i];
39         for(int j=i-1;j>i-(i&(-i));j=j-(j&(-j)))
40         {
41             tree[i]+=tree[j];
42         }
43     }
44 }
45 int read(int pos)
46 {
47     int ans=0;
48     while(pos>0)
49     {
50         ans+=tree[pos];
51         pos-=pos&(-pos);
52     }
53     return ans;
54 }
55 void update(int pos,int val)
56 {
57     while(pos<=n)
58     {
59         tree[pos]+=val;
60         pos+=pos&(-pos);
61     }
62 }