今天听了一个关于fenwick树(二叉索引树)的讲座，老师说这棵树是区间树和线段树的推广，但是我对这三种数据结构的实现是不同的。 这个确认是真的吗？为什么？
最佳答案
尽管不同的人必然会混淆这些术语，但以下分类似乎是合理的。
芬威克树/二叉索引树 link
您使用单个数组和二进制表示形式的操作来存储前缀和(也称为累积和)。元素可以是幺半群的成员。
范围树 link
树族，其中每个节点代表给定范围的一个子范围，比如 [0, N]。用于计算区间的关联运算。
区间树 link
存储实际间隔的树。最常见的是，您取一个中点，在节点处保持相交间隔，并在点的左侧和右侧的间隔重复该过程。
线段树 link
类似于范围树，其中叶子是可能连续空间中的基本区间而不是离散空间，更高的节点是基本区间的并集。用于检查是否包含点。
关于algorithm - 间隔树、段树、芬威克树是否相同？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2795989/