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

Question

考虑一系列n个正实数,(a _i)及其部分和序列(s _i).给定一个号码X  ε(0,  s ^ _Ñ ],我们必须找到我使得š _{我 -1}  <  X  ≤  小号_我.此外,我们希望能够改变的一个一个_我的,而不必更新所有的部分款项.两者都可以在O(日志做ñ)时使用二叉树的一个_我作为叶节点值,并且非叶节点的值是各个子节点的值的总和.如果n已知并且已修复,则树不必是自平衡的,并且可以有效地存储在线性阵列中.此外,如果n是2的幂,则只需要2  n  -1个数组元素.参见Blue等,Phys.Rev. E  51(1995),pp.R867-R868申请.鉴于问题的通用性和解决方案的简单性,我想知道这个数据结构是否具有特定的名称以及是否存在现有的实现(最好是在C++中).我自己已经实现了它,但是从头开始编写数据结构似乎总是让我重新发明轮子 - 如果以前没有人做过,我会感到惊讶.

Answer 1

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

Answer 2

芬威克树（又名二叉索引树）是一种维护元素序列的数据结构，能够在 O(logn) 时间内计算任意范围的连续元素的累积和。更改任何单个元素的值也需要 O(logn) 时间。