间隔,段,芬威克树是否相同？

Question

今天我听了关于fenwick树(二进制索引树)的讲座,老师说这个树是区间树和分段树的概括,但我对这三个数据结构的实现是不同的.这个假设是真的吗？为什么？

Answer 1

以下分类似乎是明智的,尽管不同的人必然会混淆这些术语.

Fenwick树/二进制索引树 链接

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

范围树 链接

树的一族,每个节点代表一个给定范围的子范围,比如[0,N].用于计算间隔的关联操作.

区间树 链接

存储实际间隔的树.最常见的是你采取中点,在节点处保持交叉间隔,并重复该点的过程,以获得点的左侧和右侧.

段树 链接

类似于范围树,其中叶子是在可能连续的空间中的基本间隔而不是离散的,并且更高的节点是基本间隔的联合.用于检查点包含.

Answer 2

我从来没有听过二进制索引树称为任何东西的泛化.它肯定不是区间树和分段树的概括.我建议你按照链接来说服自己.

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

如果通过"这棵树"你的老师意味着"二元索引树",那么他就错了.

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

当然他们是不同的,你的老师从不说他们不应该.他只是说一个是另一个的概括(这不是真的,但仍然).无论哪种方式,实现都应该是不同的.

具有相同实现的是二进制索引树和fenwick树,因为这些是相同的.