1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End
Case 1: 6 33 59
思路：基础的线段树模板直接套，作为自己线段树做的第一道题，代码纪念一下
#include <cstdio>
#include <iostream>
#include <cstring>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std ;
const int maxn = 555555 ;
int sum[maxn<<2] ;
void pushUp(int rt)
{
sum[rt] = sum[rt<<1]+sum[rt<<1 | 1] ;
}
void build(int l,int r,int rt) //构建一个线段树
{
if(l == r) //递归到最后一层
{
scanf("%d",&sum[rt]) ;
return ;
}
int m = (l+r)>>1 ;
build(lson) ;
build(rson) ;
pushUp(rt) ;
}
void update(int p,int add,int l,int r,int rt) //更新操作
{
if(l == r)
{
sum[rt]+=add ;
return ;
}
int m = (l+r)>>1 ;
if(p<=m)
{
update(p,add,lson) ;
}
else
{
update(p,add,rson) ;
}
pushUp(rt) ;
}
int query(int L,int R,int l,int r,int rt) //查询操作，L,R代表查询左右区间
{
if(r<=R && L<=l)
{
return sum[rt] ;
}
int m = (l+r)>>1 ;
int ret = 0 ;
if(L <= m)
{
ret+=query(L,R,lson);
}
if(R>m)
{
ret+=query(L,R,rson) ;
}
return ret ;
}
int main()
{
int t,n ;
while(scanf("%d",&t)!=EOF)
{
for(int k = 1 ;k<=t ;k++)
{
scanf("%d",&n) ;
build(1,n,1) ;
char op[10] ;
printf("Case %d:\n",k) ;
while(scanf("%s",op))
{
if(op[0] == 'E')
break ;
int a,b ;
scanf("%d%d",&a,&b) ;
if(op[0] == 'Q')
{
printf("%d\n",query(a,b,1,n,1)) ;
}
else if(op[0] == 'S')
{
update(a,-b,1,n,1) ;
}
else update(a,b,1,n,1) ;
}
}
}
return 0 ;
}
原文：http://blog.csdn.net/u012566693/article/details/46050517