22

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

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

这两项操作都O(log(n))及时完成，我理解逻辑和实现。实现一堆其他操作并不难，比如从 N 到 M 求和。

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

在寻找解决方案后，大多数人认为这是不可能的，少数人声称它实际上可以完成（方法1 、方法 2）。

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

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

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

如果可能的话，我很高兴听到它是如何工作的。

4

2 回答 2

25

是的，您可以将 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

我们挥动一根魔杖，出现以下树：

问题示例的 Fenwick 树

请注意，在两棵树中，每个节点都代表该子树中所有节点的最小值。例如，在 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（代表 4,5,6,7）、BIT1_14（代表 13,14）、BIT1_12（代表 9,10,11， 12) 和 REAL_8，因此涵盖了所有可能的值 [4,14]。

更新

由于一个节点代表它自己及其子节点的最小值，因此更改节点会影响其父节点，但不会影响其子节点。因此，要更新一棵树，我们从我们正在修改的节点开始，一直向上移动到虚构的根节点（0 或 N+1 取决于哪棵树）。

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

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

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

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

用于更新树中值为 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 实现的两倍，并且更新速度略快。这样做的主要原因是使用超高效的按位运算在节点之间移动。他们在这里得到了很好的解释。段树的代码真的很简单，所以想想性能优势真的值得吗？我的Fenwick RMQ的更新方法是40行，调试了一段时间。如果有人想要我的代码，我可以把它放在 github 上。我还制作了一个蛮力和测试生成器，以确保一切正常。

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

于 2016-01-05T00:20:11.707 回答
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
于 2015-06-29T02:41:26.567 回答