You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

asked 27 Dec '13, 12:29

ankesh_iitkgp's gravatar image

4★ankesh_iitkgp
16226
accept rate: 0%


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.

link

answered 27 Dec '13, 18:46

isego1's gravatar image

4★isego1
12
accept rate: 0%

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?

(27 Dec '13, 19:45) ankesh_iitkgp4★

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.

(27 Dec '13, 20:20) isego14★

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

link

answered 25 Sep '15, 16:17

rashi007's gravatar image

3★rashi007
-1
accept rate: 0%

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.

(25 Sep '15, 17:10) xellos07★

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

link

answered 25 Sep '15, 16:18

rashi007's gravatar image

3★rashi007
-1
accept rate: 0%

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

link

answered 25 Sep '15, 16:19

rashi007's gravatar image

3★rashi007
-1
accept rate: 0%

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

http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf

link

answered 11 Dec '15, 18:34

safecomp's gravatar image

0★safecomp
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,420
×1,188
×471
×139

question asked: 27 Dec '13, 12:29

question was seen: 9,127 times

last updated: 11 Dec '15, 13:04