因为线段树最坏需满二叉树结构，节点数上限为 $2 \times 2^{\lceil \log_2 n \rceil} - 1
线段树构建时数组大小为什么必须开到 4×n？
因为线段树是二叉树结构，最坏情况下需要满二叉树的节点数。对于 n 个叶子节点，高度为 ⌈log₂n⌉，总节点数不超过 2×2⌈log₂n⌉−1，而 4×n 是一个安全、易记且能覆盖所有 n 的上界（比如 n=1e5 时，217=131072，4×n=4e5 > 262143）。不开够会导致
seg[2*idx]或seg[2*idx+1]数组越界，运行时崩溃或结果错乱。常见错误现象：
Segmentation fault、查询返回 0 或随机大数、部分区间结果不稳定。
- 不要用
vector seg(n*2)—— 不够，且下标计算会错位- 推荐写法：
vectorseg(4 * n); - 若用全局数组，也请按
int seg[400010];类似方式预留单点更新后为什么必须 pushUp，而查询不需要 pushDown？
线段树维护的是“区间信息聚合”，
pushUp是把子区间的最大值合并到父节点（如seg[idx] = max(seg[2*idx], seg[2*idx+1])），这是构建和更新的必要步骤；而标准 RMQ（静态/单点更新）不涉及区间懒标记，pushDown只在带区间修改（如区间加、区间赋值）时才需要。误加pushDown不仅多余，还会因未实现懒数组导致未定义行为。使用场景：你只做
update(i, val)和query(l, r)，没有updateRange(l, r, val)—— 那就完全不需要pushDown和lazy数组。
- 单点更新函数末尾必须调用
pushUp(idx)- 查询函数中，只要当前区间被完全包含，直接 return
seg[idx]，不向下递归也无需下推- 如果后续要支持区间修改，再补
lazy和pushDown，但那是另一套逻辑query(l, r) 的递归边界与 mid 计算怎么写才不出错？
边界处理错误是 RMQ 查询最常出 bug 的地方，核心在于：左闭右闭区间 [l, r] 下，
mid必须用(l + r) / 2（整除向零），且左右子树分别对应 [l, mid] 和 [mid+1, r] —— 这样才能无重无漏覆盖原区间。用(l + r + 1) / 2或错配子区间会导致跳过元素或重复统计。典型错误现象：查询 [0,0] 返回初值（如 0）、查询长度为 2 的区间返回较小值、对称区间结果不对称。
- 建树和查询中统一用：
int mid = (l + r) / 2;- 左子树查
[l, mid]，右子树查[mid + 1, r]- 查询入口确保
l ，且初始调用是query(1, 0, n-1, ql, qr)（假设 0-indexed 原数组）- 递归终止条件：if
ql → 直接返回seg[idx]为什么比 Sparse Table 慢但更通用？
ST 表预处理 O(n log n)，查询 O(1)，但只支持静态数组；线段树预处理 O(n)，单点更新 O(log n)，查询 O(log n)，支持动态修改。实际项目中，只要存在插入、删除、单点改值等操作，ST 表就不可用，线段树是唯一合理选择。
性能影响：n=1e6 时，线段树单次查询约 20 层递归，现代 CPU 下不到 1μs；而手写栈或迭代式线段树虽可省函数调用开销，但可读性和调试成本陡增，非极端场景不值得。
- 别为了“理论上快”强行手写非递归版本，C++ 编译器对尾递归优化有限，但 20 层栈帧毫无压力
- 如果真卡常，优先检查是否用了
cin/cout而没关同步，或vector是否反复 resize- 真正容易被忽略的是：建树后忘记把原数组值赋给叶子节点——
seg[idx] = arr[l];这一行漏掉，整个树全是 0
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
