12. 段树（Segment Trees）
段树是一个完整的二叉树，可以有效地回答查询，同时仍然可以轻松修改其元素。
给定数组中索引 i 上的每个元素代表一个用[i, i]间隔标记的叶子。将其子节点分别标记为[x, y]或[y, z]的节点将具有[x, z]区间作为标签。因此，给定 n 个元素（0-indexed），线段树的根将被标记为[0, n-1]。
它们是做什么用的？
它们在可以使用分而治之（我们将要讨论的第一个算法概念）解决的任务中非常有用，并且还可能需要更新其元素。这样，在更新元素时，包含它的任何区间也会被修改，因此复杂度是对数的。例如，n 个给定元素的总和/最大值/最小值是线段树最常见的应用。如果元素更新正在发生，二分搜索也可以使用段树。
特性
作为二叉树，节点 x 将2x和2x+1作为子节点，[x/2]作为父节点，其中[x]是x的整数部分；
更新段树中整个范围的一种有效方法称为“延迟传播”，它也是在 O(log n) 中完成的（有关操作的实现，请参见下面的链接）；
它们可以是 k 维的：例如，有 q 个查询来查找一个矩阵的给定子矩阵的总和，我们可以使用二维线段树；
更新元素/范围需要 O(log n) 时间；对查询的回答是恒定的(O(1))；
空间复杂度是线性的，这是一个很大的优势：O(4*n)。
13. 树状数组（Fenwick Trees）
fenwick 树，也称为二叉索引树 (BIT)，是一种也用于高效更新和查询的数据结构。与 Segment Trees 相比，BITs 需要更少的空间并且更容易实现。
它们是做什么用的？
BIT 用于计算前缀和——第 i 个位置的元素的前缀和是从第一个位置到第 i 个元素的总和。它们使用数组表示，其中每个索引都以二进制系统表示。例如，索引 10 相当于十进制系统中的索引 2。
特性
树的构建是最有趣的部分：首先，数组应该是 1-indexed 要找到节点 x 的父节点，您应该将其索引 x 转换为二进制系统并翻转最右边的有效位；ex.节点 6 的父节点是 4；
6 = 1*2²+1*2¹+0*2⁰ => 1"1"0 (flip)
=> 100 = 1*2²+0*2¹+0*2⁰ = 4;
最后，ANDing 元素，每个节点都应该包含一个可以添加到前缀和的间隔；
更新的时间复杂度仍然是 O(log n)，查询的时间复杂度仍然是 O(1)，但空间复杂度与线段树的 O(4*n) 相比是一个更大的优势：O(n)。
14. 并查集（Disjoint Set Union）
我们有 n 个元素，每个元素代表一个单独的集合。并查集 (DSU) 允许我们做两个操作：
1.UNION — 组合任意两个集合（或者统一两个不同元素的集合，如果它们不是来自同一个集合）；
2.FIND — 查找元素来自的集合。
它们是做什么用的？
并查集（DSU） 在图论中非常重要。您可以检查两个顶点是否来自同一个连接组件，或者甚至可以统一两个连接组件。
让我们以城市和城镇为例。由于人口和经济增长的邻近城市正在扩张，它们可以轻松创建大都市。因此，两个城市合并在一起，他们的居民住在同一个大都市。我们还可以通过调用 FIND 函数来检查一个人居住在哪个城市。
特性
它们用树表示；一旦两组组合在一起，两个根中的一个成为主根，另一个根的父代是另一棵树的叶子之一；
一种实用的优化是通过高度压缩树木；这样，联合由最大的树组成，以轻松更新它们的两个数据（参见下面的实现）；
所有操作都在 O(1) 时间内完成。
15. 最小生成树（Minimum Spanning Trees）
给定一个连通图和无向图，该图的生成树是一个子图，它是一棵树并将所有节点连接在一起。单个图可以有许多不同的生成树。加权、连通和无向图的最小生成树 (MST) 是权重（成本）小于或等于其他所有生成树权重的生成树。生成树的权重是赋予生成树每条边的权重之和。
它们是做什么用的？
最小生成树（MST ）问题是一个优化问题，一个最小成本问题。有了路线网，我们可以认为影响n个城市之间建立国道的因素之一是相邻两个城市之间的最小距离。
国家路线就是这样，由道路网络图的 MST 表示。
特性
作为一棵树，具有 n 个顶点的图的 MST 具有 n-1 条边；可以使用以下方法解决：
Prim 算法 — 密集图的最佳选择（具有 n 个节点且边数接近n(n-1)/2)的图）；
Kruskal 算法——主要使用；它是一种基于不相交集联合的贪心算法（我们后面也将讨论它）；
构建它的时间复杂度对于 Kruskal 来说是 O(n log n) 或 O(n log m)（这取决于图），对于 Prim 来说是 O(n²)。
