[hdu1166]线段树模板

#include <cstdio>#include <string>using namespace std;#define lson rt << 1#define rson rt << 1 | 1const int maxn = 5e4 + 1;int st[200010];//数组开的太小会TLEstring a;void build(int l,int r,int rt){int m = l + r >> 1;if(l == r){scanf("%d",st+rt);return;}build(l, m, lson);build(m+1, r, rson);st[rt] = st[lson] + st[rson];return;}int que(int L, int R, int l, int r,int rt){int m = l + r >> 1;int ans;if(l == r)return st[rt];if(L <= l && R >= r)return st[rt];if(R <= m)return que(L,R,l,m,lson);if(L > m)return que(L,R,m+1,r,rson);else ans = que(L,R,m+1,r,rson) + que(L,R,l,m,lson);return ans;}void update(int p,int temp,int l, int r,int rt){int m = l + r >> 1;if(l == r && l == p){st[rt] += temp;return ;}if(m < p)update(p,temp, m+1, r, rson);else update(p, temp, l, m, lson);st[rt] = st[lson] + st[rson];return;}int main(){int t;int cas = 1;// freopen("test.in","r",stdin);scanf("%d", &t);while(1){bool ok = true;char q[5];int n;scanf("%d", &n);build(1,n,1);while(1){scanf("%s", q);if(q[0] == 'E')break;else if(q[0] == 'Q'){int le,ri,ans;if(ok){PRintf("Case %d:/n",cas);ok = false;}scanf("%d %d", &le, &ri);ans = que(le, ri ,1 ,n ,1);printf("%d/n",ans);}else{int cur,num;scanf("%d %d", &cur, &num);update(cur,q[0] == 'S'?-1*num:num,1,n,1);}}if(cas++ == t)break;}return 0;}
还可以用树状数组写，代码简介了很多
#include <cstdio>#include <cstring>using namespace std;const int maxn = 5e4 + 1;int c[maxn],n;int lowbit(int x){	return x&(-x);}int sum(int x){	int ans = 0;	while(x > 0){		ans += c[x];		x -= lowbit(x);	}	return ans;}int update(int x,int add){	while(x <= n){		c[x] += add;		x += lowbit(x);	}	return 0;}int main(){	int t;	int cas = 1;//	freopen("test.in","r",stdin);	scanf("%d", &t);	while(1){		int a;		bool ok = true;		char q[5];		memset(c, 0, sizeof(c));		scanf("%d", &n);		for(int i = 1; i <= n; i++){			scanf("%d",&a);			update(i,a);		}		while(1){			scanf("%s", q);			if(q[0] == 'E')break;			else if(q[0] == 'Q'){				int le,ri,ans;				if(ok){					printf("Case %d:/n",cas);					ok = false;				}				scanf("%d %d", &le, &ri);				ans = sum(ri) - sum(le-1);				printf("%d/n",ans);			}			else{				int cur,num;				scanf("%d %d", &cur, &num);				update(cur,q[0] == 'S'?-1*num:num);			}		}		if(cas++ == t)break;	}	return 0;}