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

Question

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

Answer 1

要实现范围更新和范围查询，需要了解范围更新和点查询（update [a,b] with v; query(x) gives the value at 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/

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

How do I implement a range update and range queries in Binary Indexed Tree?

data-structures

fenwick-tree