这是一道非常经典的单点修改 + 区间最值查询 (RMQ) 问题。由于涉及频繁的修改和查询，使用线段树（Segment Tree）可以将单次操作的时间复杂度降低到 $O(\log n)$，从而在限制时间内完成 $200,000$ 次操作。

线段树解决区间最值问题 (RMQ)

1. 题目分析

需求：
1. 区间查询 (Q a b)：查询 $[a, b]$ 区间内的最大值。
2. 单点更新 (U a b)：将 ID 为 $a$ 的成绩更新为 $b$（前提是 $b$ 更大）。
数据规模：$n, m \le 200,000$。如果使用暴力遍历，复杂度为 $O(n \times m)$，显然会超时。
最优解法：线段树。其查询和修改复杂度均为 $O(\log n)$，总复杂度 $O(m \log n)$。

2. 线段树设计思路

(1) 存储结构

使用一个数组 tree[] 来存储线段树节点，通常大小开到原数组的 4倍。

tree[node] 存储当前区间内的最大值。
根节点编号为 1，代表区间 $[1, n]$。
对于编号为 node 的节点：
- 左子节点编号为 node * 2 (或 node << 1)。
- 右子节点编号为 node * 2 + 1 (或 node << 1 | 1)。

(2) 核心操作

Build (建树)：递归划分区间，直到叶子节点（$L=R$），然后向上回溯，取左右子节点的较大值赋给父节点。
Update (单点修改)：找到对应的叶子节点修改值，然后一路上溯更新所有经过的父节点最大值。
Query (区间查询)：将查询区间 $[a, b]$ 拆分为线段树中已有的子区间。如果当前节点表示的区间完全被 $[a, b]$ 覆盖，直接返回该节点值；否则递归查询左右子树。

3. 代码实现 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200005;
int tree[MAXN * 4];
int scores[MAXN];

// 向上更新父节点
void push_up(int node) {
    tree[node] = max(tree[node << 1], tree[node << 1 | 1]);
}

// 建树：O(n)
void build(int node, int start, int end) {
    if (start == end) {
        tree[node] = scores[start];
        return;
    }
    int mid = (start + end) >> 1;
    build(node << 1, start, mid);
    build(node << 1 | 1, mid + 1, end);
    push_up(node);
}

// 单点修改：O(log n)
void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        // 题目要求：如果新成绩更高则更新
        tree[node] = max(tree[node], val);
        return;
    }
    int mid = (start + end) >> 1;
    if (idx <= mid) update(node << 1, start, mid, idx, val);
    else update(node << 1 | 1, mid + 1, end, idx, val);
    push_up(node);
}

// 区间查询：O(log n)
int query(int node, int start, int end, int L, int R) {
    if (L <= start && end <= R) {
        return tree[node];
    }
    int mid = (start + end) >> 1;
    int res = 0;
    if (L <= mid) res = max(res, query(node << 1, start, mid, L, R));
    if (R > mid) res = max(res, query(node << 1 | 1, mid + 1, end, L, R));
    return res;
}

int main() {
    ios::sync_with_stdio(false); // 优化输入输出
    cin.tie(0);

    int n, m;
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i++) cin >> scores[i];
        
        build(1, 1, n);

        for (int i = 0; i < m; i++) {
            char c;
            int a, b;
            cin >> c >> a >> b;
            if (c == 'Q') {
                // 题目可能出现 a > b 的情况，需要规范化
                if (a > b) swap(a, b);
                cout << query(1, 1, n, a, b) << "\n";
            } else if (c == 'U') {
                update(1, 1, n, a, b);
            }
        }
    }
    return 0;
}
````

---

### 4. 复杂度与注意事项

- **时间复杂度**：建树 $O(n)$，每次修改和查询 $O(\log n)$。总计 $O(n + m \log n)$。
    
- **空间复杂度**：$O(4n)$，主要是 `tree` 数组开销。
    
- **注意点**：
    
    - `ios::sync_with_stdio(false)`：对于 $200,000$ 级别的数据量，传统的 `cin/cout` 会非常慢，建议开启优化或使用 `scanf/printf`。
        
    - **区间合法性**：部分题目测试用例中查询区间 $[a, b]$ 可能出现 $a > b$ 的情况，处理前应做 `swap`。
        

### 5.线段树核心函数深度解析

线段树的三个核心操作：`build`（建树）、`update`（单点修改）、`query`（区间查询），都遵循递归结构。

---

#### 1. 建树函数 `build`：自底向上的初始化
建树的过程就像是在画一棵倒挂的二叉树。我们从根节点（代表区间 $[1, n]$）开始，不断二分。

* **核心逻辑**：
    1.  如果当前区间只有一个数（`start == end`），说明到达了叶子节点，直接赋值。
    2.  否则，递归构建左子树和右子树。
    3.  **PushUp**：子树构建完成后，父节点的值等于两个子节点值的最大值。

**核心代码块：**
```cpp
void build(int node, int start, int end) {
    if (start == end) {
        tree[node] = scores[start]; // 到达叶子节点，存储实际成绩
        return;
    }
    int mid = (start + end) >> 1;     // 找到区间中点
    build(node << 1, start, mid);     // 构建左子树 [start, mid]
    build(node << 1 | 1, mid + 1, end); // 构建右子树 [mid + 1, end]
    tree[node] = max(tree[node << 1], tree[node << 1 | 1]); // 合并子节点信息
}
````

--- 

#### 2. 单点修改 `update`：路径式更新

当你修改了某一个学生的成绩，线段树中从该叶子节点到根节点的路径上，所有父节点的信息都可能失效。

- **核心逻辑**：
    
    1. 通过二分查找，准确定位到代表学生 `idx` 的叶子节点。
        
    2. 更新叶子节点的值。
        
    3. 在递归回溯的过程中，重新计算路径上所有父节点的最大值。
        

**核心代码块：**


```cpp
void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        tree[node] = max(tree[node], val); // 更新叶子节点
        return;
    }
    int mid = (start + end) >> 1;
    if (idx <= mid) update(node << 1, start, mid, idx, val); // 目标在左半区
    else update(node << 1 | 1, mid + 1, end, idx, val);      // 目标在右半区
    tree[node] = max(tree[node << 1], tree[node << 1 | 1]);  // 回溯时更新父节点
}

3. 区间查询 `query`：区间拆解与合并

这是线段树最神奇的地方。查询 $[L, R]$ 时，它并不遍历每个点，而是寻找几个能完美拼凑成 $[L, R]$ 的“大块”区间。

核心逻辑：
1. 如果当前节点代表的区间 $[start, end]$ 完全包含在查询范围 $[L, R]$ 内，直接返回当前节点记录的最大值。
2. 如果不完全包含，则看 $[L, R]$ 是否跨越了中点 mid，分别去左右子树寻找。
3. 最后将结果汇总。

核心代码块：

C++

int query(int node, int start, int end, int L, int R) {
    // 情况1：当前区间完全在查询范围内
    if (L <= start && end <= R) return tree[node];

    int mid = (start + end) >> 1;
    int res = 0;
    // 情况2：查询范围与左子树有交集
    if (L <= mid) res = max(res, query(node << 1, start, mid, L, R));
    // 情况3：查询范围与右子树有交集
    if (R > mid) res = max(res, query(node << 1 | 1, mid + 1, end, L, R));
    
    return res;
}