链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1166
#include "iostream"
#include "cstring"
using namespace std;
struct segment_tree
{
int left,right,num;
}tree[150010];
int a[50010];
int T,n;
void Build(int left,int right,int i)
{
tree[i].left=left;
tree[i].right=right;
if(left==right)
{
tree[i].num=a[left];
return;
}
int mid=(left+right)/2;
Build(left,mid,2*i);
Build(mid+1,right,2*i+1);
tree[i].num=tree[2*i].num+tree[2*i+1].num;
}
void Updata(int id,int num,int i)
{
if(tree[i].left==tree[i].right)
{
tree[i].num+=num;
return;
}
else
{
tree[i].num+=num;
if(id<=tree[i*2].right) Updata(id,num,i*2);
else Updata(id,num,i*2+1);
}
}
int Query(int left,int right,int i)
{
if(tree[i].left==left&&tree[i].right==right) return tree[i].num;
int mid=(tree[i].left+tree[i].right)/2;
if(right<=mid) return Query(left,right,i*2);
else if(left>mid) return Query(left,right,i*2+1);
else return Query(left,mid,i*2)+Query(mid+1,right,i*2+1);
}
int main()
{
int i,t1,t2;
char s[10];
scanf("%d",&T);
for(int k=1;k<=T;k++)
{
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
Build(1,n,1);
printf("Case %d:\n",k);
while(1)
{
scanf("%s",s);
if(strcmp(s,"End")==0) break;
scanf("%d%d",&t1,&t2);
if(strcmp(s,"Query")==0)
{
int ans=Query(t1,t2,1);
printf("%d\n",ans);
}
if(strcmp(s,"Sub")==0) Updata(t1,-t2,1);
if(strcmp(s,"Add")==0) Updata(t1,t2,1);
}
}
return 0;
}posted on 2010-11-14 12:45
wuxu 阅读(292)
评论(0) 编辑 收藏 引用 所属分类:
数据结构