使用二叉索引树（Fenwick Trees）解决区间最小值查询问题

Question

使用二叉索引树（Fenwick Trees）解决区间最小值查询问题

algorithmdata-structurestreefenwick-treermq

20

形式上，区间最小值查询问题是:

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

现在，标准解决方案是使用线段树，并已在这里中描述。另一个用于解决范围查询的数据结构是二进制索引树（Fenwick Tree），它更容易理解和编码。

区间最小查询问题是否可以通过使用二进制索引树来解决？如何实现更新和查询函数？

- Ankesh Anand

8

我尝试了一下，但没能想出解决方案。所以我才在这里发帖。我相信我的问题很清楚，并展示了研究的努力。你的反对票有些严厉。 - Ankesh Anand

我认为仅仅命名算法并要求实现并不能展示出多少研究努力。你应该发布你尝试过的内容（代码）。 - Kaustav Ray

这难道不表明我已经阅读并实现了位运算，并且已经有了解决问题的线段树方法吗？对你来说，研究工作只意味着代码片段吗？我的朋友，你没有建设性。 - Ankesh Anand

1

请再次明确您的问题：是否可以使用BIT解决上述问题？如果可以，如何实现BIT以解决该问题？您认为这是研究工作吗？您提供了segment tree的topcoder链接。那是一项研究工作吗？如果您认为发布算法链接是一项研究工作，并期望进行实现！那我很抱歉！ - Kaustav Ray

3个回答

4

通常情况下，可以对Fenwick树进行调整以适用于任何可逆操作（例如加法、乘法等）。

对于最小值，可以使用Fenwick树来回答形式为0...x的区间查询（左端点固定为0）。这是在假设仅将位置x的更新操作降低存储的值的情况下进行的。

- Filip Pavetić

3

我自己也在思考同样的问题。然而，我认为树状数组无法执行最小/最大查询，因为它依赖于从a到b的累积频率是f(b)-f(a-1)这一事实，而该属性对于min/max函数是无效的。

- alei

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Atte Juvonen · Accepted Answer

尽管有其他答案，但可以使用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)
}