15

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

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

现在，标准解决方案是使用分段树，并在此处进行了描述。另一种用于解决范围查询的数据结构是二叉索引树（Fenwick Tree），它更容易理解和编码。

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

4

3 回答 3

8

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

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

简而言之，你需要维护

  • 表示节点 [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)
}
于 2016-01-05T00:26:36.310 回答
4

通常，可以针对任何可逆运算（例如加法、乘法）调整 Fenwick 树。

至少可以使用 Fenwick 树来回答形式为 0...x 的区间的查询（左点固定为 0）。这是在对位置 x 的更新操作仅降低存储值的假设下。

于 2014-04-23T11:31:13.387 回答
2

我想知道自己是否有同样的问题。但是，我认为芬威克树不可能执行最小/最大查询，这是因为它依赖于从 a 到 b 的累积频率是 f(b)-f(a-1) 的事实，并且属性对 min/max 函数无效

于 2014-01-18T02:12:59.587 回答