第一次看到区间并查集这个名词是在做一类区间染色题的时候。暴力模拟每次都把 [l, r] 重新涂一遍遇到覆盖频繁的样例直接超时而题解区有人写了这么一句话“倒着处理每个点只会被赋值一次用并查集跳过去。”我当时愣了半天并查集不是用来维护连通性的吗怎么能“跳”后来才想明白这套做法的本质是把每个已经确定答案的位置看成一个“坏点”find(i) 直接返回它右边第一个还没确定的位置。而同样是区间操作另一类问题——单点修改、区间求和我几乎条件反射地拿出树状数组。这篇东西想聊的就是区间并查集和树状数组这两样工具一个负责让区间操作里的重复劳动消失一个负责把区间统计压到对数级。如果你正在刷算法题或者手头有一个数组要做批量赋值加区间查询的需求读完应该能直接动手写核心代码。1. 区间问题的两种刚需跳过与统计1.1 从一道染色题看“跳过”的价值假设有 n 个空位m 次操作每次把区间 [l, r] 全部涂成某种颜色后面的操作会覆盖前面的颜色问你最后每个位置是什么颜色。最直接的做法是从第一次操作开始模拟每次都把区间里的点重新赋值。麻烦在于一个点可能被反复涂很多次最后一次操作尤其浪费如果第 m 次操作覆盖了 1e5 个位置前面那些涂色等于是白涂。正难则反。既然最后的状态由最后一次覆盖决定那就把操作倒过来看从最后一步往前处理某个位置第一次被涂到就是它的最终颜色之后遇到它就可以直接忽略。于是问题变成了“如何快速跳过已经处理过的位置”。这就是区间并查集的用武之地。1.2 从区间求和看“统计”的价值另一类常见问题是维护一个数组支持单点加一个数查询 [l, r] 的和。朴素做法是修改 O(1)、查询 O(n)如果查询很多复杂度很快失控。树状数组解决的就是这个统计问题它把前缀和查询和单点修改都做到 O(log n)。线段树也能做但树状数组代码量小、常数小在处理“只需要前缀信息”的场景下几乎是最优选择。所以区间问题通常可以分成两派一派需要跳过重复操作一派需要快速统计信息。很多题目单独用其中一种就够了但某些题目需要两个一起上这时候对两个工具的理解都得过关。2. 区间并查集让“已处理的点”自己跳开2.1 同一个 find不同的语义普通并查集里fa[i] 指向集合的根find(i) 返回 i 属于哪个集合。区间并查集借用了这个结构但语义变了一下fa[i] 表示从 i 出发向右第一个还未被处理过的位置。一开始所有点都未处理所以 fa[i] i。当点 x 被处理完就让 fa[x] find(x 1)意思是我这个位置已经没用了你下次找我直接去右边找空位。配合路径压缩整个链会越跳越短最终所有点都会指向哨兵 n 1。这里可以用电影院找座位的例子来理解你约好了有一个座位但实际上你旁边的座位被人占了被占的座位会告诉你“去下一个空位看看”。一路问下去总能找到空位。因为每个位置被占后都会更新信息下一轮再有人问就能直接跳到更远的空位不需要重新扫描中间所有已占座位。2.2 标准模板与主循环写法初始化需要多开一个哨兵位置 n 1const int N 1e6 5; int fa[N]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void init(int n) { for (int i 1; i n 1; i) fa[i] i; }处理区间 [l, r] 的每个未处理位置核心循环是这样的int x find(l); while (x r) { // 处理点 x例如给最终答案数组赋值 ans[x] color; // 处理完就让这个点指向右边第一个未处理位置 fa[x] find(x 1); // 继续从新的空位开始 x fa[x]; }注意x find(l)这一步不能省因为 l 本身可能已经被处理过了。如果写成int x l;遇到 l 已被处理的情况就会反复访问一个废点。2.3 为什么区间并查集不需要按秩合并一般并查集教程会强调按秩合并可以保证树高 O(log n)。但区间并查集里我基本没见过有人用按秩合并原因是这里的“合并”方向是固定的一个点被处理后就指向它右边的位置相当于把当前点从待处理集合里摘除挂到下一个待处理节点上。这种操作不会出现两个规模差不多的集合随机合并的场景树的高度主要靠路径压缩来压。最坏情况下处理顺序是从左往右逐个赋值但下一次 find 某个点时会一路压缩后续的 find 代价会显著下降。实际跑下来加上路径压缩的版本在 n 1e6 的数据上非常稳不需要额外维护秩数组。2.4 它最适合什么题区间并查集最经典的场景是倒序染色操作会互相覆盖但某个位置只关心最后一次覆盖。它同样适用于“给每个点分配一个不重复的值”“把某个区间内所有还没被占用的位置标记掉”这类去重问题。如果操作是可撤销的、同一个点会被多次要求计算或者你需要知道每个点一共被覆盖了多少次那区间并查集就不太合适了。统计覆盖次数应该用差分数组区间加应该用树状数组的区间修改版本别硬套。3. 树状数组从 lowbit 到差分模板的一次性讲透3.1 lowbit 到底是什么树状数组的底层是二进制。lowbit(x) x -x它取出 x 的二进制表示里最低位的 1 以及后面的 0例如 x 6二进制 110lowbit(6) 2。这个 lowbit 出现了两种用途更新时从当前下标不断加上 lowbit跳到父节点查询时从当前下标不断减去 lowbit拆成若干个覆盖完整区间的块。树状数组里点 x 管理的是从x - lowbit(x) 1到 x 这一段区间的和。第 6 个节点管理 [5, 6]第 8 个节点管理 [1, 8]。这样设计的好处是任何一个前缀都能用不超过 log n 个“完整块”拼出来。3.2 单点加、前缀和的两段循环这是最基础也最需要背熟的部分void add(int x, int v) { for (; x n; x x -x) { bit[x] v; } } int sum(int x) { int res 0; for (; x 0; x - x -x) { res bit[x]; } return res; }查询 [l, r] 时直接sum(r) - sum(l - 1)。这里有个常见误解树状数组内部每个节点存的是“原数组某一段的和”不是原数组本身。理解这件事后面看差分版本才不会懵。3.3 差分加双 BIT区间加、区间求和的推导如果题目要求“把 [l, r] 整体加上 v再查询区间和”单点加模板就不够用了需要借助差分。设原数组为 a[]差分数组 d[]其中 d[1] a[1]d[i] a[i] - a[i - 1]。对 a[l..r] 整体加 v反映到差分数组上只有两个位置变化d[l] vd[r 1] - v。于是问题变成了维护 d[] 的前缀和就能拿到 a[x]但如果要查询前缀和还需要再多推一步。假设要求 S[x] a[1] a[2] ... a[x]把 a 展开成 d 的累加S[x] d[1] (d[1] d[2]) ... (d[1] d[2] ... d[x])换个角度看d[j] 在前缀和里一共出现了 (x - j 1) 次所以S[x] Σ d[j] * (x - j 1) (x 1) * Σ d[j] - Σ j * d[j]这个式子拆成了两部分一部分是 Σ d[j]另一部分是 Σ j * d[j]。所以开两个树状数组一个存 d[j]另一个存 j * d[j] 即可。struct BIT { int n; vectorlong long c; BIT(int n): n(n), c(n 2, 0) {} void add(int x, long long v) { for (; x n; x x -x) c[x] v; } long long qry(int x) { long long res 0; for (; x 0; x - x -x) res c[x]; return res; } }; BIT b1(n), b2(n); void range_add(int l, int r, long long v) { b1.add(l, v); b1.add(r 1, -v); b2.add(l, l * v); b2.add(r 1, (r 1) * (-v)); } long long prefix_sum(int x) { return (x 1) * b1.qry(x) - b2.qry(x); } long long range_sum(int l, int r) { return prefix_sum(r) - prefix_sum(l - 1); }这里要小心 r 1 这一项如果 r n在维护差分时还要访问 n 1所以 BIT 的容量要开成 n 1甚至 n 2 更稳妥。3.4 树状数组的本质题感树状数组能做的事情比很多人以为的多求逆序对、二维偏序计数、离线就绪后的区间颜色统计都能用。以逆序对为例先把数组排序离散化然后从左往右扫每扫到一个数就把对应位置 1同时查询当前位置右侧已经有多少个数累加即可。sort(tmp 1, tmp n 1); int m unique(tmp 1, tmp n 1) - tmp - 1; long long inv 0; for (int i 1; i n; i) { int id lower_bound(tmp 1, tmp m 1, a[i]) - tmp; inv i - 1 - sum(id); add(id, 1); }树状数组解决这类问题的核心能力是“前缀统计”而不是“区间维护”。理解了这一点你就能判断什么时候用树状数组、什么时候必须上线段树。4. 组合实战每个点只赋值一次但要实时回答区间和4.1 一个把两个工具绑在一起的题目设定我实际遇到过这样的需求维护一个长度为 n、初始全为 0 的数组支持两类操作操作 1update l r c把 [l, r] 里所有还没被赋过值的位置赋值为 c操作 2query l r查询当前 [l, r] 的和。注意“还没被赋过值”这个限制它保证了每个点在整个运行过程中最多被处理一次。如果直接用线段树做区间赋值代码不短如果用区间并查集配合树状数组思路非常干净。区间并查集负责跳过已赋值的位置保证操作 1 的总复杂度不会退化到 O(nm)树状数组负责单点赋值后的区间求和让操作 2 的查询能做到 O(log n)。4.2 为什么这里缺一不可只靠区间并查集确实能维护“哪些点被赋值过”也能在最后统一算一遍总和。但查询操作是穿插在赋值操作之间的你不可能每次都把所有点重新扫一遍求和那样会退化成 O(n)。只靠树状数组区间求和很简单但“跳过已赋值的位置”这个需求没有对应的数据结构支持。你不能给整个区间打标记说“这些点以后不再碰”因为这本质上是一个集合删除操作树状数组不负责这种事。两个工具合在一起各管一摊一个管“点的生命状态”一个管“值的聚合结果”。这也是我推荐你分开理解它们的原因。4.3 可以直接跑的模板代码#include bits/stdc.h using namespace std; const int N 1e6 5; int fa[N]; long long bit[N]; int n, m; int find(int x) { while (fa[x] ! x) { fa[x] fa[fa[x]]; x fa[x]; } return x; } void bit_add(int x, long long v) { for (; x n; x x -x) bit[x] v; } long long bit_sum(int x) { long long res 0; for (; x 0; x - x -x) res bit[x]; return res; } int main() { scanf(%d%d, n, m); for (int i 1; i n 1; i) fa[i] i; while (m--) { int op; scanf(%d, op); if (op 1) { int l, r; long long c; scanf(%d%d%lld, l, r, c); int x find(l); while (x r) { bit_add(x, c); fa[x] find(x 1); x fa[x]; } } else { int l, r; scanf(%d%d, l, r); printf(%lld\n, bit_sum(r) - bit_sum(l - 1)); } } return 0; }这段代码里有一个很关键的细节fa[x] find(x 1); x fa[x];两行必须连在一起。如果只赋值fa[x]却不更新 x下一轮循环会重新处理已赋值的点轻则死循环重则重复计入答案错的非常隐蔽。4.4 复杂度与扩展思路总的赋值次数不会超过 n每个点被区间并查集找到后立即被标记跳过所以所有 update 里实际修改 BIT 的次数是 O(n)。每次 update 还要做若干次 find均摊下来几乎常数。每次 query 是两次 BIT 前缀和O(log n)。整体复杂度大约是 O((n m) log n)内存上只需要两个 O(n) 级别的数组非常轻量。这套思路还可以扩展。如果题目改成“查询当前还有多少个位置没有被赋值”初始化时把每个位置都 add 1赋值时 add -1查询时直接 sum(n) 即可。如果改成“每个点记录最后一次赋值的编号”那把 BIT 换成普通数组甚至不用 BIT 也能做。核心不变每个点只处理一次统计工具随便挑。5. 踩坑复盘写这两个工具时最容易出问题的地方5.1 主循环里的更新顺序必须固定区间并查集的模板循环我至少见过三种错误写法。最典型的错误是int x find(l); while (x r) { // 处理 x fa[x] find(x 1); x; // 错x 应该跳到新空位而不是简单加 1 }如果 x 在赋值后这么处理下一次检查的可能是已经处理过的点或者跳过了真正未处理的点。正确做法是x fa[x]因为fa[x]已经收藏了find(x 1)的结果。还有一个容易忽略的点进入循环前必须x find(l)。哪怕代码里前面已经写过类似判断也要养成在循环开头重新 find 的习惯因为 l 可能在之前的操作中被赋值过。5.2 哨兵 n 1 和数组边界区间并查集的 fa 数组必须初始化到 n 1。如果只初始化到 n当某个点指向 n 1 时find 会访问一个未初始化的位置轻则返回随机值重则数组越界崩溃。我习惯这样处理for (int i 1; i n 1; i) fa[i] i;这样 n 1 也能自环作为“没有空位了”的终止标记。所有区间处理循环里都用x r作为退出条件一旦 x 变成 n 1自然退出循环。5.3 find 的递归写法在大数据量下的风险递归版 find 很短但是当区间并查集形成的链很长时递归深度可能达到 O(n)。比如从左往右依次处理点 1 到 n某个新操作从位置 1 开始找空位递归路径会一路走到 n 1递归 1e6 层不是开玩笑的。为了避免不必要的栈风险我建议直接用迭代版 findint find(int x) { while (fa[x] ! x) { fa[x] fa[fa[x]]; x fa[x]; } return x; }这个写法做了路径压缩不递归代码只比递归版多两行在极限数据下更安心。5.4 BIT 查询的边界和数值类型查询区间和时用bit_sum(r) - bit_sum(l - 1)当 l 1 时 l - 1 0BIT 的循环条件x 0会自然退出不需要特判。数值类型方面如果数组长度到 1e6、每次赋值到 1e9区间和可能超过 int。BIT 内部数组、查询返回值、add 的参数全部用 long long不要只想着省内存。树状数组这套模板在你真正比赛时不会留给你慢慢调类型的时间一开始就写长整型最稳妥。6. 最后聊点选择上的经验6.1 一句话判断该用哪个工具遇到区间操作题先问自己一个问题某个位置在整个过程中会被有效处理几次如果只会被处理一次、后面都是跳过优先想区间并查集如果需要反复修改、反复查询优先想树状数组。如果你发现题目两头都有那就按第四节的方式把它们组合起来而不是纠结“用哪个更好”。二分法判断逻辑可以简化成一张小表需求描述首选工具倒序染色、区间去重、每个点只赋值一次区间并查集单点修改、区间求和树状数组区间加、区间求和树状数组差分版区间覆盖加实时求和、每个点只处理一次区间并查集 树状数组区间最大值、区间翻转等复杂维护线段树或平衡树6.2 三个让我少走弯路的小习惯第一所有涉及区间的数据结构模板开数组时多开几位比如 n 5避免各种边界问题。第二写完模板后先在一组小数据上跑一遍手工验证特别是左边界、右边界、单点区间这三种情况都要覆盖到。第三如果真的在线上调试优先检查并查集 find 返回的值是否符合预期因为 BIT 出错多数是逻辑短路并查集出错往往是语义没理清。我记得有一次线上比赛被一道区间染色题卡了很久不是因为写法不会而是忘了在每次 update 前重新执行x find(l)以为 l 是新的就一定有空位结果左侧区间已被整体处理过程序卡在同一个位置反复跳。踩过这次坑之后我把区间并查集的循环模板固定成“先 find再判界再处理再跳跃”四步后来遇到同类题基本没有出过问题。代码量不大但细节密度很高值得你多写几遍把手感练出来。