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
- an array representing the real values for nodes [1,N]
- a Fenwick tree with 0 as the root, where the parent of any node i is
i-(i&-i)
- a Fenwick tree with N+1 as the root, where the parent of any node i is
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)
}
