algorithm - 使用二进制索引树(Fenwick 树)解决范围最小查询

Question

形式上，范围最小查询问题是:

Given an array A[0, N-1] , Find the position of the element with the minimum value between any two given indices.

现在，标准的解决方案是使用线段树并且已被描述here .另一种用于解决范围查询的数据结构是二叉索引树(Fenwick Tree)，它更容易理解和编码。

Binary-Indexed-Trees 能否解决范围最小查询问题，如何解决？更新和查询功能的实现将不胜感激。

Answer 1

尽管有其他答案，但可以将 Fenwick 树用于任何范围的范围最小查询。我在这里发布了详细的解释:

How to adapt Fenwick tree to answer range minimum queries

简而言之，你需要保持

• 代表节点 [1,N] 的实际值的数组
• 以 0 为根的 Fenwick 树，其中任何节点 i 的父节点是 i-(i&-i)
• 以 N+1 为根的 Fenwick 树，其中任何节点 i 的父节点是 i+(i&-i)

在O(log n)中查询任意范围

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])
  return val
}

要更新分摊 O(log n) 中的任何值，您需要更新实际数组和两棵树。更新单个树:

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)
}