使用二进制索引树进行RMQ扩展 [英] Using binary indexed trees for a RMQ extension
问题描述
RMQ问题可以这样扩展：
给定是一个数组 n 整数 A 。
查询（x，y）：给定两个整数1≤ x ， y ≤ n ，找到最小值 A [x]，A [x + 1]，... A [y] ;
query(x, y): given two integers 1 ≤ x, y ≤ n, find the minimum of A[x], A[x+1], ... A[y];
update（x，v）：给定一个整数 v 和1 ≤ x ≤ n do A [x] = v 。
update(x, v): given an integer v and 1 ≤ x ≤ n do A[x] = v.
这个问题可以在 O（log n）中使用分段树。
This problem can be solved in O(log n) for both operations using segment trees.
这是在纸上有效的解决方案，但在实践中，段树涉及很多开销，特别是如果递归实现的话。
This is an efficient solution on paper, but in practice, segment trees involve a lot of overhead, especially if implemented recursively.
我知道有一种方法可以解决 O（log ^ 2 n）对于一个（或两者，我不确定）的操作，使用二进制索引树（可以找到更多的资源，但此和此是IMO ，最简洁和详尽）。对于适合内存的 n 的值，此解决方案在实践中更快，因为BIT的开销较少。
I know for a fact that there is a way to solve the problem in O(log^2 n) for one (or both, I'm not sure) of the operations, using binary indexed trees (more resources can be found, but this and this are, IMO, the most concise and exhaustive, respectively). This solution, for values of n that fit into memory, is faster in practice, because BITs have a lot less overhead.
但是，我不知道如何使用BIT结构来执行给定的操作。我只知道如何使用它来查询例如间隔和。如何使用它找到最低限度？
However, I do not know how the BIT structure is used to perform the given operations. I only know how to use it to query an interval sum for example. How can I use it to find the minimum?
如果它有帮助，我有其他人写的代码，这是我要求的，但我无法理解它。这是一个这样的代码：
If it helps, I have code that others have written that does what I am asking for, but I cannot make sense of it. Here is one such piece of code:
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索引为1任何原因）和 upd 首先被调用为每个读取值。之前 upd 被称为 a执行[x] = v 。
In the above code, T is initialized with 0, a is the given array, N its size (they do indexing from 1 for whatever reason) and upd is called at first for every read value. Before upd is called a[x] = v is executed.
另外， p& -p 与某些BIT源中的 p ^（p&（p-1））相同，索引编号从1开始，零元素初始化为无穷大。
Also, p & -p is the same as the p ^ (p & (p - 1)) in some BIT sources and indexing starts from 1 with the zero element initialized to infinity.
任何人都可以解释上述的工作原理，或者我如何用BIT解决给定的问题？
Can anyone explain how the above works or how I could solve the given problem with a BIT?
推荐答案
从一个比较轻微的位置开始，这是我们所拥有的：
From a level above the bit fiddling, this is what we have:
一个正常的BIT数组 g 用于整数数据数组 a 存储范围总和。
A normal BIT array g for integer data array a stores range sums.
g[k] = sum{ i = D(k) + 1 .. k } a[i]
其中 D（k）只是 k ，最低位1位设置为0.这里我们改为
where D(k) is just k with the lowest-order 1 bit set to 0. Here we have instead
T[k] = min{ i = D(k) + 1 .. k } a[i]
查询的工作原理与正常的BIT范围和查询一样，随着查询的进行而不是求和而将子范围的最小值取为最小。对于 a 中的N个项目，N中有ceiling（log N）位，用于确定运行时间。
The query works exactly like a normal BIT range sum query with the change that minima of subranges are taken as the query proceeds rather than sums. For N items in a, there are ceiling(log N) bits in N, which determines the run time.
更新需要更多的工作，因为O（log N）子范围最小值 - 即元素 g 受到更改，并且每个都需要一个O（log N）查询本身来解决。这使得整体更新O（log ^ 2 n）。
The update takes more work because O(log N) subrange minima - i.e. elements of g - are affected by the change, and each takes an O(log N) query by itself to resolve. This makes the update O(log^2 n) overall.
在比特级别，这是一个非常聪明的代码。语句 x + = x& -x 清除 x 中的最低连续字符串1，然后将下一个最高级零设置为1.这就是你需要穿过原始整数的元数据$ $ $ code>。
At the bit fiddling level this is fiendishly clever code. The statement x += x & -x clears the lowest-order consecutive string of 1's in x and then sets the next highest-order zero to 1. This is just what you need to "traverse" the BIT for the original integer x.
这篇关于使用二进制索引树进行RMQ扩展的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
