线段树建树数组需开4×n，因完全二叉树最坏需2^(⌈log₂n⌉+1)−1<4n个节点，开4n最稳妥；只开2n易越界；单点更新必须自底向上更新所有父节点，否则聚合信息失效。
线段树建树时数组大小为什么必须开到 4×n
因为线段树是二叉树结构，最坏情况下叶子节点全在最后一层，而标准实现用数组模拟完全二叉树——根在 1，左子节点是 2*i，右子是 2*i+1。当原数组长度为 n，满二叉树最多需要 2^(⌈log2(n)⌉+1)-1 个节点，这个值始终小于 4*n。开 4*n 是最稳妥的下界，比算精确值快且不易越界。
常见错误：只开 2*n 或 n*2+1，在 n 不是 2 的幂时，递归建树途中会写到数组外，引发未定义行为（比如查询结果随机、程序崩溃）。
- 若用 vector 动态分配，直接初始化为
vector<int>(4 * n)</int> - 若用全局数组，别写
int tree[N]然后设N = 100005—— 要设N = 400020 - 调试时可在建树函数里加边界检查：
if (idx >= tree.size()) { throw runtime_error("tree overflow at " + to_string(idx)); }
单点更新后为什么不能只改叶子节点
线段树每个非叶节点存的是其子树区间的信息聚合（这里是最大值）。如果只改叶子节点对应位置的 tree[idx]，父节点的值就不再反映真实子区间的最大值，后续所有跨区间的查询都会出错。
必须自底向上更新路径上的所有父节点。从叶子索引开始，每次除以 2（整数除法），直到根节点 1：
立即学习“C++免费学习笔记（深入）”；
void update(int idx, int l, int r, int pos, int val) {
if (l == r) {
tree[idx] = val;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(idx*2, l, mid, pos, val);
else update(idx*2+1, mid+1, r, pos, val);
tree[idx] = max(tree[idx*2], tree[idx*2+1]); // ← 关键：回溯时刷新父节点
}- 漏掉这行
tree[idx] = max(...)是新手最高频 bug，会导致后续所有query返回旧值 - 不要试图“懒更新”来省事——RMQ 没有区间修改需求，无需 lazy tag，强行加反而引入冗余逻辑和 bug
- 更新复杂度是
O(log n)，不是O(1)，这点必须心里有数
区间查询函数里 mid 和左右子树边界的计算必须严格对齐
查询时若区间划分不一致，会导致部分数据被跳过或重复计算，结果偏小。关键在于：当前节点覆盖 [l, r]，它左子树管 [l, mid]，右子树管 [mid+1, r]，其中 mid = (l + r) / 2（向下取整）。这个 mid 必须和建树/更新时用的完全一致。
错误写法举例：mid = (l + r + 1) / 2 或把右子树写成 [mid, r] —— 这会让 [l,r] 被错误拆分，尤其当 l==r-1 时，可能漏掉一个元素。
- 统一用
int mid = l + (r - l) / 2避免l+r溢出（虽然一般不会，但严谨起见） - 查询分支逻辑只分三种情况：查询区间完全在左、完全在右、横跨中点——没有第四种
- 横跨时必须调用两次递归再取
max，不能只查一边然后补一个端点值
构造线段树前要不要对原数组离散化
不需要。RMQ（Range Maximum Query）只依赖数值大小关系，不涉及哈希、映射或坐标压缩。离散化是为了解决值域过大但实际出现数少的问题（如坐标压缩、权值线段树），而这里我们只关心下标区间内的最大值，原始值直接参与比较即可。
真正要小心的是：输入数组是否含负数？是否全为 INT_MIN？这些不影响线段树逻辑，但会影响初始化哨兵值的选择。
- 建树前初始化
tree数组，不要用0当默认值——应设为INT_MIN（#include <climits>） - 如果题目保证数值 ≥ 0，可用
0初始化，但不如统一用INT_MIN省心 - 离散化反而会破坏原下标到值的映射，让单点更新
pos失去意义
边界情况比想象中多：空区间、单元素、n=1、多次更新同一位置……测试时至少覆盖这几种，否则上线后遇到特殊输入就挂。
