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

general
, , ,
1

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 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.

2

I’m pretty sure that can’t. BIT can solve this type of query: Find min/max element in interval [ 0, x ] where x = { 0, n - 1 }. But there are some restriction with this BIT.

3

If it can solve queries in [0,x], then it can also solve queries in any [a,x] which is essentially query[x]-query[a]. Can you be more clear?

4

No. You can’t do this. Here is an example:
Array = { 5, 3, 2 },
Look for minimum in interval: [ 1, 2 ].
query[ 2 ] = 2, query[ 0 ] = 5.
Now, you would do this 2 - 5, which is obviously wrong.

5

can we not do min(query[2],query[0])?

6

can we not do min(query[2],query[0])?

7

can we not do min(query[2],query[0])?

8

For Array = { 2, 3, 5 }, min(query[2],query[0]) = min(2,2) = 2, while the correct answer is 3. No, it won’t work.

9

actually it’s possible to do RMQ with BIT , the following paper describe the idea and i want to share it so it will be useful for everyone interested in this topic