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

Answer 2

I was wondering myself about the same problem. However, I think that is not possible for a fenwick tree to perform minimum/maximum queries, that is because it relies on the fact that the acummulative frequency from a to b is f(b)-f(a-1), and that property is not valid for the min/max functions

Answer 3

Generally, it is possible to adjust Fenwick tree for any invertible operation (for example addition, multiplication).

For minimum it is possible to use the Fenwick tree to answer the queries for intervals of the form 0...x (the left point is fixed to 0). That is under the assumption that update operation to position x only lowers the stored value.