代码线段树入门整理中有介绍、
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXNODE=<<;
const int MAX=;
struct NODE{
int left,right;
int value;
}node[MAXNODE];
int father[MAX];
void buildtree(int i,int left,int right)
{
node[i].left=left;
node[i].right=right;
node[i].value=;
if(left==right){
father[left]=i;
return;
}
buildtree(i<<, left, (int)floor( (right+left) / 2.0));
buildtree((i<<) + , (int)floor( (right+left) / 2.0) + , right); }
void updatatree(int ri)
{
if(ri==) return;
int fi=ri/;
int a=node[fi<<].value;
int b=node[(fi<<)+].value;
node[fi].value=a>b?a:b;
updatatree(ri/);
}
int maxn;
void query(int i,int l,int r)
{
if(node[i].left==l&&node[i].right==r){
maxn=(maxn<node[i].value)?node[i].value:maxn;
return;
}
i=i<<;
if(l<=node[i].right)
if(r<=node[i].right)
query(i,l,r);
else
query(i,l,node[i].right);
i+=;
if(r>=node[i].left)
if(l>=node[i].left)
query(i,l,r);
else
query(i,node[i].left,r);
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m)){
buildtree(,,n);
int grade;
for(int i=;i<=n;++i){
scanf("%d",&grade);
node[father[i]].value=grade;
updatatree(father[i]);
}
while(m--){
int x,y;char str[];
scanf("%s %d %d",str,&x,&y);
if(str[]=='U'){
node[father[x]].value=y;
updatatree(father[x]);
}
else{
maxn=;
query(,x,y);
printf("%d\n",maxn);
}
}
}
}