计蒜客：最甜的苹果（线段树）

 样例输入

5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

样例输出

5
6
5
9

这题我们需要维护的信息，从区间的和变成了区间内的最大值。现在区间的内的某个值可能增大可能减小，若从上到下（从根到叶）进行节点更新，我们无法直接判断目前区间内的最大的节点。

所以维护区间最大/最小值和维护区间和最大的不同就是：我们只能从下到上（从叶到根）进行节点更新。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 vector<int> maximum(200000 * 4);
 4 void modify(int p, int left, int right, int x, int y){
 5     if (left == right) {
 6         maximum[p] = y; //更新叶节点
 7         return;
 8     }
 9     int mid = (left + right) / 2;
10     if (x <= mid) {
11         modify(p * 2, left, mid, x, y);
12     } else {
13         modify(p * 2 + 1, mid + 1, right, x, y);
14     }
15     maximum[p] = max(maximum[p * 2], maximum[p * 2 + 1]); //叶节点更新完成后再更新最大值
16 }
17 int query(int p, int left, int right, int x, int y){
18     if (left >= x && right <= y){
19         return maximum[p];
20     }
21     int mid = (left + right) / 2, res, res1 = 0, res2 = 0;
22     if (x <= mid){
23         res1 = query(p * 2, left, mid, x, y);
24     }
25     if (y > mid){
26         res2 = query(p * 2 + 1, mid + 1, right, x, y);
27     }
28     return res = max(res1, res2);
29 }
30 int main(){
31     int n, m;
32     cin >> n >> m;
33     int temp, x, y;
34     char operation;
35     for (int i = 1; i <= n; ++i) {
36         cin >> temp;
37         modify(1, 1, n, i, temp);
38     }
39     while (m--) {
40         cin >> operation >> x >> y;
41         if (operation == 'Q') {
42             cout << query(1, 1, n, x, y) << endl;
43         } else {
44             modify(1, 1, n, x, y);
45         }
46     }
47 }