Solving Range Minimum Queries using Binary Indexed Trees (Fenwick Trees)

Question

Formally, the Range Minimum Query Problem is:

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

Now, the standard solution is to use a segment tree and has been described here. Another data structure used to solve range queries is the Binary-Indexed Tree (Fenwick Tree), and it is much easier to understand and code.

Can the range minimum query problem be solved by Binary-Indexed-Trees, and how? An implementation of the update and query function would be appreciated.

Answer 1

Despite the other answers it is possible to use Fenwick trees for Range Minimum Queries for any range. I posted a detailed explanation here:

How to adapt Fenwick tree to answer range minimum queries

In short, you need to maintain

• an array representing the real values for nodes [1,N]
• a Fenwick tree with 0 as the root, where the parent of any node i is i-(i&-i)
• a Fenwick tree with N+1 as the root, where the parent of any node i is i+(i&-i)

To query any range in 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
}

To update any value in amortized O(log n) you need to update the real array and both trees. Updating a single tree:

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