algorithmdata-structurestreefenwick-treermq

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


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.


Solution

  • 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

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