data-structures - 如何在二叉索引树中实现范围更新和范围查询？

Question

我已经阅读了一些关于二进制索引树的教程，但是当查询和更新两个操作都在某个范围内时，我无法理解如何实现它。

Answer 1

要实现范围更新和范围查询，您需要了解范围更新和点查询（ update [a,b] with v; query(x) 给出 A[x] 处的值）。

我们将使用两个 BIT 来实现范围更新和范围查询。

假设数组初始化为 0。如果我们用 v 更新 [a,b]，

For some x, sum(0,x) = 0     if 0 < x < a

                     = v*(x - (a-1)) if a <= x <= b

                     = v * (b - (a-1)) if b < x

where v is the value at A[x] (calculated via BIT1)

从上面的公式中，我们会找到 T，当从 v*x 中减去（v 是从 BIT1 计算出来的）我们得到结果。

if 0 < x < a : sum(0,x) = 0, T = 0

   a <= x <= b: sum(0,x) = v*x - v*(a-1) , T = v*(a-1)

   b < x : sum(0,x)  = v*(b-a+1) , T = -v*(b-(a-1)) (since A[x] = 0 when x > b)

We store T in second BIT (BIT2)

现在，用 v 实现更新 [a,b]：

update(a,v) ; update(b+1,-v) in BIT1 and

update(a,v*(a-1)); update(b+1,-v*b) in BIT2

总和[0,x]：

QueryBIT1(x)*x - QueryBIT2(x); // call query() on corresponding BIT

其中，update(index,value) 和 Query(index) 是用于点更新和范围查询的实现。

对于，进一步的细节：

http://zobayer.blogspot.in/2013/11/various-usage-of-bit.html https://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree /