存储部分和的二进制树：名称和现有实现 [英] Binary tree that stores partial sums: Name and existing implementations

问题描述

考虑 n 正实数序列，（ i ）及其部分和序列（ sub> i ）。给定一个数字 x ε（0， s _n ]，我们必须找到 i 另外，我们希望能够更改其中一个 _i ，而无需更新所有部分和。两者都可以在O（log n ）时间通过使用具有 a _i 的二进制树作为叶节点值，并且非叶节点的值是值的总和如果 n 是已知和固定的，则树不必是自平衡的，并且可以有效地存储在线性阵列中。而且，如果 n >是两个的幂，只需要2个数组元素，参见Blue et al。，Phys.Rev.E 51 （1995），第R867页-R868为一个应用程序考虑到问题的一般性和解决方案的简单性，我想知道这个数据结构是否具有特定的名称以及是否存在（最好在C ++中）。我已经自己实现了，但是从头开始写数据结构总是看起来像是将轮转向我 - 如果没有人做过，我会感到惊讶。

解决方案

这在功能编程中被称为手指树，但显然在命令式语言中有实现。在文章中有一个指向博客文章的链接C＃中的这个数据结构的实现可能对你有用。

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.

解决方案

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.

这篇关于存储部分和的二进制树：名称和现有实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！