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

Question

考虑一个由n 个正实数组成的序列 ( a _i ) 及其部分和序列 ( s _i )。给定一个数x  ∊ (0,  s _n ]，我们必须找到i使得s _{i −1}  <  x  ≤ <em>s _i。此外，我们希望能够更改其中一个a _i，而不必更新所有部分和。两者都可以通过使用带有a _i的二叉树在 O(log n ) 时间内完成's 作为叶节点值，非叶节点的值是各个子节点值的总和。如果n已知且固定，则树不必是自平衡的，并且可以有效地存储在线性数组中。此外，如果n是 2 的幂，则只需要 2 <em>n - 1 个数组元素。参见 Blue 等人，Phys。Rev. E  51 (1995), pp. R867–R868 申请。鉴于问题的通用性和解决方案的简单性，我想知道这个数据结构是否有特定的名称以及是否有现有的实现（最好是 C++）。我自己已经实现了它，但是从头开始编写数据结构对我来说似乎总是在重新发明轮子——如果以前没有人做过，我会感到惊讶。

Answer 1

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

Answer 2

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