algorithm - 区间树、段树、芬威克树是否相同？

Question

今天我听了一个关于 fenwick 树（二叉索引树）的讲座，老师说这棵树是区间树和段树的概括，但是我对这三种数据结构的实现是不同的。这个肯定是真的吗？为什么？

Answer 1

以下分类似乎是明智的，尽管不同的人必然会将这些术语混为一谈。

Fenwick 树/二进制索引树 链接

您使用单个数组和二进制表示上的操作来存储前缀和（也称为累积和）的一种。元素可以是幺半群的成员。

范围树 链接

树族，其中每个节点表示给定范围的子范围，例如 [0, N]。用于计算区间上的关联操作。

区间树 链接

存储实际间隔的树。最常见的做法是取一个中点，在节点处保持相交区间，然后对点的左侧和右侧的区间重复该过程。

段树 链接

类似于范围树，其中叶子是可能连续空间中的基本间隔，而不是离散的，更高的节点是基本间隔的并集。用于检查是否包含点。

Answer 2

我从未听说过称为任何事物的泛化的二叉索引树。这当然不是区间树和线段树的概括。我建议您按照链接说服自己相信这一点。

比这棵树是区间树和段树的概括

如果您的老师所说的“这棵树”是指“二叉索引树”，那么他就错了。

但是我对这三种数据结构的实现是不同的

当然他们是不同的，你的老师从来没有说过他们不应该这样。他只是说一个是另一个的概括（这不是真的，但仍然如此）。无论哪种方式，实现都应该是不同的。

具有相同实现的是二叉索引树和芬威克树，因为它们是相同的。