根号算法

分块

1. $M$ $l$ $r$ $x$，表示将区间 $[l,r]$ 的每个数都加 $x$。
2. $Q$ $l$ $r$，表示查询区间 $[l,r]$ 的每个数的和。

根号分治

1. 每次询问暴力 $O(\frac{n}{x})$ 的一个一个跳。这样的话，查询操作会在 $x$ 很小的时候卡到 $O(n)$，而每次修改是 $O(1)$ 的。
2. 维护一个数组 $sum_{i,j}$，表示下标模 $i$ 余 $j$ 的数的和。每次修改的时候，我们修改 $sum_{i,x\%i}$，其中 $i$ 为后面的查询中最大的 $x$。这样的话，修改操作会在 $i$ 很大的时候卡到 $O(n)$ ，而每次查询是 $O(1)$ 的。

1. 维护数组 $sum_{i,j}$，意义与上述第二种暴力相同，但我们只维护 $i \le \sqrt{n}$ 的模数 $i$。
2. 对于每次查询，如果 $x \le \sqrt{n}$，直接输出 $sum_{x,y}$，复杂度 $O(1)$ ；否则，暴力 $O(\frac{n}{x})$ 的跳过去，复杂度 $O(\sqrt{n})$。
3. 每次修改，更新 $sum_{i,x\%i}$，复杂度 $O(\sqrt{n})$。

莫队

普通莫队

while (R<r) Add(++R);
while (R>r) Delete(R--);
while (L>l) Add(--L);
while (L<l) Delete(L++);

//其中Add()表示加贡献，Delete()表示减贡献

复杂度

$R$ 的移动

$L$ 的移动

带修改的莫队

1. 当 $T<t$ 时，暴力操作到第 $t$ 次。
2. 当 $T>t$ 时，暴力还原到第 $t$ 次。