线段树应使用下标从1开始的tree数组存储，大小开4×n以避免越界；建树、查询、更新均需严格按区间[l,r]递归，注意叶子判断、子区间划分及回溯更新。
线段树节点怎么存才不爆内存又支持区间和
线段树本质是二叉树，但用数组模拟比指针更高效、更少出错。关键不是“写个树结构”，而是选对存储方式：tree 数组下标从 1 开始，tree[i] 表示对应区间的和，左子节点是 2*i，右子节点是 2*i+1。数组大小必须开到 4 * n（不是 2*n 或 2*n-1），否则建树或更新时越界——这是最常踩的坑。
原因：满二叉树叶子数为 n 时，总节点数最多约 2*n - 1；但 n 不一定是 2 的幂，实际要补到最近的 2 的幂，最坏情况（如 n = 2^k + 1）会导致树高增加一层，4*n 是安全上界。
build() 函数里递归边界和区间划分怎么写才不出错
建树函数 build 的核心是明确当前节点覆盖的区间 [l, r]，而不是依赖全局变量或模糊的“当前长度”。常见错误是把 mid 算成 (l + r) / 2 后没加括号，或递归调用时传错子区间。
正确写法要点：
立即学习“C++免费学习笔记（深入）”；
-
mid必须写成(l + r) >> 1或(l + r) / 2，且后续子区间严格为[l, mid]和[mid + 1, r] - 叶子节点判断是
l == r，此时直接赋值tree[idx] = arr[l]（注意arr下标是否从 0 起始） - 非叶子节点：先递归建左右子树，再
tree[idx] = tree[2*idx] + tree[2*idx + 1]
query() 区间查询时为什么老返回 0 或结果不对
查询函数 query 错误几乎都出在区间匹配逻辑上。它不是“找覆盖”，而是“分解覆盖”：把目标区间 [ql, qr] 拆成若干个线段树中已存的完整节点区间，并累加它们的 tree[idx] 值。
典型错误场景：
- 没写全三种情况：当前节点区间完全在查询区间外（直接 return 0）、完全在内（return tree[idx]）、部分重叠（递归查左右）
- 递归调用时传了错误的子区间，比如把
query(2*idx, l, mid, ql, qr)写成query(2*idx, l, r, ql, qr) - 忘了在部分重叠分支里加
return left_res + right_res，导致只返回一个子结果
示例片段（关键逻辑）：
if (qr < l || r < ql) return 0; if (ql <= l && r <= qr) return tree[idx]; int mid = (l + r) >> 1; return query(2*idx, l, mid, ql, qr) + query(2*idx+1, mid+1, r, ql, qr);
update() 单点修改后为什么区间和没变
单点更新 update 的本质是“从叶子往上修”，不是“找到节点就改”。最容易漏的是：改完叶子后，忘记沿父路径一路向上更新所有相关节点的和。
必须保证的步骤：
- 递归到底层叶子（
l == r），更新tree[idx] = val - 回溯时，每个非叶子节点都要重新计算：
tree[idx] = tree[2*idx] + tree[2*idx + 1] - 别用“懒更新”逻辑——这是区间更新才需要的，单点修改不需要
lazy数组
如果更新后查询结果不变，大概率是回溯没做，或者更新的 idx 对应错了原始数组下标（比如 arr 从 0 开始，但建树时用了 arr[i] 而不是 arr[i-1]）。
线段树难的不是代码量，而是每一步递归的区间语义是否清晰。一旦 l、r、ql、qr 的含义在脑中模糊，后面所有操作都会偏移。写的时候在纸上画两层节点，标清楚每个 tree[i] 对应哪段区间，比调十分钟 bug 更快。
