用 Fenwick 树计算子数组和

Question

我有一个问题，不知道能不能用分域树解决。这是问题所在：我有一个原始数组 a = [8,4,7,0]。现在我遍历数组，在每一步我都对排序后的子数组感兴趣，它们看起来像这样：[8]、[4,8]、[4,7,8]、[0,4,7, 8].在插入当前数字时迭代的每一步，我想知道所有大于我刚插入的数字的数字之和。所以对于上面的例子，它看起来像这样：

[8]; sum = 0 因为大于插入数字 (8) 的所有数字的总和为 0
[4,8]； sum = 8 因为大于插入数字 (4) 的所有数字的总和是 8
[4,7,8]; sum = 8 因为大于插入数字 (7) 的所有数字的总和是 8
[0,4,7,8]; sum = 19 因为大于插入数字 (0) 的所有数字的总和是 19

上面的例子只是为了说明，原始数组可以更大，因此有效地计算这样的和变得非常重要。关于如何有效解决这个问题有什么建议吗？

Answer 1

假设你离线知道数组，你可以排序找到每个元素的排名，例如，[8, 4, 7, 0] --> [(8, 3), (4, 1), (7, 2), (0, 0)]。然后用全零初始化Fenwick树，并处理一个元素，将Fenwick树对应于较高等级的后缀求和，然后在其等级处插入元素。芬威克树的进化是

[0, 0, 0, 0]
          --: sum = 0

[0, 0, 0, 8]
    --------: sum = 8

[0, 4, 0, 8]
       -----: sum = 8

[0, 4, 7, 8]
 -----------: sum = 19

如果您需要运行在线，那么我认为扩充平衡二叉搜索树是最简单的。

用 Fenwick 树计算子数组和

Calculating sub array sums with a Fenwick tree

sorting

data-structures

fenwick-tree

segment-tree

array-sum