编辑“︁线段树”︁（章节）

== 基本概念 ==
线段树是一种'''平衡二叉树'''，其中每个叶子节点存储原始数据的一个元素，而每个非叶子节点存储其子节点对应区间的某种聚合信息（如区间和、区间最大值等）。线段树的构建、查询和更新操作均基于递归实现。

=== 结构特点 ===
* 叶子节点：存储原始数组的单个元素。
* 非叶子节点：存储其子节点对应区间的聚合信息。
* 区间划分：每个非叶子节点<math>[l, r]</math>的左子节点为<math>[l, \text{mid}]</math>，右子节点为<math>[\text{mid}+1, r]</math>，其中<math>\text{mid} = \lfloor \frac{l + r}{2} \rfloor</math>。

<mermaid>
graph TD
    A["[1, 4] (Sum: 10)"] --> B["[1, 2] (Sum: 3)"]
    A --> C["[3, 4] (Sum: 7)"]
    B --> D["[1, 1] (Sum: 1)"]
    B --> E["[2, 2] (Sum: 2)"]
    C --> F["[3, 3] (Sum: 3)"]
    C --> G["[4, 4] (Sum: 4)"]
</mermaid>