链接：http://codevs.cn/problem/1080/
先用树状数组水一发，再用线段树水一发
树状数组代码：84ms
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #define dinf 0x3f3f3f3f12 typedef long long ll;13 const int Max=(1<<16)+10;14 using namespace std;15 16 #define SIZE 100000517 18 int c[SIZE],a[SIZE];19 20 int Lowbit(int x)21 {22 return x&(-x);23 }24 25 int Sum(int x)26 {27 int sum=0;28 while(x>0)29 {30 sum+=c[x];31 x-=Lowbit(x);32 }33 return sum;34 }35 36 void Update(int i,int x)37 {38 while(i<=SIZE)//要把所有的与i相关的c数组中的值全部更新，不然会出错 39 {40 c[i]+=x;41 i+=Lowbit(i);42 }43 }44 45 46 int main()47 {48 int n,m; 49 while(~scanf("%d",&n))50 {51 memset(a,0,sizeof(a));52 memset(c,0,sizeof(c));53 54 for(int i=1;i<=n;i++)55 {56 scanf("%d",&a[i]);57 Update(i,a[i]);58 }59 scanf("%d",&m);60 int op,node,num;61 for(int i=1;i<=m;i++)62 {63 scanf("%d %d %d",&op,&node,&num);64 if(op==1)65 Update(node,num);66 else if(op==2)67 {68 printf("%d\n",Sum(num)-Sum(node-1));69 }70 }71 } 72 return 0;73 }
线段树代码：48ms
1 #include2 using namespace std; 3 struct RE 4 { 5 int sum,l,r; 6 }tree[400001]; 7 int a[100001]; 8 void build(int node,int l,int r) 9 {10 int mid=(l+r)>>1;11 tree[node].l=l;12 tree[node].r=r;13 if (l==r)14 {15 tree[node].sum=a[l];16 return;17 }18 build(2*node,l,mid);19 build(2*node+1,mid+1,r);20 tree[node].sum+=tree[2*node].sum+tree[2*node+1].sum;21 }22 void updata(int node,int a,int b)23 {24 int mid=(tree[node].l+tree[node].r)>>1;25 if (mid==tree[node].l&&mid==tree[node].r)26 {27 tree[node].sum+=b;28 return;29 }30 if (a<=mid) 31 updata(2*node,a,b);32 else 33 updata(2*node+1,a,b);34 tree[node].sum+=b;35 }36 int query(int node,int l,int r)37 {38 int mid=(tree[node].l+tree[node].r)>>1;39 if (tree[node].l==l&&tree[node].r==r)40 return tree[node].sum;41 if (l>mid) 42 return query(2*node+1,l,r);43 if (r<=mid) 44 return query(2*node,l,r);45 return query(2*node,l,mid)+query(2*node+1,mid+1,r);46 }47 int main()48 {49 int n,m;50 scanf("%d",&n);51 int i,j;52 for (i=1;i<=n;i++)53 scanf("%d",&a[i]);54 build(1,1,n);55 scanf("%d",&m);56 int sign,a,b;57 for (i=1;i<=m;i++)58 {59 scanf("%d%d%d",&sign,&a,&b);60 if (sign==1) updata(1,a,b);61 else printf("%d\n",query(1,a,b));62 }63 return 0;64 }