如何调整 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)。

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

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

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

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

Answer 1

Fenwick 树结构适用于加法，因为加法是可逆的。它不适用于最小值，因为一旦你有一个单元格应该是两个或更多输入的最小值，你就可能丢失了信息。

如果您愿意将存储需求增加一倍，您可以使用隐式构建的线段树（如二叉堆）来支持 RMQ。对于具有 n 个值的 RMQ，将 n 个值存储在数组的 [n, 2n) 位置。位置 [1, n) 是聚合，公式为 A(k) = min(A(2k), A(2k+1))。位置 2n 是一个无限哨兵。更新例程应如下所示。

def update(n, a, i, x):  # value[i] = x
    i += n
    a[i] = x
    # update the aggregates
    while i > 1:
        i //= 2
        a[i] = min(a[2*i], a[2*i+1])

这里的乘法和除法可以用移位来代替以提高效率

RMQ伪代码更精致。这是另一个未经测试和优化的例程。

def rmq(n, a, i, j):  # min(value[i:j])
    i += n
    j += n
    x = inf
    while i < j:
        if i%2 == 0:
            i //= 2
        else:
            x = min(x, a[i])
            i = i//2 + 1
        if j%2 == 0:
            j //= 2
        else:
            x = min(x, a[j-1])
            j //= 2
    return x

Answer 2

是的，您可以将 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] 的查询将 return 值的最小值 BIT2_4（代表 4,5,6,7），BIT1_14（代表 13,14 ), BIT1_12 (rep. 9,10,11,12) 和 REAL_8，因此涵盖了所有可能的值 [4,14].

更新

由于一个节点代表了它自己和它的子节点的最小值，改变一个节点会影响它的父节点，而不是它的子节点。因此，要更新一棵树，我们从我们正在修改的节点开始，一直向上移动到虚构的根节点（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 年的论文。

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

How to adapt Fenwick tree to answer range minimum queries

algorithm

data-structures

fenwick-tree

rmq

查询

更新

二进制索引