树状数组支持区间加减和求区间和的方法

starli posted @ 2016年2月05日 20:45 in 数据结构 , 351 阅读

在此感谢一下Claris教我这个方法,而我当时居然没看到……

CA爷说得好：学长给你讲啥你要好好听..就算听完不会也得问问..

设delta[i]=a[i]-a[i-1] 即delta[i]为delta的增量则$a[i]=\sum_{k=1}^{i}delta[k]$

修改的时候（令[s,t]+c）就很显然了 delta[s]+=c,delta[t+1]-=c;

比较麻烦的是求和

我们要求区间(1,t)的和 $\sum_{k=1}^{t}a[i]=\sum_{k=1}(t-k+1)delta[k]=(t+1)\sum_{k=1}^{t}delta[k]-(\sum_{k=1}^{t}k*delta[k])$

在这里我们只要快速计算出delta[k]的前缀和以及 k*delta[k]的前缀和即可用两个树状数组维护这两个值就好了

至此我们可以用两个树状数组动态维护数组的区间加减和求区间和了

代码的话以后等我写了再补

From The Stupid