Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 672
Ankesh Anand Avatar asked Dec 27 '13 12:12

Ankesh Anand


People also ask

Can Fenwick solve range minimum?

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.

Is binary indexed tree and Fenwick tree same?

A Fenwick tree, also called a binary indexed tree (BIT), is a data structure that can efficiently update elements and calculate range sums on a list of numbers. This tutorial will show how to construct a Fenwick tree to solve a mutable range sum query problem.

How do you update the range on a Fenwick tree?

Range Update and Point Query Suppose that we want to increment the interval by . We make two point update operations on Fenwick tree which are add(l, x) and add(r+1, -x) . If we want to get the value of , we just need to take the prefix sum using the ordinary range sum method.

What are Fenwick trees used for?

A Fenwick tree or binary indexed tree is a data structure that helps compute prefix sums efficiently. Computing prefix sums are often important in various other algorithms, not to mention several competitive programming problems. For example, they are used to implement the arithmetic coding algorithm.


2 Answers

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)
}
like image 76
Atte Juvonen Avatar answered Sep 28 '22 13:09

Atte Juvonen


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.

like image 38
Filip Pavetić Avatar answered Sep 28 '22 14:09

Filip Pavetić