题目：线段树模板题。
代码：
#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
struct node{
int right,left;
int sum;
}tree[210000];
int a[51000];
void build(int root,int start,int end){
tree[root].left=start;
tree[root].right=end;
if(start==end){
tree[root].sum=a[start];
return ;
}
int m=(tree[root].left+tree[root].right)/2;
build(root*2,start,m);
build(root*2+1,m+1,end);
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}
void update_sub(int root,int pos,int val){
if(tree[root].left==tree[root].right&&tree[root].left==pos){
tree[root].sum-=val;
return ;
}
int m=(tree[root].left+tree[root].right)/2;
if(pos<=m) update_sub(root*2,pos,val);
else update_sub(root*2+1,pos,val);
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}
void update_add(int root,int pos,int val){
if(tree[root].left==tree[root].right&&tree[root].left==pos){
tree[root].sum+=val;
return ;
}
int m=(tree[root].left+tree[root].right)/2;
if(pos<=m) update_add(root*2,pos,val);
else update_add(root*2+1,pos,val);
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}
int question(int root,int start,int end){
if(tree[root].left==start&&tree[root].right==end) return tree[root].sum;
int m=(tree[root].left+tree[root].right)/2;
if(end<=m) return question(root*2,start,end);
else if(start>=m+1) return question(root*2+1,start,end);
else return question(root*2,start,m)+question(root*2+1,m+1,end);
}
int main(){
int t,tot=1;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
printf("Case %d:\n",tot);
string s;
while(cin>>s){
if(s=="End") break;
int i,j;
scanf("%d%d",&i,&j);
if(s=="Query") printf("%d\n",question(1,i,j));
else if(s=="Sub") update_sub(1,i,j);
else update_add(1,i,j);
}
tot++;
}
return 0;
}
原文：http://www.cnblogs.com/LMissher/p/7404015.html