树状数组

一维：区间修改区间查询

设原序列 $\{a_i\}$ 的差分序列为 $\{d_i\}$ （即 $d_i=\begin{cases}a_i-a_{i-1}&i\ge2\\a_1&i=1\end{cases}$ ）。

\begin{aligned} \sum\limits_{i=1}^na_i&=\sum_{i=1}^n\sum_{j=1}^id_j\\ &=\sum_{i=1}^nd_i\times(n-i+1)\\ &=(n+1)\times\sum_{i=1}^nd_i~-\sum_{i=1}^ni\times d_i \end{aligned}

因此，除了维护差分序列 $\{d_i\}$ 本身的前缀和外，还需维护序列 $\{i\times d_i\}$ 的前缀和。

区间查询：如上。
区间修改：序列 1 第 $l$ 位加上 $\Delta x$ 、第 $r+1$ 位减去 $\Delta x$ ；序列 2 第 $l$ 位加上 $l\times\Delta x$ 、第 $r+1$ 位减去 $(r+1)\times\Delta x$ 。

二维：区间修改区间查询

定义差分数组 $d_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1}$ 。则 $a_{i,j}=\sum\limits_{h=1}^i\sum\limits_{k=1}^jd_{h,k}$ 。

\begin{aligned} \sum_{i=1}^x\sum_{j=1}^ya_{i,j}&=\sum_{i=1}^x\sum_{j=1}^y\sum_{h=1}^i\sum_{k=1}^jd_{h,k}\\ &=\sum_{i=1}^x\sum_{j=1}^yd_{i,j}\times(x-i+1)\times(y-j+1)\\ &=(x+1)(y+1)\sum_{i=1}^x\sum_{j=1}^yd_{i,j}-(y+1)\times\sum_{i=1}^x\sum_{j=1}^yi\times d_{i,j}-(x+1)\times\sum_{i=1}^x\sum_{j=1}^yj\times d_{i,j}+\sum_{i=1}^x\sum_{j=1}^yi\times j\times d_{i,j} \end{aligned}

莫队

普通莫队

设块大小为 $O(B)$ ， $l$ 的总移动为 $O(Bm)$ ， $r$ 的总移动为 $O(\frac nB\cdot n)$ ，总共为 $O(Bm+\frac{n^2}B$ 。由均值不等式得块长在 $B\in O(\frac n{\sqrt m})$ 时取得最小值，总复杂度 $O(n\sqrt m)$ 。

常数优化：

奇偶交错升降。
块大小可尝试 $\frac n{\sqrt{\frac 23m}}$ 。

带修莫队

第一关键字 $L$ 按所在块排序，第二关键字 $R$ 按所在块排序，第三关键字按时间排序。当块长 $B\in O(n^{\frac23})$ （假设 $n=m$ ）时，总复杂度 $O(n^{\frac53})$ 。