树状数组的区间加区间查询操作

对数组 $A_{1\dots n}$ 进行区间加和区间查询操作，令 $D_i=A_i-A_{i-1}$，即

$$\sum _{j=1}^i{D}_j=A_i$$

区间查询 $S(l,r)$ 可以差分为前缀和 $S(r)-S(l-1)$，则有

$$\begin{array}{rl}S(x)& =\sum _{i=1}^x{A}_i\\ & =\sum _{i=1}^x\sum _{j=1}^i{D}_j\\ & =\sum _{j=1}^x{D}_j(x-j+1)\\ & =(x+1)\sum _{j=1}^x{D}_j-\sum _{j=1}^x(j\times D_j)\end{array}$$

因此，求答案只需维护 $D$ 的前缀和以及 $i\times D$ 的前缀和。当对 $A_{l\dots r}$ 区间加时，只有 $D_l$ 和 $D_{r+1}$ 发生了变化，转化为单点加单点查询。