algorithm - 如何调整 Fenwick 树以回答范围最小查询

Question

Fenwick tree是一种数据结构，可以有效地回答主要查询:

• 将元素添加到数组的特定索引 update(index, value)
• 求1到N的元素之和 find(n)

这两个操作都在 O(log(n)) 时间内完成，我理解 logic and implementation .实现一堆其他操作并不难，例如从 N 到 M 求和。

我想了解如何为 RMQ 调整 Fenwick 树。很明显，前两个操作改变了 Fenwick 树。但我无法弄清楚如何在 N 到 M 的范围内找到最小值。

在搜索解决方案后，大多数人认为这是不可能的，少数人声称实际上可以做到(approach1，approach2)。

第一种方法(用俄语编写，基于我的谷歌翻译有 0 个解释，只有两个函数)依赖于三个数组(初始、左和右)，在我的测试中，所有可能的测试用例都不能正常工作。

第二种方法只需要一个数组，并且根据声明在 O(log^2(n)) 中运行，并且几乎没有解释为什么以及如何工作。我没有尝试测试它。

---

鉴于有争议的说法，我想知道是否可以增加 Fenwick 树来回答 update(index, value) 和 findMin(from, to).

如果可能的话，我很乐意听听它是如何工作的。

Answer 1

是的，您可以将 Fenwick 树(二叉索引树)改编为

• 在 O(log n) 中更新给定索引处的值
• 查询 O(log n) 范围内的最小值(摊销)

我们需要 2 棵 Fenwick 树和一个额外的数组来保存节点的实际值。

假设我们有以下数组:

index 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
value 1  0  2  1  1  3  0  4  2  5  2  2  3  1  0

我们挥动魔杖，就会出现以下树木:

请注意，在两棵树中，每个节点代表该子树中所有节点的最小值。例如，在BIT2中，节点12的值为0，这是节点12、13、14、15的最小值。

查询

我们可以通过计算多个子树值和一个附加实节点值的最小值来高效地查询任何范围的最小值。例如，范围 [2,7] 的最小值可以通过取 BIT2_Node2(代表节点 2,3)和 BIT1_Node7(代表节点 7)、BIT1_Node6(代表节点 5,6)和 REAL_4 的最小值来确定 - 因此覆盖 [2,7] 中的所有节点。但是我们怎么知道我们想要查看哪些子树呢？

Query(int a, int b) {
  int val = infinity // always holds the known min value for our range

  // Start traversing the first tree, BIT1, from the beginning of range, a
  int i = a
  while (parentOf(i, BIT1) <= b) {
    val = min(val, BIT2[i]) // Note: traversing BIT1, yet looking up values in BIT2
    i = parentOf(i, BIT1)
  }

  // Start traversing the second tree, BIT2, from the end of range, b
  i = b
  while (parentOf(i, BIT2) >= a) {
    val = min(val, BIT1[i]) // Note: traversing BIT2, yet looking up values in BIT1
    i = parentOf(i, BIT2)
  }

  val = min(val, REAL[i]) // Explained below
  return val
}

从数学上可以证明，两次遍历都将在同一个节点结束。该节点是我们范围的一部分，但它不是我们查看过的任何子树的一部分。想象一下我们范围的(唯一)最小值在那个特殊节点中的情况。如果我们不查找它，我们的算法将给出不正确的结果。这就是为什么我们必须对实际值数组进行一次查找。

为了帮助理解算法，我建议您用笔和纸模拟它，在上面的示例树中查找数据。例如，范围 [4,14] 的查询将返回 BIT2_4 (rep. 4,5,6,7)、BIT1_14 (rep. 13,14)、BIT1_12 (rep. 9,10,11, 12) 和 REAL_8，因此涵盖了所有可能的值 [4,14]。

更新

由于一个节点代表它自己和它的 child 的最小值，改变一个节点会影响它的 parent ，但不会影响它的 child 。因此，要更新一棵树，我们从我们正在修改的节点开始，一直向上移动到虚构的根节点(0 或 N+1，具体取决于哪棵树)。

假设我们正在更新某棵树中的某个节点:

• 如果新值 < 旧值，我们将始终覆盖该值并向上移动
• 如果新值 == 旧值，我们可以停止，因为不会有更多向上级联的变化

• 如果新值 > 旧值，事情就会变得有趣。

  • 如果旧值仍然存在于该子树的某处，我们就完成了
  • 如果不是，我们要找到real[node]和每个tree[child_of_node]之间新的最小值，改变tree[node]并向上移动

更新 a 树中值为 v 的节点的伪代码:

while (node <= n+1) {
  if (v > tree[node]) {
    if (oldValue == tree[node]) {
      v = min(v, real[node])
      for-each child {
        v = min(v, tree[child])
      }
    } else break
  }
  if (v == tree[node]) break
  tree[node] = v
  node = parentOf(node, tree)
}

请注意，oldValue 是我们替换的原始值，而 v 在我们向上移动树时可能会被重新分配多次。

二进制索引

在我的实验中，Range Minimum Queries 的速度大约是 Segment Tree 实现的两倍，更新速度略快。这样做的主要原因是使用超高效的按位运算在节点之间移动。他们解释得很好here .线段树的代码非常简单，所以想想性能优势真的值得吗？我的 Fenwick RMQ 的更新方法是 40 行，调试了一段时间。如果有人想要我的代码，我可以把它放在 github 上。我还制作了一个暴力测试生成器，以确保一切正常。

芬兰算法社区帮助我理解了这个主题并实现了它。图片来源为http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf ，但他们将其归功于 Fenwick 1994 年的论文。