algorithm - 使用二进制索引树进行 RMQ 扩展

Question

RMQ problem可以这样扩展:

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

query(x, y):给定两个整数1≤x，y≤n，求A[x], A[x+1], ... A[y] 的最小值;

update(x, v): 给定一个整数 v 并且 1 ≤ x ≤ n 做 A[x] = v。

使用segment trees 可以在O(log n) 中解决这两个操作的问题.

这在理论上是一个有效的解决方案，但在实践中，线段树涉及大量开销，尤其是递归实现时。

我知道有一种方法可以解决 O(log^2 n) 中的一个(或两个，我不确定)操作的问题，使用二进制索引树(可以找到更多资源，但是 this 和 this 在 IMO 中分别是最简洁和详尽的)。对于适合内存的 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 与某些 BIT 源中的 p ^ (p & (p - 1)) 相同，索引从 1 开始零元素初始化为无穷大。

谁能解释一下上面的工作原理或者我如何用 BIT 解决给定的问题？

Answer 1

我没有仔细看代码，不过好像大致符合下面的方案:

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

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

3) 给定一个任意范围，将指针放在范围的起点和终点并向上移动它们直到它们相遇。如果您向上移动一个指针并朝向另一个指针，那么您刚刚进入一个节点，其中每个后代都是该范围的成员，因此请记下该节点的值。如果你向上移动一个指针并远离另一个指针，你刚刚加入的节点记录了从范围外的值导出的最小值，并且你已经注意到范围内该节点下方的每个相关值，所以忽略该节点的值。

4)一旦两个指针是同一个指针，范围内的最小值就是你记下的任意节点中的最小值。