这个题也是线段树的基础题，有了上一个题的基础，在做这个题就显得比较轻松了，大体都是一样的，那个是求和，这个改成求最大值，基本上思路差不多，下面是代码的实现
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int MAX = * ;
int segment[MAX];
//向上调整
void pushUp(int root)
{
segment[root] = max(segment[root * ], segment[root * + ]);
} void buildTree(int root, int left, int right)
{
if(left == right)
{
scanf("%d", &segment[root]);
return;
}
int mid = (left + right) / ;
buildTree(root * , left, mid);
buildTree(root * + , mid + , right);
//要把跟他上面所有关联的节点都要更新
pushUp(root);
}
//更新节点
void update(int root, int pos, int update_num, int left, int right)
{
if(left == right)
{
segment[root] = update_num;
return;
}
int mid = (left + right) / ;
if(pos <= mid)
{
update(root * , pos, update_num, left, mid);
}
else
{
update(root * + , pos, update_num, mid + , right);
}
pushUp(root);
}
//left和right为查到的区间，L和R为需要查询的区间
int getMax(int root, int left, int right, int L, int R)
{
if(L == left && R == right)
{
return segment[root];
}
int mid = (left + right) / ;
int Max_Num = ;
if(R <= mid)
{
Max_Num = getMax(root * , left, mid, L, R);
}
else if(L > mid)
{
Max_Num = getMax(root * + , mid + , right, L, R);
}
else
{
Max_Num = getMax(root * , left, mid, L, mid);
Max_Num = max(Max_Num, getMax(root * + , mid + , right, mid + , R));
}
return Max_Num;
} int main()
{
int N, M;
while(~scanf("%d %d", &N, &M))
{
memset(segment, , sizeof(segment));
buildTree(, , N);
char ch;
int t1, t2;
for(int i = ; i < M; i++)
{
getchar();
scanf("%c %d %d", &ch, &t1, &t2);
if(ch == 'U')
{
update(, t1, t2, , N);
}
else
{
printf("%d\n", getMax(, , N, t1, t2));
}
}
}
return ;
}