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

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.

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