6

RMQ 问题可以这样扩展：

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

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

update(x, v)：给定一个整数v和 1 ≤ x≤ ndo A[x] = v。

O(log n)对于这两种操作，都可以使用段树来解决这个问题。

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

我知道有一种方法可以解决O(log^2 n)一个（或两个，我不确定）操作中的问题，使用二进制索引树（可以找到更多资源，但是这个和这个是，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被执行。

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

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

4

3 回答 3

3

代码我没仔细看，不过好像和下面的方案大体一致：

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

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

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

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

于 2013-06-18T04:28:59.450 回答
2

从位摆弄之上的一个层次来看，这就是我们所拥有的：

g整数数据数组的普通 BIT 数组a存储范围和。

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]

该查询的工作方式与普通的 BIT 范围求和查询完全一样，只是在查询进行时取子范围的最小值而不是求和。对于 中的 N 项a，N 中有上限（log N）位，它决定了运行时间。

更新需要更多的工作，因为 O(log N) 子范围最小值 - 即元素g- 受到更改的影响，并且每个都需要 O(log N) 自己的查询来解决。这使得整体更新 O(log^2 n)。

在位摆弄级别，这是非常聪明的代码。该语句x += x & -x清除 1 的最低顺序连续字符串，x然后将下一个最高顺序零设置为 1。这正是您“遍历”原始 integer 的 BIT 所需要的x。

于 2013-06-18T12:51:35.530 回答
0

段树在实践中也是一种有效的解决方案。但是，您不会将它们实现为树。向上n取整到 2 的下一个幂并使用rmqsize数组2*n。的最后一个n条目rmq是A。如果j < n，那么rmq[j] = min(rmq[2*j], rmq[2*j+1])。您只需要以对数方式查看多个条目rmq即可回答范围最小查询。并且您只需要在更新条目rmq时以对数方式更新多个条目A。

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

于 2013-06-18T00:10:01.940 回答