数组实现线段树通过下标映射模拟完全二叉树结构：节点i的左右子节点分别为2i和2i+1，根从1开始；数组长度取≥4×n或精确为2×next_power_of_2(n)−1；支持O(log n)单点/区间更新与查询，配合懒标记实现高效区间修改。
用数组实现线段树，核心是把树结构“压平”到一维数组里，靠下标规律模拟父子关系，从而高效支持区间查询（如求和、最值）和单点/区间更新。关键不在背公式，而在理解索引映射逻辑和递归边界控制。
数组下标如何对应树节点
线段树通常用完全二叉树建模，根节点编号为 1（避免 0 作根时左子节点为 0 的歧义），则：
- 节点 i 的左子节点在 2*i
- 节点 i 的右子节点在 2*i + 1
- 叶子节点对应原始数组的单个元素，按中序或层序铺开
- 数组总长一般取 ≥ 4×n 的最小 2 的幂（保守但安全），或精确计算：若原数组长 n，线段树数组长度 ≈ 2×next_power_of_2(n)−1
例如原数组 [1,3,5,7]（n=4），可直接用大小为 15 的数组（4 层满二叉树共 2⁴−1=15 个节点），根在索引 1，tree[1] 存整个区间 [0,3] 的信息。
建树与单点更新的数组操作要点
建树用后序递归：先建左右子树，再合并信息（如求和就是 tree[i] = tree[2*i] + tree[2*i+1]）。单点更新从叶子向上回溯修改所有受影响的父节点。
- 叶子位置计算：若原数组下标从 0 开始，值
a[k]对应的叶子节点索引，需先定位到树的最底层——常用方法是让所有叶子集中在数组后半段，即设 base = 最小 ≥ n 的 2 的幂，叶子 i 映射到base + i（适合堆式存储）；或用标准递归方式不显式找叶子，而是递归到区间长度为 1 时赋值 - 更新时无需重建整棵树，只改 log₂n 个节点，时间复杂度 O(log n)
- 注意数组索引越界检查，尤其当 n 不是 2 的幂时，叶子区间可能不完全对齐
区间查询的递归拆分逻辑
查 [l, r] 时不硬套中点，而是用当前节点代表的区间 [s, e] 去比对：
- 若 [s, e] 完全在 [l, r] 内 → 直接返回
tree[i] - 若 [s, e] 与 [l, r] 无交 → 返回中性值（如求和返回 0，求最值返回 −∞）
- 否则递归查左子树 [s, m] 和右子树 [m+1, e]，合并结果
例如查 [1,2] 在 4 元素数组上，会触发根 [0,3] → 拆为 [0,1] 和 [2,3] → [0,1] 再拆为 [0,0] 和 [1,1]，其中 [1,1] 被命中；[2,3] 拆得 [2,2] 被命中；最终合并 a[1] + a[2]。
懒标记（Lazy Propagation）在数组中的落地
支持区间更新（如 [l,r] 都加 x）时，不能每点都更新，需引入懒数组 lazy[]，与 tree[] 同长，仅在节点对应区间被完整覆盖且需延迟下发时记录操作。
- 每次进入节点前先下传：若
lazy[i] != 0，则更新tree[i]，并把 lazy 值推给两个子节点（lazy[2*i] += lazy[i]，lazy[2*i+1] += lazy[i]），再清空lazy[i] = 0 - 区间更新时，若当前 [s,e] ⊆ [l,r]，直接改
tree[i]并设lazy[i] += x；否则照常递归 - 下传和更新都只涉及数组索引计算，无指针操作，简洁但需严格保证下传时机
懒标记让区间更新也保持 O(log n)，是数组实现线段树处理动态区间的真正实用基础。
