分块(Sqrt Decomposition)

分块(Sqrt Decomposition,平方根分解)是一种把长度为 n 的序列划分成若干个大小约为根号 n 的连续区块,并对每个区块预先维护聚合信息(如区间和、最值、标记)的通用技巧。区间操作时,整块直接使用块内聚合信息批量处理,不完整的两端零散元素则暴力遍历,从而将单次操作复杂度降到约根号 n。

概述

分块并非某个具体算法,而是一种优雅折中的思想:它牺牲一部分渐进最优性,换取实现简单与适应性强。当问题难以用线段树维护的复杂标记表达时,分块往往能以更直观的方式解决。块的大小通常取根号 n,使整块数量与零散块内元素数量达到平衡,总代价最小。

核心原理

• 预处理:把序列分成约根号 n 个块,记录每个元素所属块号,并为每块维护整体信息。
• 整块操作:对完全落在查询区间内的块,直接读取或修改其聚合值,并使用懒标记记录待下放的整体修改。
• 零散处理:对区间两端不完整的块,逐个元素暴力更新,并在必要时先下放该块的懒标记。
• 复杂度:块数与块长均约为根号 n,故单次操作约为根号 n 级别。

应用场景

分块广泛用于区间加区间求和、区间修改区间查询最值、区间众数、区间第 k 大等竞赛题;它也是莫队算法的思想基础。当维护信息不满足区间可加性、难以用线段树标记合并时,分块几乎是万能的兜底方案。

常见问题

问:分块和线段树该如何取舍?答:线段树单次操作为对数级,渐进更优;但分块实现简单、能处理线段树难以表达的复杂查询,常数也较可控,在数据规模不极端时性能足够。

问:块大小一定取根号 n 吗?答:根号 n 是理论最优点,但实际中可根据操作与查询的频率比例微调块长以优化常数,例如查询多则块取小一些。