对RMQ扩展使用二进制索引树

Question

可以像这样扩展RMQ problem：

给定的是一个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)中解决，因为这两个操作都使用segment trees。

这是一个有效的书面解决方案，但在实践中，段树需要大量开销，特别是在递归实现的情况下。

我知道有一种方法可以解决O(log^2 n)中的一个操作(或者两个操作，我不确定)，使用二进制索引树(可以找到更多的资源，但this和this分别是最简洁和详尽的)。这个解决方案，对于内存中的n值，实际上更快，因为比特的开销要小得多。

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

如果有帮助的话，我有其他人写的代码，可以做我想要的，但我无法理解。下面是这样一段代码：

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))相同，索引从1开始，零元素初始化为无穷大。

有人能解释一下上面的工作原理吗?或者我怎样才能稍微解决这个问题呢？

Answer 1

从一点以上的角度来看，这就是我们所拥有的：

用于整数数据数组的普通位数组g存储范围和。

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

其中，D(k)只是k，其最低阶1位设置为0。我们现在有了

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

该查询的工作方式与普通位范围和查询的工作原理完全类似，该查询的更改是在查询进行时取子范围的最小值，而不是求和。对于a中的N项，N中有上限(Log)位，这决定了运行时间。

更新需要更多的工作，因为O(log )子范围极小值(即g的元素)会受到更改的影响，而每个子范围极小值都需要一个O(log )查询来解析。这使得更新O(log^2 n)总体上如此。

在比特篡改级别上，这是非常聪明的代码。语句x += x & -x在x中清除最低顺序的连续字符串1，然后将下一个最高阶为0设置为1，这正是您“遍历”原始整数x的位所需要的。

Answer 2

我还没有详细查看代码，但它似乎与以下方案大致一致：

1)保持位的结构，即在阵列上建立一个基于二次方幂的树结构。

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

( 3)给定任意范围，将指针放在范围的开始和结束处，并将指针向上移动，直到它们相遇。如果您向上移动一个指针并指向另一个指针，那么您刚刚输入了一个节点，其中每个子代都是范围的成员，所以请注意该节点上的值。如果将指针向上移离另一个指针，那么您刚刚加入的节点将记录从值(包括超出范围的值)派生的最小值，并且您已经注意到范围内该节点下面的每个相关值，因此忽略该节点的值。

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

Answer 3

在实践中，分段树也是一种有效的解决方案。不过，你不能把它们当作树来实现。将n循环到下一个2的幂，并使用大小为2*n的数组rmq。n的最后一个rmq条目是A。如果是j < n，那么rmq[j] = min(rmq[2*j], rmq[2*j+1])。您只需要查看rmq的对数多个条目就可以回答范围最小的查询。而且您只需要在更新rmq条目时以对数方式更新A的多个条目。

不过，我不明白你的代码，所以我不会评论它。