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

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.

can we not do min(query,query)?

can we not do min(query,query)?

can we not do min(query,query)?

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

1 Like

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?

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.

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

1 Like