存储部分和的二叉树：名称和现有实现
考虑一个由 n 个正实数组成的序列 (ai) 及其部分和序列 (si ）。给定一个数字x ∊ (0, sn]，我们必须找到i 使得 si−1 < x ≤ si 我们还希望能够更改 ai 之一，而不必更新所有部分总和。通过使用以 ai 作为叶节点值的二叉树，两者都可以在 O(log n) 时间内完成，并且非叶节点的值是各个子节点值的总和如果n已知且固定，则树不必是自平衡的并且可以有效地存储在。此外，如果 n 是 2 的幂，则仅需要 2 n − 1 个数组元素，请参阅 Blue 等人，Phys。 . Rev. 51 (1995)，第 R867–R868 页，考虑到问题的通用性和解决方案的简单性，我想知道这些数据是否有效。结构有一个特定的名称以及是否有现有的实现（最好是在 C++ 中）。我自己已经实现了它，但从头开始编写数据结构对我来说总是像是重新发明轮子——如果以前没有人这样做过，我会感到惊讶。
Consider a sequence of n positive real numbers, (ai), and its partial sum sequence, (si). Given a number x ∊ (0, sn], we have to find i such that si−1 < x ≤ si. Also we want to be able to change one of the ai’s without having to update all partial sums. Both can be done in O(log n) time by using a binary tree with the ai’s as leaf node values, and the values of the non-leaf nodes being the sum of the values of the respective children. If n is known and fixed, the tree doesn’t have to be self-balancing and can be stored efficiently in a linear array. Furthermore, if n is a power of two, only 2 n − 1 array elements are required. See Blue et al., Phys. Rev. E 51 (1995), pp. R867–R868 for an application. Given the genericity of the problem and the simplicity of the solution, I wonder whether this data structure has a specific name and whether there are existing implementations (preferably in C++). I’ve already implemented it myself, but writing data structures from scratch always seems like reinventing the wheel to me—I’d be surprised if nobody had done it before.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这在函数式编程中被称为手指树，但显然有命令式语言的实现。在文章中，有一个指向博客文章的链接，解释了用 C# 实现此数据结构可能对您有用。
This is known as a finger tree in functional programming but apparently there are implementations in imperative languages. In the articles there is a link to a blog post explaining an implementation of this data structure in C# which could be useful to you.
Fenwick 树（又名二元索引树）是一种维护元素序列的数据结构，并且能够在 O(logn) 时间内计算任意范围的连续元素的累积和。更改任何单个元素的值也需要 O(logn) 时间。
Fenwick tree (aka Binary indexed tree) is a data structure that maintains a sequence of elements, and is able to compute cumulative sum of any range of consecutive elements in O(logn) time. Changing value of any single element needs O(logn) time as well.