树状数组区间加区间求和

2018-10-10 15:58:05


普通的树状数组是可以单点修改区间求和或者区间修改单点查询

要支持区间修改区间求和,需要一些骚操作


记差分数组 $d_i=a_i-a_{i-1}$

那么 $a_x=\sum_{i=1}^xd_i$

前缀和 $sum_x=\sum_{i=1}^xa_i$

将 $a_i$ 拆开,得到 $sum_x=\sum_{i=1}^x(x-i+1)d_i$

也就是 $sum_x=\sum_{i=1}^x{(x+1)d_i}-\sum_{i=1}^xi*d_i$

所以树状数组中维护两个值,一个 $d_i$ ,一个 $i*d_i$

修改的时候修改 $l$ 和 $r+1$ 两个点,查询的时候 $ans=sum(r)-sum(l-1)$