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.
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.
A Fenwick tree, also called a binary indexed tree (BIT), is a data structure that can efficiently update elements and calculate range sums on a list of numbers. This tutorial will show how to construct a Fenwick tree to solve a mutable range sum query problem.
Range Update and Point Query Suppose that we want to increment the interval by . We make two point update operations on Fenwick tree which are add(l, x) and add(r+1, -x) . If we want to get the value of , we just need to take the prefix sum using the ordinary range sum method.
A Fenwick tree or binary indexed tree is a data structure that helps compute prefix sums efficiently. Computing prefix sums are often important in various other algorithms, not to mention several competitive programming problems. For example, they are used to implement the arithmetic coding algorithm.
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
i-(i&-i)
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)
}
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With