存储部分和的二叉树：名称和现有实现

Consider a sequence of n positive real numbers, (a_i), and its partial sum sequence, (s_i). Given a number x ∊ (0, s_n], we have to find i such that s_i−1 < x ≤ s_i. Also we want to be able to change one of the a_i’s without having to update all partial sums. Both can be done in O(log n) time by using a binary tree with the a_i’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.

这被称为手指树 http://en.wikipedia.org/wiki/Finger_tree在函数式编程中，但显然有命令式语言的实现。文章中有一个链接博客文章 http://dnovatchev.spaces.live.com/blog/cns!44B0A32C2CCF7488!582.entry解释此数据结构在 C# 中的实现，这可能对您有用。