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

背景

在《秋天的第一杯奶茶》一题中，全机房都rush了一个莫队，莫队左右端点的指针移动操作是一个区间查询/区间修改的问题。zzh毫不犹豫的拍了个线段树板子，然后：

凭借着线段树的大常数成功垫底。

推导

转自OI-wiki

若维护序列 $a$ 的差分数组 $b$ ，此时我们对 $a$ 的一个前缀 $r$ 求和，即 $\sum_{i=1}^{r} a_i$ ，由差分数组定义得 $a_i=\sum_{j=1}^i b_j$

进行推导

$\begin{aligned} &\sum_{i=1}^{r} a_i\\=&\sum_{i=1}^r\sum_{j=1}^i b_j\\=&\sum_{i=1}^r b_i\times(r-i+1) \\=&\sum_{i=1}^r b_i\times (r+1)-\sum_{i=1}^r b_i\times i \end{aligned}$

区间和可以用两个前缀和相减得到，因此只需要用两个树状数组分别维护 $\sum b_i$ 和 $\sum i \times b_i$ ，就能实现区间求和。

效果