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

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

在此感谢一下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]的前缀和即可 用两个树状数组维护这两个值就好了

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

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


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter