線段樹的入門題 用來查詢區間的最大最小值
是用模板過的 不過也是在看懂之后 才會用
#include <stdio.h>
#define N 200000+1
struct Node
{
int l,r;
int max;
}seg[3*N];
int num[N];
int ans;
int Max(int a,int b)
{
return a>b?a:b;
}
void build(int l,int r,int k)
{
seg[k].l=l;
seg[k].r=r;
if(l==r)
{
seg[k].max = num[l];
return ;
}
else
{
int mid = (l+r)/2;
build(l,mid,2*k);
build(mid+1,r,2*k+1);
seg[k].max = Max(seg[2*k].max,seg[2*k+1].max);
}
return ;
}
void Search(int l,int r,int k)
{
if(seg[k].l==l && seg[k].r==r)
{
if(seg[k].max>ans)
ans = seg[k].max;
return ;
}
else
{
int mid=(seg[k].l+seg[k].r)/2;
if(mid>=r)
Search(l,r,2*k);
else if(mid<l)
Search(l,r,2*k+1);
else
{
Search(l,mid,2*k);
Search(mid+1,r,2*k+1);
}
}
}
void Update(int l,int r,int value,int k)
{
if(seg[k].l== l && seg[k].r==r)
{
seg[k].max = value;
return ;
}
else
{
int mid = (seg[k].l+seg[k].r)/2;
if(mid>=r)
Update(l,r,value,2*k);
else if(mid<l)
Update(l,r,value,2*k+1);
else
{
Update(l,mid,value,2*k);
Update(mid+1,r,value,2*k+1);
}
seg[k].max = Max(seg[2*k].max,seg[2*k+1].max);
}
return ;
}
int main()
{
char ch;
int a,b,m,n,i;
while(scanf("%d%d",&m,&n)!=EOF)
{
for(i=1;i<=m;i++)
scanf("%d",num+i);
build(1,m,1);
for(i=0;i<n;i++)
{
getchar();
ch = getchar();
if(ch=='Q')
{
scanf("%d%d",&a,&b);
ans = 0;
Search(a,b,1);
printf("%d\n",ans);
}
else if(ch=='U')
{
scanf("%d%d",&a,&b);
Update(a,a,b,1);
}
}
}
return 0;
}
posted on 2010-05-13 16:08
付翔 閱讀(113)
評論(0) 編輯 收藏 引用 所屬分類:
ACM 數據結構