使用二叉索引树(Fenwick树)求解范围最小查询

Question

正式地,范围最小查询问题是:

给定一个数组A [0,N-1],找到任意两个给定索引之间具有最小值的元素的位置.

现在,标准解决方案是使用分段树,这里已经描述过了.用于解决范围查询的另一个数据结构是二进制索引树(Fenwick树),它更容易理解和编码.

可以通过二叉索引树来解决范围最小查询问题,以及如何解决？将理解更新和查询功能的实现.

Answer 1

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

如何使Fenwick树适应范围最小的查询

简而言之,您需要维护

• 表示节点[1,N]的实际值的数组
• 一个Fenwick树,其中0为根,其中任何节点的父节点为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)
}