链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1754
这次的代码和上个代码很相似，只不过上次的节点里存的是sum值，这次节点里存放的是Max， 正在慢慢找感觉
节点里保存的值是十分重要的！！！！
代码：
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
using namespace std; #define Lson r<<1
#define Rson r<<1|1 const int N = *1e6+; struct SegmentTree
{
int L, R;
int MAX;
int Mid()
{
return (R+L)>>;
}
}a[N<<]; void BuildSegTree(int r, int L, int R)
{
a[r].L=L, a[r].R=R; if(L==R)
{
scanf("%d", &a[r].MAX);
return ;
} BuildSegTree(Lson, L, a[r].Mid());
BuildSegTree(Rson, a[r].Mid()+, R); a[r].MAX = max(a[Lson].MAX, a[Rson].MAX);
} void Update(int r, int i, int e)
{
a[r].MAX = max(a[r].MAX, e); if(a[r].L==a[r].R)
return ; if(i<=a[r].Mid())
Update(Lson, i, e);
else if(i>a[r].Mid())
Update(Rson, i, e);
} int Query(int r, int L, int R)
{
if(a[r].L==L && a[r].R==R)
return a[r].MAX; if(R<=a[r].Mid())
return Query(Lson, L, R);
else if(L>a[r].Mid())
return Query(Rson, L, R);
else
{
int Lsum = Query(Lson, L, a[r].Mid());
int Rsum = Query(Rson, a[r].Mid()+, R); return max(Lsum, Rsum);
}
} int main()
{
int n, m; while(scanf("%d%d", &n, &m)!=EOF)
{
BuildSegTree(, , n); char s[];
int L, R, A, B; while(m--)
{
scanf("%s", s);
if(s[]=='Q')
{
scanf("%d%d", &L, &R);
printf("%d\n", Query(, L, R));
}
else
{
scanf("%d%d", &A, &B);
Update(, A, B);
}
}
}
return ;
}