使用二叉索引树进行 RMQ 扩展

The RMQ问题可以这样扩展：

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

查询（x，y）：给定两个整数 1 ≤x, y ≤ n，找到最小值A[x], A[x+1], ... A[y];

更新（x，v）：给定一个整数v且 1 ≤x ≤ n do A[x] = v.

这个问题可以解决O(log n)对于这两个操作都使用线段树.

从理论上讲，这是一个有效的解决方案，但在实践中，线段树涉及大量开销，特别是在递归实现的情况下。

我知道有一个事实可以解决这个问题O(log^2 n)对于其中一个（或两个，我不确定）操作，使用二元索引树（可以找到更多资源，但是this and this在我看来，分别是最简洁和最详尽的）。该解决方案，对于值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被执行。

Also, p & -p与p ^ (p & (p - 1))在某些 BIT 源中，索引从 1 开始，零元素初始化为无穷大。

谁能解释一下上述内容是如何工作的，或者我如何用 BIT 解决给定的问题？

我没有详细看过代码，不过看起来大致符合下面的方案：

1）保留BIT的结构，即在数组上强加基于2的幂的树结构。

2) 在树的每个节点，保留在该节点的任何后代中找到的最小值。

3）给定一个任意范围，将指针放在范围的起点和终点，并将它们向上移动，直到它们相遇。如果将指针向上并移向另一个指针，则您刚刚进入了一个节点，其中每个后代都是该范围的成员，因此请记下该节点处的值。如果将指针向上移动并远离另一个指针，则刚刚加入的节点会记录从包括范围之外的值派生的最小值，并且您已经记下该范围内该节点下方的每个相关值，因此请忽略该节点的值。

4) 一旦两个指针是同一个指针，则范围中的最小值就是您记录的任何节点中的最小值。