题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166
线段树裸题，注意数组大小为nlogn
贴代码
#include<cstdio> #include<cstring> using namespace std; const int N=50005; int a[N];//addflag[N], int addflag[N*20],tree[N*20],left[20*N],right[20*N]; int n,Q; void build(int root,int L,int R){ addflag[root]=0; left[root]=L;right[root]=R; if (L==R) tree[root]=a[L]; else{ int mid=(L+R)/2; build(root*2,L,mid); build(root*2+1,mid+1,R); tree[root]=tree[root*2]+tree[root*2+1]; } } void pushdown(int root){ if (addflag[root]!=0){ addflag[root*2]+=addflag[root]; addflag[root*2+1]+=addflag[root]; tree[root*2]+=addflag[root]; tree[root*2+1]+=addflag[root]; addflag[root]=0; } } int query(int root,int l,int r){ int L,R; L=left[root]; R=right[root]; if ((r<L)||(l>R))return 0; if ((l<=L)&&(R<=r))return tree[root]; pushdown(root); int mid=(L+R)/2; int x=query(root*2,l,r)+query(root*2+1,l,r); return x; } void add(int root,int x,int delta){ int L,R; L=left[root]; R=right[root]; if ((x<L)||(x>R))return; if ((x<=L)&&(R<=x)){ addflag[root]+=delta; tree[root]+=delta; return; } pushdown(root); int mid=(L+R)/2; add(root*2,x,delta); add(root*2+1,x,delta); tree[root]=tree[root*2]+tree[root*2+1]; } int main(){ // freopen("1166.in","r",stdin); // freopen("1166.out","w",stdout); memset(tree,0,sizeof(tree)); memset(addflag,0,sizeof(addflag)); scanf("%d\n",&Q); for (int t=1;t<=Q;t++){ scanf("%d",&n); for (int i=1;i<=n;i++)scanf("%d",&a[i]); scanf("\n"); build(1,1,n); printf("Case %d:\n",t); while (true){ char ch,ch1,ch2,ch3,ch4; int x,y; scanf("%c",&ch); if (ch=='A'){ scanf("%c%c",&ch1,&ch2); scanf("%d%d\n",&x,&y); add(1,x,y); }else if (ch=='S'){ scanf("%c%c",&ch1,&ch2); scanf("%d%d\n",&x,&y); add(1,x,-y); }else if (ch=='Q'){ scanf("%c%c%c%c",&ch1,&ch2,&ch3,&ch4); scanf("%d%d\n",&x,&y); printf("%d\n",query(1,x,y)); }else if (ch=='E'){ scanf("%c%c\n",&ch1,&ch2); break; } } } return 0; } 【写的有漏洞的，欢迎路过大神吐槽】2017/07/10 21:20:24
Ending.
