1

我有一个问题，我不知道我是否可以用 Fenwick 树解决它。这是问题所在：我有一个原始数组 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

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

4

1 回答 1

2

假设您知道数组离线，您可以排序以找到每个元素的排名，例如，[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

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

于 2021-02-01T17:50:11.233 回答