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)

 0 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 16●2●2●6 accept rate: 0%

 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. answered 27 Dec '13, 18:46 4★isego1 1●2 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) 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★
 0 can we not do min(query[2],query[0])? answered 25 Sep '15, 16:17 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★
 0 can we not do min(query[2],query[0])? answered 25 Sep '15, 16:18 3★rashi007 -1 accept rate: 0%
 0 can we not do min(query[2],query[0])? answered 25 Sep '15, 16:19 3★rashi007 -1 accept rate: 0%
 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 answered 11 Dec '15, 18:34 0★safecomp 1 accept rate: 0%
 toggle preview community wiki:
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,768
×1,664
×711
×146

question asked: 27 Dec '13, 12:29

question was seen: 11,513 times

last updated: 11 Dec '15, 13:04