根号类算法

根号类算法是一类时间复杂度与数据规模的平方根紧密相关的算法统称。这类算法通常运用一些巧妙的技巧，在时间和空间复杂度之间找到完美平衡，从而高效解决问题。

分块算法是根号类算法的典型代表，它将数据划分成大小相等的块，对每个块进行预处理。在进行查询或修改操作时，通过对块的整体处理和对块内元素的单独处理相结合，实现时间复杂度的优化。例如，在处理区间查询问题时，分块算法可以将区间查询巧妙转化为对若干个完整块和少量剩余元素的查询，显著提高查询效率。莫队算法也是基于分块思想的离线算法，主要用于解决区间统计问题，通过对查询区间的排序和分块处理，能够在根号级别的时间复杂度内完成区间统计。在面对一些对时间和空间复杂度要求苛刻的序列查询、区间统计等问题时，根号类算法具有独特优势，是 OI 竞赛中不可或缺的算法技巧之一。