使用了RMQ扩展二进制索引树 [英] Using binary indexed trees for a RMQ extension
问题描述
借助 RMQ 可扩展，像这样的问题：
The RMQ problem can be extended like so:
由于是数组 N 整数 A 。
查询（X，Y）：给定两个整数1和乐; X ，是＆乐; 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];
更新（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）一个（或两个，我不知道）在操作，使用二进制索引树（更多的资源可以被发现，但的这个和这个< /一>是，海事组织，最简洁和详尽，分别）。该解决方案，为值 N 装入内存，在实践中更快，因为位具有少了很多开销。
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?
如果有帮助，我有其他人写的，做什么我要求code，但我无法理解它。这里有一个这样的一块code：
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;
}
在上面的code， T 被初始化为0， A 是给定的数组， N 它的大小（他们的索引从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 是一样的点^（P＆安培;（4 - 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:
一个正常的位阵列先按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]
查询工作完全像一个正常的位范围之查询与子范围的最小值被作为查询所得，而不是金额的变化。对于N项 A ，还有天花板（日志N）的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（日志N）的子区间极小 - 的先按g 即元素 - 都受到了变化，每个需要一个O（日志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.
在位小提琴演奏水平，这是恶魔般的聪明code。声明 X + = X＆放大器; -x 清除最低阶1的连续字符串 X ，然后设置一个最高的顺序零到1。这正是您需要穿越的位，原来的整数 X 。
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屋！
