kkogoro

树状数组区间修改与区间查询
树状数组维护区间修改,区间询问推导这里用区间加,询问区间和来进行示范,要注意树状数组是用来维护满足区间加法的信息的...
扫描右侧二维码阅读全文
25
2018/11

树状数组区间修改与区间查询

树状数组维护区间修改,区间询问

推导

这里用区间加,询问区间和来进行示范,要注意树状数组是用来维护满足区间加法的信息的。

首先为了保证修改的复杂度,我们要差分一下,这样单次区间加复杂度 $O(log{n})$

对于询问一个前缀和首先有 $O(n^2)$ 暴力公式(diff是差分数组)

$$ \sum_{i=1}^{x}\sum_{j=1}^{i} diff[j] $$

利用树状数组我们可以得到朴素复杂度 $O(n\log{n})$ ,显然这很爆炸

观察每个diff[i]被加入了答案几次,可以写出

$$ \sum_{i=1}^{x}(x-i+1)\times diff[i] $$

按照常量与自变量分类

$$ \sum_{i=1}^{x}(x+1)\times diff[i] - \sum_{i=1}^{x}i\times diff[i] $$

提出 $x+1$

$$ (x+1)\times \sum_{i=1}^{x} diff[i] - \sum_{i=1}^{x}i\times diff[i] $$

所以我们开两个树状数组BIT1BIT2分别维护

$diff[i]$ 和 $i\times diff[i]$ 的前缀和,然后按照 $L-1$ , $R$ 的前缀和做差就可以实现区间加,区间查询了。

应用

我们来看一道简单的题目吧!

BZOJ 3110 K大数查询

Last modification:November 25th, 2018 at 06:45 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment