简单分块与莫队

1 - 分块

1.1 - 定义

分块是将要维护的信息分成若干块，而后通过维护整块的信息或者是块间的信息来优化算法。

1.2 - 序列分块

在序列上以线段树来类比，线段树是将序列每次对半分，最后得到一个比较完美的二叉树的结构。分块是将序列首先分成一个多叉树，根的儿子节点的儿子就直接是叶子。

1.3 - 复杂度分析

复杂度分析：假设块的大小是 \(B\)，一共有 \(\frac nB\) 块，整块部分的复杂的度就是 \(O\left(\frac nB\right)\)，散块部分的复杂度是 \(O(B)\)，所以整体复杂度是 \(O\left(\frac nB+B\right)\)，显然 \(B\) 取 \(\sqrt n\) 的时候最优。

分块的时候务必分析时间复杂度来取合适的块大小，不要无脑取根号。

1.4 - 分块的优点

分块在修改的时候，只有若干整块以及两个散块需要修改，在整块的处理上，其和线段树等一样，都是打标记，但是在散块上，其只需要暴力修改两个小散块的信息，整个修改过程只和散块中的元素有关，而线段树等数据结构会从叶子开始一层层往上更新，最后牵扯到整个序列信息。

分块在统计答案的时候只有整块的散块的区别，不像线段树等那般有多层结构，这使得信息难以合并的时候，分块有其特殊的用处。

1.5 - 分块思想的另一种应用

对于动态修改问题，有时候我们会遇到这样一种情况：想到了两种做法，一种可以快速修改，但查询很慢；一种可以快速查询，但是修改很慢。这种时候也可以使用分块算法进行折中处理。

2 - 莫队

2.1 普通莫队

对于序列上的区间询可问题,如果从\([η的答案能够O(1)扩展到[1ー1,r,7+1,r,[,r+1,[,rー]\)的答案,那么可以在O(nvm)的复杂度内求出所有询可的答案,实际就是一种优美的暴力。