單個更新；維護區間和。
以下是我的代碼：
#include<iostream>
#include<string>
#define maxn 50007
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
using namespace std;
const string _1("Add");
const string _2("Sub");
const string _3("Query");
const string end("End");
struct
{
long a,b,sum;
}seg[maxn*3];
long test,n,r[maxn];
void build(long node,long x,long y)
{
long mid=(x+y)>>1;
seg[node].a=x;seg[node].b=y;
if(x==y)
seg[node].sum=r[x];
else if(x<y)
{
build(L(node),x,mid);
build(R(node),mid+1,y);
seg[node].sum=seg[L(node)].sum+seg[R(node)].sum;
}
}
void add(long node,long pos,long det)
{
long a=seg[node].a,b=seg[node].b,mid=(a+b)>>1;
seg[node].sum+=det;
if(a<b)
{
if(mid>=pos)
add(L(node),pos,det);
else add(R(node),pos,det);
}
}
void sub(long node,long pos,long det)
{
long a=seg[node].a,b=seg[node].b,mid=(a+b)>>1;
seg[node].sum-=det;
if(a<b)
{
if(mid>=pos)
sub(L(node),pos,det);
else sub(R(node),pos,det);
}
}
long getsum(long node,long x,long y)
{
long a=seg[node].a,b=seg[node].b,mid=(a+b)>>1,re=0;
if(x<=a&&b<=y)
re=seg[node].sum;
else
{
if(mid>=x)
re+=getsum(L(node),x,y);
if(mid+1<=y)
re+=getsum(R(node),x,y);
}
return re;
}
int main()
{
long a,b;
string cmd;
cin>>test;
for(long k=1;k<=test;k++)
{
cin>>n;
for(long i=1;i<=n;i++) cin>>r[i];
build(1,1,n);
cout<<"Case "<<k<<":"<<endl;
while(cin>>cmd&&cmd!=end&&cin>>a>>b)
if(cmd==_1)
add(1,a,b);
else if(cmd==_2)
sub(1,a,b);
else if(cmd==_3)
cout<<getsum(1,a,b)<<endl;
}
return 0;
}
posted on 2010-02-24 10:50
lee1r 閱讀(429)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構