被線段樹折磨了這么久，今天終于把它給寫出來了……用的是數組模擬樹。
功能：創建一棵線段樹；給a[i]加上一個值；求一個區間的最大值。
以下是我的代碼：
/*
Author >> Lee1R
Time >> 02,16,2010 23:37
//*/
#include<stdio.h>
const long maxn=10007;
typedef struct NODE
{
long a,b,sum;
long left,right;
}node;
long n,m,a[maxn];
node tree[maxn];long tot;
void creat(long begin,long end)
{
long now,mid=(begin+end)/2;
tot++;now=tot;
tree[now].a=begin;tree[now].b=end;
if(end-begin<=1)
{
tree[now].left=-1;
tree[now].right=-1;
tree[now].sum=a[begin]+a[end];
}
else
{
tree[now].left=tot+1;creat(begin,mid);
tree[now].right=tot+1;creat(mid,end);
tree[now].sum=tree[tree[now].left].sum+tree[tree[now].right].sum-a[mid];
}
}
void add(long pos,long det,long node)
{
long begin=tree[node].a,end=tree[node].b,mid=(begin+end)/2;
tree[node].sum+=det;
if(end-begin==1) return;
if(pos>=begin&&pos<=mid)
add(pos,det,tree[node].left);
if(pos>=mid&&pos<=end)
add(pos,det,tree[node].right);
}
long getsum(long begin,long end,long node)
{
long re=0,t=(tree[node].a+tree[node].b)/2;
if(tree[node].b-tree[node].a==1) re=tree[node].sum;
else
{
if(end<=t)
re=getsum(begin,end,tree[node].left);
else if(begin>=t)
re=getsum(begin,end,tree[node].right);
else
re=getsum(begin,t,tree[node].left)+getsum(t,end,tree[node].right)-a[t];
}
return re;
}
int main()
{
//*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
scanf("%ld",&n);
for(long i=1;i<=n;i++) scanf("%ld",&a[i]);
tot=0;creat(1,n);
// Init
scanf("%ld",&m);
for(long i=1;i<=m;i++)
{
long t,b,c;
scanf("%ld%ld%ld",&t,&b,&c);
switch(t)
{
case 1:
a[b]+=c;
add(b,c,1);
break;
case 2:
if(b==c) printf("%ld\n",a[b]);
else printf("%ld\n",getsum(b,c,1));
break;
}
}
return 0;
}
posted on 2010-02-17 13:33
lee1r 閱讀(295)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數據結構