Using binary indexed trees for a RMQ extension

Question

The RMQ problem can be extended like so:

Given is an array of n integers A.

query(x, y): given two integers 1 ≤ x, y ≤ n, find the minimum of A[x], A[x+1], ... A[y];

update(x, v): given an integer v and 1 ≤ x ≤ n do A[x] = v.

This problem can be solved in O(log n) for both operations using segment trees.

This is an efficient solution on paper, but in practice, segment trees involve a lot of overhead, especially if implemented recursively.

I know for a fact that there is a way to solve the problem in O(log^2 n) for one (or both, I'm not sure) of the operations, using binary indexed trees (more resources can be found, but this and this are, IMO, the most concise and exhaustive, respectively). This solution, for values of n that fit into memory, is faster in practice, because BITs have a lot less overhead.

However, I do not know how the BIT structure is used to perform the given operations. I only know how to use it to query an interval sum for example. How can I use it to find the minimum?

If it helps, I have code that others have written that does what I am asking for, but I cannot make sense of it. Here is one such piece of code:

int que( int l, int r ) {
    int p, q, m = 0;

    for( p=r-(r&-r); l<=r; r=p, p-=p&-p ) {
        q = ( p+1 >= l ) ? T[r] : (p=r-1) + 1;
        if( a[m] < a[q] )
            m = q;
    }

    return m;
}

void upd( int x ) {
    int y, z;
    for( y = x; x <= N; x += x & -x )
        if( T[x] == y ) {
            z = que( x-(x&-x) + 1, x-1 );
            T[x] = (a[z] > a[x]) ? z : x;
        }
        else
            if( a[ T[x] ] < a[ y ] )
                T[x] = y;
}

In the above code, T is initialized with 0, a is the given array, N its size (they do indexing from 1 for whatever reason) and upd is called at first for every read value. Before upd is called a[x] = v is executed.

Also, p & -p is the same as the p ^ (p & (p - 1)) in some BIT sources and indexing starts from 1 with the zero element initialized to infinity.

Can anyone explain how the above works or how I could solve the given problem with a BIT?

for( y = x; x <= N; x += x & -x ) this is deep. BTW what is T[] ? BTW2: I'm not sure if this should be for( y = x; x < N; x += x & -x ) BTW3: what is N ? — wildplasser
@wildplasser - that first for is actually quite standard for a BIT. T seems to be where the BIT information is actually held. As for N, that is n in my problem statement, I will edit that in. — IVlad

mcdowella mcdowella · Accepted Answer · 2013-06-18T04:28:59

I haven't looked at the code in detail, but it seems to be roughly consistent with the following scheme:

1) Keep the structure of the BIT, that is, impose a tree structure based on powers of two on the array.

2) At each node of the tree, keep the minimum value found at any descendant of that node.

3) Given an arbitrary range, put pointers at the start and end of the range and move them both upwards until they meet. If you move a pointer upwards and towards the other pointer then you have just entered a node in which every descendant is a member of the range, so take note of that value at that node. If you move a pointer upwards and away from the other pointer the node you have just joined records a minimum derived from values including those outside the range, and you have already taken note of every relevant value below that node inside the range, so ignore the value at that node.

4) Once the two pointers are the same pointer, the minimum in the range is the minimum value in any node that you have taken note of.

Using binary indexed trees for a RMQ extension

3 Answers