http://acm.hdu.edu.cn/showproblem.php?pid=1754
线段树功能：
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #define MAXN 200005 int seg_tree[MAXN<<2]; void build_tree(int l,int r,int id); int query_tree(int left,int right,int l,int r,int id); void update_point_tree(int left,int right,int value,int l,int r,int id); void push_up_tree(int id); int main() { int tcase,n,i,left,right,value,m; char str[20]; while(scanf("%d%d",&n,&m)==2) { build_tree(1,n,1); while(m--) { scanf("%s",str); if(str[0]=='Q') { scanf("%d%d",&left,&right); printf("%d\n",query_tree(left,right,1,n,1)); } if(str[0]=='U') { scanf("%d%d",&left,&value); update_point_tree(left,right,value,1,n,1); } } } } void build_tree(int l,int r,int id) { if(l==r) { scanf("%d",&seg_tree[id]); return ; } int mid=(l+r)/2; build_tree(l,mid,id<<1); build_tree(mid+1,r,id<<1|1); push_up_tree(id); } int query_tree(int left,int right,int l,int r,int id) { if(left<=l&&right>=r) return seg_tree[id]; int mid=(l+r)>>1,ret0=0,ret1=0; if(left<=mid) ret0=query_tree(left,right,l,mid,id<<1); if(right>mid) ret1=query_tree(left,right,mid+1,r,id<<1|1); return ret0>=ret1?ret0:ret1; } void update_point_tree(int left,int right,int value,int l,int r,int id) { if(l==r) { seg_tree[id]=value; return ;} int mid=(l+r)>>1; if(left<=mid) update_point_tree(left,right,value,l,mid,id<<1); else update_point_tree(left,right,value,mid+1,r,id<<1|1); push_up_tree(id); } void push_up_tree(int id) { int temp1,temp2; temp1=seg_tree[id<<1]; temp2=seg_tree[id<<1|1]; seg_tree[id]=(temp1>=temp2?temp1:temp2); }