7.14 数据结构（一）: 线段树，树状数组，二维线段树

### 数据结构专题：线段树、树状数组与二维线段树 #### 一、线段树概述 **线段树（Segment Tree）**是一种高效的数据结构，主要用于处理区间查询和更新问题。它通过将一个大的区间划分为若干个较小的区间来实现高效的区间操作。在ACM/ICPC竞赛中，线段树是非常重要的工具之一。 **定义：** - **树形结构**：线段树本质上是一棵二叉树。 - **区间表示**：树中的每个节点都对应一个区间，如 `[a, b]`，其中 `a` 和 `b` 通常是整数。 - **叶子节点**：叶子节点代表单个元素或单位区间，长度为1。 - **内部节点**：内部节点的左右子节点分别表示 `[a, (a+b)/2]` 和 `[(a+b)/2+1, b]` （向下取整）。 #### 二、线段树的构建 **构建过程：** 1. **初始化根节点**：假设根节点表示的区间是 `[1, n]`，即整个数组的范围。 2. **递归构建**：对于每一个节点，如果区间不是单位长度，则进一步划分为左右子区间，并构建左右子树。 **示例**：构建区间 `[1, 9]` 的线段树。 ``` [1,9] [1,5] [6,9] [1,3] [4,5] [6,7] [8,9] ``` - **特性**： - 深度不超过 `log2(n)+1`。 - 节点数量为 `2N-1`，其中 `N` 是叶子节点的数量。 - 叶子节点的数目等于根节点表示区间的长度。 - 更新和查询的时间复杂度均为 `O(log(n))`。 #### 三、线段树的查询与更新 **查询操作**：查询指定区间 `[i, j]` 的信息。 - **分解区间**：将查询区间分解为一系列不相交的子区间。 - **查询子区间**：计算每个子区间的和等信息。 **更新操作**：更新数组中某个元素的值。 - **更新路径**：找到覆盖更新位置的所有节点并进行相应的更新。 **示例**：对于区间 `[2, 8]` 的查询操作。 ``` [1,9] [1,5] [6,9] [1,3] [4,5] [6,7] [8,9] ``` - **分解**：查询 `[2, 8]` 会分解为 `[2, 5]` 和 `[6, 8]`。 - **查询节点**：最终涉及的查询节点为 `[2, 3]`, `[4, 5]`, `[6, 7]`, `[8, 9]`。 #### 四、树状数组（Binary Indexed Tree） **树状数组**是另一种用于处理区间查询和更新问题的有效数据结构。相较于线段树，树状数组的空间占用更少，但在实现上稍微复杂一些。 **特点**： - **低比特位操作**：利用低比特位的操作来维护数据结构。 - **更新与查询**：支持单点更新和前缀和查询，时间复杂度均为 `O(log(n))`。 **应用场景**：树状数组适用于需要频繁进行单点更新和前缀和查询的场景。 #### 五、二维线段树 **二维线段树**是线段树的一种扩展形式，用于处理二维空间中的区间查询问题。 **构建思路**： 1. **构建第一个维度**：首先按照第一维构建一棵线段树。 2. **嵌套第二维度**：在每个节点中再构建一棵线段树，用于处理第二维的区间。 **应用场景**：二维线段树适用于需要在二维空间中处理区间查询的问题，例如查询矩形区域内的某些统计信息。 #### 六、线段树与树状数组的应用实例 **示例**：考虑一个包含 `n` 个元素的数组，需要支持以下两种操作： 1. 修改数组中某一点的值。 2. 查询数组中某个区间 `[i, j]` 的和。 **解决方案**： - 使用线段树或树状数组均可解决此问题。 - **线段树实现**：构建线段树，每个节点存储该区间的和。 - **树状数组实现**：构建树状数组，支持单点更新和前缀和查询。 **总结**：线段树和树状数组都是处理区间查询问题的强大工具。线段树更加灵活，可以处理更复杂的区间操作；而树状数组则更节省空间，在单点更新和前缀和查询方面更为高效。选择合适的数据结构取决于具体问题的需求。