19

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.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Ankesh Anand
  • 1,695
  • 2
  • 16
  • 24
  • 8
    @Kaustav I did try it myself, I wasn't able to come up with a solution. And that's why I posted it here. I believe my question is clear and shows research effort. Your down-vote was harsh. – Ankesh Anand Dec 31 '13 at 15:36
  • I think that just naming the algorithm and asking for the implementation does not show much research effort. You should have posted what you tried(codes). – Kaustav Ray Dec 31 '13 at 15:46
  • Doesn't this show I read and implemented BITs and already have a segment tree approach for solving the problem? Does research effort only mean code snippets for you? You are not being constructive my friend. – Ankesh Anand Dec 31 '13 at 16:21
  • 1
    Again, Your EXACT question: Can the above mentioned problem be solved by using BIT. If yes, how can BIT be implemented to solve the problem? Do you consider this research effort ? You are giving the topcoder link of the segment tree. Is that a research effort ? If you consider posting the links of the algorithm, a research effort, and expecting implementation ! Then I am sorry ! – Kaustav Ray Dec 31 '13 at 17:33

3 Answers3

10

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)
}
Atte Juvonen
  • 4,922
  • 7
  • 46
  • 89
  • Links to external resources are encouraged, but please add context around the link so your fellow users will have some idea what it is and why it’s there. Always quote the most relevant part of an important link, in case the target site is unreachable or goes permanently offline. – davejal Jan 05 '16 at 00:46
  • Doesn’t this get rid of the main advantage of Fenwick trees which is that you don’t need any additional memory? If you have to have a separate equal sized array why not just use a heap? – Joseph Garvin Jul 19 '21 at 21:26
  • 2
    @JosephGarvin What do you mean by "heap"? Do you mean Segment Tree? – Atte Juvonen Jul 20 '21 at 07:31
4

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.

Filip Pavetić
  • 41
  • 3
3

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

alei
  • 66
  • 3