线段树
#include<stdio.h> #include<string.h> #define MAXN 200005 struct ST //存储类型 { int l,r,max; //max表示当前节点的最大值 }st[4*MAXN]; inline int max(int a,int b) { return a>b?a:b; } void build(int ll,int rr,int n) //初始化建立线段树 { st[n].l=ll; //表示当前节点的最左端， st[n].r=rr; //表示当前节点的最右端， st[n].max=0; //当前节点的值，初始化全为零， if (ll==rr) return ; //如果遇到了根节点 int mid=(ll+rr)/2; //将当前节点分开，mid为左孩子的右端点，为右孩子的左端点； build(ll,mid,2*n); //先遍历左边的树 build(mid+1,rr,2*n+1); //再遍历右边的树 } void insert(int ll,int rr,int a,int n) // 更新 { if (st[n].l==ll&&st[n].r==rr) {st[n].max=a;return ;}//如果找到，就赋值，退出。 else if (a>st[n].max) st[n].max=a; //从新更新； int mid=(st[n].l+st[n].r)/2; if (rr<=mid) //如果右端点比他的中间区分值mid还小，那么久插到左边， insert(ll,rr,a,2*n); else if (ll>=mid+1) //如果左端点比他的中间区分值mid还大，那么久插到右边， insert(ll,rr,a,2*n+1); } int find(int ll,int rr,int n) // 查询 { if (st[n].l==ll&&st[n].r==rr) return st[n].max; //返回max； int mid=(st[n].l+st[n].r)/2; if (rr<=mid) //如果rr小于中点分解值，那么就查找左孩子， find(ll,rr,2*n); else if (ll>=mid+1) //如果rr大于于中点分解值，那么就查找右孩子， find(ll,rr,2*n+1); else return max(find(ll,mid,2*n),find(mid+1,rr,2*n+1)); } int main() { int n,m,a,b,i; char op; while (scanf("%d%d",&n,&m)!=EOF) { build(1,n,1); for (i=1;i<=n;++i) { scanf("%d",&a); insert(i,i,a,1); } getchar(); for (i=1;i<=m;++i) { scanf("%c %d %d",&op,&a,&b); getchar(); if (op=='Q') printf("%d\n",find(a,b,1)); if (op=='U') insert(a,a,b,1); } } return 0; }