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?

Answer 1

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.

Answer 2

From a level above the bit fiddling, this is what we have:

A normal BIT array g for integer data array a stores range sums.

g[k] = sum{ i = D(k) + 1 .. k } a[i]

where D(k) is just k with the lowest-order 1 bit set to 0. Here we have instead

T[k] = min{ i = D(k) + 1 .. k } a[i]

The query works exactly like a normal BIT range sum query with the change that minima of subranges are taken as the query proceeds rather than sums. For N items in a, there are ceiling(log N) bits in N, which determines the run time.

The update takes more work because O(log N) subrange minima - i.e. elements of g - are affected by the change, and each takes an O(log N) query by itself to resolve. This makes the update O(log^2 n) overall.

At the bit fiddling level this is fiendishly clever code. The statement x += x & -x clears the lowest-order consecutive string of 1's in x and then sets the next highest-order zero to 1. This is just what you need to "traverse" the BIT for the original integer x.