#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
#define MAX 50000
int sum1;
struct Node
{
int left,right,sum;
}stu[3*MAX];
void CreateTree(int ii,int a,int b)//建树的结果只是形成一个空箱子 里面什么东西都没有 只有区间的两端
{
stu[ii].left = a;
stu[ii].right = b;
stu[ii].sum = 0;
if(a == b)
{
return;
}
else
{
int mid = (a+b)>>1;
CreateTree(ii*2,a,mid);
CreateTree(ii*2+1,mid+1,b);
}
}
void updata(int ii,int a,int b)//ii:数组的标记 要修改的节点 修改的值
{
if(stu[ii].left == a && stu[ii].right == a)
{
stu[ii].sum+= b;
}
else
{
int mid = (stu[ii].left+stu[ii].right)>>1;
if(a <= mid)
{
updata(ii*2,a,b);
}
else
{
updata(ii*2+1,a,b);
}
stu[ii].sum += b;
}
}
void find(int ii,int a,int b)
{
if(stu[ii].left == a && stu[ii].right == b)//如何区间断点正合适 直接取区间内的最大值相比较
{
sum1+= stu[ii].sum;
}
else
{
int mid = (stu[ii].left + stu[ii].right)>>1;
if(b <= mid)//如果a b都在左子树里 则查询左子树
{
find(ii*2,a,b);
}
else if(a > mid)//如果a b都在右子树里则查询右子树
{
find(ii*2+1,a,b);
}
else//如果a b横跨左右子树则分别找左右子树
{
find(ii*2,a,mid);
find(ii*2+1,mid+1,b);
}
}
}
int main()
{
int t;
cin>>t;
for(int l=1;l<=t;l++)
{
cout<<"Case "<<l<<":"<<endl;
int n;
cin>>n;
CreateTree(1,1,n);
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
updata(1,i,a);
}
string s;
while(cin>>s)
{
int b,c;
sum1=0;
if(s=="End")
break;
cin>>b>>c;
if(s=="Add")
updata(1,b,c);
else if(s=="Sub")
updata(1,b,-c);
else if(s=="Query")
{
find(1,b,c);
cout<<sum1<<endl;
}
}
}
return 0;
}
转载于:https://www.cnblogs.com/cyiner/archive/2011/07/14/2106495.html
