莫队
考虑一个经典的问题。对一个数列进行 \(m\) 次区间求和。暴力需要 \(O(nm)\)，但是莫队可以优化到 \(O(n\sqrt m)\)。
思想具有启发式思维。假如我们知道 \([l,r]\) 的和为 \(k\)。在此基础上 \([l-1,r],[l,r+1]\) 都可以很快得到。莫队是对上一个问题解决这个问题。要给对问题的求解一个顺序，否则 \(l,r\) 的移动在最坏情况都是 \(n\)。用分块的思想排序，设块长为 \(len\)。把 \(l\) 的块编号按第一关键字，\(r\) 为第二关键字排序。这样，\(l\) 移动次数为 \(len\times m\)，\(r\) 移动次数为 \(\frac{n^2}{len}\)。均值不等式求得 \(len = \sqrt \frac{n^2}{m}\)。 在莫队中，块长对于复杂度有决定性的作用。
小优化
- 对于块编号 \(id\)，使用数组存储。
- 对于奇数块，\(r\) 升序；偶数块，\(r\) 降序。
回滚莫队
很多时候我们只方便加，或只方便减。以下考虑只加不减。
回观普通莫队，对于每次询问。\(l\) 都可能减。但是只要还在一个块。\(r\) 只会增加。
我们需要在每次询问时，将 \(l\) 只加不减。修改为当前块的右端点 \(+1\)。在当前块变化时，将 \(r\) 修改为当前块的右端点。
然后按照普通莫队求解，但是这时候 \(l\) 的操作是临时的，不要覆盖可以重复使用的区间答案。按照普通莫队的分析方法可证复杂度 \(O(n\sqrt m)\)。
树上莫队
一般都是将树的括号序跑下来。在这上面做莫队。例题：COT2 - Count on a tree II
标签：复杂度,len,小计,sqrt,块长,例题,莫队 From： https://www.cnblogs.com/yfzqwq/p/18165631