建树+更新+查找
第一次写线段树的题，改了比较久orz
需要注意的几点：
1.main函数里调用函数时，第一个变量——当前下标从哪里开始。之前一直想着从0开始，忽略了p*2会继续为0这件事。
2.忘记改case：%d对应的变量了……
3.比较两个字符串那里可以改成strcmp(str,"Query")这样orz
贴上代码
#include<stdio.h> #include<stdlib.h> #include<string.h> int a[50005]; int tree[200020]; void build(int p,int l,int n) { if(l==n) { tree[p]=a[l]; return; } int mid=(l+n)/2; build(p*2,l,mid); build(p*2+1,mid+1,n); tree[p]=tree[p*2]+tree[p*2+1]; } void change1(int p,int l,int r,int x,int num) { if(l==r) { tree[p]+=num;return; } int mid=(l+r)/2; if(x<=mid) change1(p*2,l,mid,x,num); else change1(p*2+1,mid+1,r,x,num); tree[p]=tree[p*2]+tree[p*2+1]; } void change2(int p,int l,int r,int x,int num) { if(l==r) { tree[p]-=num;return; } int mid=(l+r)/2; if(x<=mid) change2(p*2,l,mid,x,num); else change2(p*2+1,mid+1,r,x,num); tree[p]=tree[p*2]+tree[p*2+1]; } int find(int p,int l,int r,int x,int y) { if(x<=l&&r<=y) return tree[p]; int mid=(l+r)/2; if(y<=mid) return find(p*2,l,mid,x,y); if(x>mid) return find(p*2+1,mid+1,r,x,y); return (find(p*2,l,mid,x,mid)+find(p*2+1,mid+1,r,mid+1,y)); } int main() { int i,j,t,n; char str1[4]={"Add"},str2[4]={"Sub"},str3[6]={"Query"},str4[4]={"End"}; scanf("%d",&t); for(i=0;i<t;i++){ char str[6];int x,y; scanf("%d",&n); for(j=0;j<n;j++){ scanf("%d",&a[j]); } build(1,0,n-1); printf("Case %d: ",i+1); while(1){ for(j=0;j<6;j++) str[j]=0; scanf("%s",str); if(strcmp(str,str4)==0) break; else{ scanf("%d %d",&x,&y); if(strcmp(str,str1)==0) change1(1,1,n,x,y); else if(strcmp(str,str2)==0) change2(1,1,n,x,y); else if(strcmp(str,str3)==0) printf("%d ",find(1,1,n,x,y)); } } } return 0; }