线段树单点更新模板-杭电1166

#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define LL long long #define left L,m,rt<<1 #define right m+1,R,rt<<1|1 LL num[200010]; void update(int rt) { num[rt]=num[rt<<1]+num[rt<<1|1]; } void build(int L,int R,int rt) { if(L==R) { scanf("%I64d",&num[rt]); return; } int m=(L+R)/2; build(left); build(right); update(rt); } void Add(int a,int b,int L,int R,int rt) { if(L==R) { num[rt]+=b; return; } int m=(L+R)/2; if(a<=m) { Add(a,b,left); } else Add(a,b,right); update(rt); } LL Query(int a,int b,int L,int R,int rt) { if(a<=L&&b>=R) { return num[rt]; } LL num1=0; int m=(L+R)/2; if(a<=m) { num1+=Query(a,b,left); } if(b>m) { num1+=Query(a,b,right); } return num1; } int main() { int T,N,pos1,num1,pos2,Case=0; char op[20]; int i,j; scanf("%d",&T); while(T--) { printf("Case %d:\n",++Case); scanf("%d",&N); build(1,N,1); while(scanf("%s",op)&&op[0]!='E') { if(op[0]=='A') { scanf("%d %d",&pos1,&num1); Add(pos1,num1,1,N,1); } else if(op[0]=='S') { scanf("%d %d",&pos1,&num1); Add(pos1,-num1,1,N,1); } else { scanf("%d %d",&pos1,&pos2); printf("%I64d\n",Query(pos1,pos2,1,N,1)); } } } return 0; }