该RMQ问题可以扩展如下所示：

给定的是一个n整数数组A。

query（x，y）： 给出两个整数1≤ x，y≤ n，找到的最小值A[x], A[x+1], ... A[y]；

更新（X，V）： 给定的整数v和1≤ x≤ n做A[x] = v。

O(log n)使用段树在两种操作中都可以解决此问题。

这在纸上是一种有效的解决方案，但是在实践中，段树会涉及很多开销，尤其是如果以递归方式实现的话。

我知道一个事实，那就是解决这个问题的方式O(log^2 n)为一个（或两个，我不知道）的操作，使用二进制索引树（更多的资源可以被发现，但这个和这个是，国际海事组织，最简洁，最详尽）。对于n这种适合内存的值的解决方案，在实践中会更快，因为BIT的开销要少得多。

但是，我不知道如何使用BIT结构执行给定的操作。例如，我只知道如何使用它来查询间隔总和。如何使用它来找到最小值？

如果有帮助，我有别人编写的代码可以满足我的要求，但我无法理解。这是一段这样的代码：

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

在上面的代码中，T使用0进行初始化，a是给定的数组，N其大小（无论出于何种原因，它们都从1开始索引），并upd在每次读取值时首先被调用。upd被调用之前a[x] = v被执行。

此外，p & -p与p ^ (p & (p - 1))某些BIT源中的相同，索引从1开始，零元素初始化为无穷大。

谁能解释上述工作方式或我如何用BIT解决给定的问题？