线段树入门题
中文题就不说题意了。就是基本的区间询问最大值和修改某个特定单元的值，初学线段树，自己硬生生啃出来的代码，写得不好，不过1Y了这道题很是鼓舞。时间上500ms，不知道那些100ms是怎么做到的
#include <cstdio> #include <cstring> #define N 200010 #define INF 0x3f3f3f3f struct segment_tree { int a,b; //区间 int l,r; //左右孩子 int max; }tree[2*N]; int a[N]; int tot; //线段树结点的个数 int n,m; //区间长度和询问的个数 int query(int num , int a , int b) //区间[a,b] { //if(tree[num].b<a || tree[num].a>b) //该结点的区间和需要询问的区间不想交 //return -INF; if(tree[num].a==a && tree[num].b==b) //完全重合直接返回最大值 return tree[num].max; int mid,max1,max2; mid=(tree[num].a+tree[num].b)/2; max1=max2=-INF; if(a>mid) //不需要在左半区间中查找 max2=query(tree[num].r,a,b); else if(b<=mid) //不需要在右半区间中查找 max1=query(tree[num].l,a,b); else //横跨两个部分 { max1=query(tree[num].l,a,mid); max2=query(tree[num].r,mid+1,b); } return max1>max2?max1:max2; } void updata(int num , int p ,int e) //要将p位置的值变为e { if(tree[num].a==tree[num].b) { tree[num].max=e; return ; } int mid=(tree[num].a+tree[num].b)/2 , max,tmp; if(p<=mid) //去左半区间查找 { updata(tree[num].l , p ,e); tmp=tree[num].l; } else //去右半区间查找 { updata(tree[num].r , p , e); tmp=tree[num].r; } max=tree[tmp].max ; if(max>tree[num].max) tree[num].max=max; return ; } int create_tree(int x ,int y , int num) { if(x==y) //元结点 { tree[num].a=tree[num].b=x; tree[num].l=tree[num].r=-1; return tree[num].max=a[x]; } int mid=(x+y)/2,max1,max2,num1,num2; tree[num].a=x; tree[num].b=y; num1=tot+1; num2=tot+2; tree[num].l=++tot; tree[num].r=++tot; max1=create_tree(x,mid,num1); max2=create_tree(mid+1,y,num2); return tree[num].max=max1>max2?max1:max2; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1; i<=n; i++) scanf("%d",&a[i]); tot=1; create_tree(1,n,1); //建树 while(m--) //读入m个询问 { char s[5]; int tmp1,tmp2; scanf("%s%d%d",s,&tmp1,&tmp2); if(!strcmp(s,"Q")) //询问区间的最大值 { int ans=query(1,tmp1,tmp2); //区间为[tmp1,tmp2],从第1个结点开始 printf("%d\n",ans); } else //更改数值 updata(1,tmp1,tmp2); } } return 0; }