区间树、线段树、二叉索引树和范围树有哪些区别？

Question

段树、区间树、二叉索引树和范围树在以下几个方面有何不同：

• 关键思想/定义
• 应用场景
• 性能/高维度顺序/空间消耗

请勿仅提供定义。

- Aditya

---

不是重复问题，那个问题是询问Fenwick树是否是区间树的泛化，而我的问题更具体且不同。 - Aditya

在https://dev59.com/xXE85IYBdhLWcg3wZymt 上还没有得到回答，那里的答案仅仅给出了定义。 - Aditya

为什么说这个问题太宽泛了？“X和Y之间有哪些不同之处？”这个问题非常清晰明确。这是一个非常好的问题。 - IVlad

目前没有任何地方提供一个好的答案。一个好的答案将会对社区非常有益。 - Aditya

除了 Fenwick 树以外，这些数据结构大多数都在这个PDF中有介绍："Interval, Segment, Range, and Priority Search Trees"（作者为李东岳）。或者你可以在这本书中的一个章节中找到相关内容： "Handbook of Data Structures and Applications"。 - Evgeny Kluev

Answer 1

所有这些数据结构都用于解决不同的问题：

• 线段树（Segment Tree） 用于存储区间，并且针对“给定点包含在哪些区间内”的查询进行优化。
• 区间树（Interval Tree） 也用于存储区间，但是针对“哪些区间与给定区间重叠”的查询进行优化。它还可以用于点查询 - 类似于线段树。
• 范围树（Range Tree） 用于存储点，并且针对“哪些点落在给定区间内”的查询进行优化。
• 二进制索引树（Binary Indexed Tree） 用于存储每个索引处的项数，并针对“索引m和n之间有多少项”这一查询进行优化。

一个维度的性能/空间消耗：

• 线段树（Segment Tree） - O(n logn) 预处理时间，O(k+logn) 查询时间，O(n logn) 空间
• 区间树（Interval Tree） - O(n logn) 预处理时间，O(k+logn) 查询时间，O(n) 空间
• 范围树（Range Tree） - O(n logn) 预处理时间，O(k+logn) 查询时间，O(n) 空间
• 二进制索引树（Binary Indexed tree） - O(n logn) 预处理时间，O(logn) 查询时间，O(n) 空间

（k是报告结果的数量）

所有数据结构都可以动态变化，即使用场景包括数据更改和查询：

• 线段树（Segment Tree） - 区间可以在O(logn) 时间内添加/删除（见这里）
• 区间树（Interval Tree） - 区间可以在O(logn) 时间内添加/删除

范围树 - 新增/删除点的时间复杂度为O(logn)（详见这里）

树状数组 - 每个索引项的计数可以在O(logn)时间内增加

高维空间（d>1）：

• 线段树 - 预处理时间复杂度为O(n(logn)^d)，查询时间复杂度为O(k+(logn)^d)，空间复杂度为O(n(logn)^(d-1))
• 区间树 - 预处理时间复杂度为O(n logn)，查询时间复杂度为O(k+(logn)^d)，空间复杂度为O(n logn)
• 范围树 - 预处理时间复杂度为O(n(logn)^d)，查询时间复杂度为O(k+(logn)^d)，空间复杂度为O(n(logn)^(d-1)))
• 树状数组 - 预处理时间复杂度为O(n(logn)^d)，查询时间复杂度为O((logn)^d)，空间复杂度为O(n(logn)^d)

- Lior Kogan

---

我很清楚地感受到线段树 < 区间树。有没有任何理由更喜欢线段树？例如实现的简易性？ - j_random_hacker

基于线段树的算法在某些更复杂的高维间隔查询变体中具有优势。例如，查找哪些非坐标轴平行线段与2D窗口相交。 - Lior Kogan

谢谢，我很感兴趣听你进一步解释一下。 - j_random_hacker

@j_random_hacker，线段树还有另一个有趣的用途：在O（log N）时间内进行区间最小值查询（range minimum queries），其中N是整个区间的大小。 - ars-longa-vita-brevis

为什么线段树的空间复杂度是O(n log n)？它们存储了N个叶子节点加上N / 2 + N/4 + ... + N/2^(log N)个非叶子节点，而这个总和如果我没记错的话是O(N)。另外，@icc97的答案也报告了O(N)的空间复杂度。 - Ant

Answer 2

虽然我没有比Lior的回答更多的补充，但它似乎需要一个好的表格。

一维

k是报告结果的数量

操作	区间（Segment）	区间长度（Interval）	范围（Range）	索引（Indexed）
预处理	n logn	n logn	n logn	n logn
查询	k+logn	k+logn	k+logn	logn
空间	n logn	n	n	n
插入/删除	logn	logn	logn	logn

高维

d > 1

操作	区间（Segment）	区间长度（Interval）	范围	索引
预处理	n(logn)^d	n logn	n(logn)^d	n(logn)^d
查询	k+(logn)^d	k+(logn)^d	k+(logn)^d	(logn)^d
空间	n(logn)^(d-1)	n logn	n(logn)^(d-1))	n(logn)^d

这个表格展示了一个数据结构的性能指标，涉及到预处理、查询和空间。其中，预处理需要 n(logn)^d 的时间，查询需要 k+(logn)^d 的时间，并使用 (logn)^d 的空间。在所有方案中，使用最多的空间是 n(logn)^d 。

- icc97

---

报告的结果是什么意思？ - Pratik Singhal

@ps06756 搜索算法通常具有log(n)的运行时间，其中n是输入大小，但可以产生与n成线性关系的结果，这在对数时间内无法完成（在log(n)时间内输出n个数字是不可能的）。 - oerpli

线段树在第一张表中不应该有O(n logn)的空间吗？ - Danny_ds

@Danny_ds - 谢谢，当你评论时我修复了那个错误。 - icc97

Answer 3

预处理的边界和段树、树状数组的空间可以得到改进：


如果你放弃在任意点添加区间，那么段树可以使用动态规划在2n=O(n)的时间内存储在2n的空间中并随后构建：https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-6
树状数组可以在n的时间内构建，参见这个答案：Is it possible to build a Fenwick tree in O(n)?
树状数组还支持在O(log(n))的时间内将元素附加到末尾

- Asad-ullah Khan