Solving minimum range queries using binary indexed trees (Fenwick trees)

Question

Formally, the problem of the minimum query range:

For a given 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 the 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 minimum search range problem be solved with Binary-Indexed-Trees and how? Implementation of the update and query function is welcome.

Answer 1

Despite other answers, you can use Fenwick trees for minimal range queries for any range. I posted a detailed explanation here:

How to adapt the Fenwick tree to meet the minimum range requirements

In short, you need to maintain

• array representing real values ​​for nodes [1, N]
• Fenwick tree with root 0, where the parent of any node i is i-(i&-i)
• 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. Single tree update:

 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) } 

Answer 2

Typically, you can configure the Fenwick tree for any reversible operation (for example, addition, multiplication).

For a minimum, you can use the Fenwick tree to answer queries for intervals of the form 0 ... x (the left point is fixed at 0). This is done under the assumption that the update operation to position x only reduces the stored value.

Answer 3

I was wondering about the same problem. However, I think it is not possible for the fenwick tree to execute minimum / maximum requests, that is, because it depends on the fact that the acummulative frequency from a to b is f (b) -f (a-1), and that the property is not valid for min / max functions