线段树建树需至少4×n空间，因二叉树最坏情况下叶子节点分布不连续，2×n易越界；RMQ场景若无区间更新，应删除lazy逻辑；纯单点修改+查询用ST表更优。
线段树建树为什么必须用 2N 空间？
直接开 vector<int> tree(2 * n)</int> 是常见错误——实际需要至少 4 * n。因为线段树是二叉树结构，最坏情况下叶子节点在最后一层不连续分布，标准实现中为避免越界和简化下标计算，普遍采用 4 * n 容量。若用 2 * n，当 n 不是 2 的幂时，递归建树大概率触发 std::out_of_range 或读到未初始化内存。
实操建议：
- 统一声明为
vector<int> tree(4 * n)</int>，别省那点内存 - 若确定
n是 2 的幂（比如手动补零到最近 2^k），可用2 * n，但需额外校验n > 0 && (n & (n-1)) == 0 - 建树函数参数推荐用闭区间
[l, r]，递归终止条件写成if (l == r)，比开区间更不易漏边界
单点更新后 query 区间最大值总不对？检查 lazy 标记是否误用
RMQ 场景下绝大多数情况**不需要 lazy 传播**。线段树支持区间更新才需 lazy；而纯最大值查询 + 单点修改（如 update(i, val)）只需自底向上更新路径上的节点，时间复杂度 O(log n)。一旦加了 lazy，反而会因未清空或误传播导致查询结果滞后或错乱。
典型错误现象：
立即学习“C++免费学习笔记（深入）”；
- 第一次
update后query正确，第二次就返回旧值 -
query(0, n-1)返回整个数组最大值，但query(0, 0)却不是最新值
解决办法：删掉所有 lazy 数组、push_down 和 push_up 中涉及 lazy 的逻辑，只保留 push_up（即 tree[node] = max(tree[left], tree[right])）。
query 函数递归边界怎么写才不漏区间？
关键在三个分支判断顺序：先判「当前节点对应区间完全在查询区间内」，再判「完全无交集」，最后递归左右子树。顺序颠倒会导致跳过有效子树。
正确模板片段：
int query(int node, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[node]; // 完全包含
if (qr < l || r < ql) return INT_MIN; // 完全不交
int mid = (l + r) / 2;
return max(query(node*2, l, mid, ql, qr),
query(node*2+1, mid+1, r, ql, qr));
}注意点：
-
ql和qr是查询的闭区间，与建树时的[l, r]语义一致 - 返回
INT_MIN而非0，否则数组含负数时出错 - 不要用
(l + r) >> 1替代(l + r) / 2，虽等价但可读性差，且在极端大整数时有溢出风险（C++ 中int相加可能溢出）
构建线段树比 ST 表慢很多？别在 RMQ 场景硬套线段树
如果只有静态数组、查询远多于修改，ST 表（Sparse Table） 的 O(n log n) 预处理 + O(1) 查询完胜线段树的 O(n) 建树 + O(log n) 查询。线段树真正的优势是支持单点/区间修改，而非纯查询。
选型建议：
- 输入后不再修改 → 用
ST 表，代码量少、常数小、不易写错 - 有
update(i, val)或update(l, r, val)→ 才值得上线段树 - 若真要优化线段树建树速度，把递归改成 BFS 层序建树（但意义不大，
O(n)本来就不慢）
真正容易被忽略的是：线段树的常数比 ST 表大 3–5 倍，同一台机器上 1e6 数据，ST 表查询耗时可能不到 1ms，线段树可能接近 5ms——这在高频实时服务里就是瓶颈。
