链接：https://vjudge.net/problem/HDU-1754
思路：
线段树模板题
代码：
//#include#include #include #include #include using namespace std;const int MAXN = 2e6+10;struct Node{ int value;//线段树中每个位置对应的最大值 int left,right;//位置对应的区间}node[MAXN*2];int Father[MAXN];int Max;void BuildTree(int i,int left,int right){ //构建线段树 node[i].left = left; node[i].right = right; node[i].value = 0; if (left == right) { Father[left] = i;//原数组位置对应在线段树中的结点 return; } BuildTree(i<<1,left,(int)(floor(left+right)/2.0));//构建左子树 BuildTree((i<<1)+1,(int)(floor(left+right)/2.0)+1,right);//构建右子树}void UpdateTree(int ri){ if (ri == 1) return ; int fi = ri/2; int a = node[fi<<1].value; int b = node[(fi<<1)+1].value;//当前结点和其兄弟结点 node[fi].value = max(a,b);//当前结点的父节点的最大值 UpdateTree(fi);}void Query(int i,int left,int right){ //查询区间最大值 if (node[i].left == left&&node[i].right == right) { Max = max(Max,node[i].value); return; } i <<= 1; if (left <= node[i].right)//查询区间交叉 { if (right <= node[i].right)//查询区间完全属于左结点 Query(i,left,right); else Query(i,left,node[i].right);//查询区间部分属于左节点 } i++; if (right >= node[i].left) { if (left >= node[i].left)//查询区间完全属于右结点 Query(i,left,right); else Query(i,node[i].left,right);//查询区间部分属于右结点 }}int main(){ int n,m,g; ios::sync_with_stdio(false); //while (cin >> n >> m) while (~scanf("%d%d",&n,&m)) { BuildTree(1,1,n); for (int i = 1;i<=n;i++) { scanf("%d",&g); node[Father[i]].value = g;//给只包含一个位置的结点更新值 UpdateTree(Father[i]);//初始化所有父节点 } char op[10]; int l,r; for (int i = 1;i<=m;i++) { //cin >> op >> l >> r; scanf("%s%d%d",op,&l,&r); if (op[0] == 'Q') { Max = 0; Query(1,l,r); cout << Max << endl; } else { node[Father[l]].value = r;//更新单个结点值 UpdateTree(Father[l]);//更新更改结点所有父节点 } } } return 0;}