需要清楚地解释范围更新和范围查询二进制索引树

Question

我已经完成了Range更新的几个教程 - 二进制索引树的范围查询.我无法理解他们中的任何一个.我不明白建造另一棵树的必要性.

有人可以用简单的英语向我解释一下吗？

Answer 1

试图以更直观的方式解释(我理解的方式).我将它分为四个步骤:

假设更新在A和B之间,使用V,查询是任何索引<= X的前缀查询

第一个范围更新/点查询树(T1)

第一个是简单的范围更新/点查询树.当您使用V将A更新为B时,实际上您将V添加到位置A,因此任何前缀查询X> = A都会受其影响.然后你从B + 1删除V,所以任何查询X> = B + 1都没有看到V添加到A.这里没有惊喜.

对范围更新/点树的前缀查询

这T1.sum(X)是对X的第一个树的点查询.我们乐观地假设X之前的每个元素都等于X的值.这就是我们这样做的原因T1.sum(X)*X.显然这不太正确,这就是为什么我们:

使用修改的范围更新/点查询树来修复结果(T2)

更新范围时,我们还会更新第二个树,以告知我们必须修复多少第一个T1.sum(X)*X查询.此更新包括(A-1)*V从任何查询X> = A 中删除.然后我们加回B*VX> = B. 我们做后者是因为对第一棵树的查询不会返回V> X> = B + 1(因为T1.add(B+1, -V)),所以我们需要以某种方式告诉(B-A+1)*V任何查询X> = B + 1 的区域矩形.我们已经(A-1)*V从A中删除了,我们只需要添加回B*VB + 1.

将它们全部包装在一起

update(A, B, V):
    T1.add(A, V)         # add V to any X>=A
    T1.add(B+1, -V)      # cancel previously added V from any X>=B+1

    T2.add(A, (A-1)*V)   # add a fix for (A-1)s V that didn't exist before A
    T2.add(B+1, -B*V)    # remove the fix, and add more (B-A+1)*V to any query 
                         # X>=B+1. This is really -(A-1)*V -(B-A+1)*V, but it 
                         # simplifies to -B*V

sum(X):
    return T1.sum(X)*X - T2.sum(X)