线段树与离线询问

专题 / segment-tree-offline

本地源文件：docs/topic__segment-tree-offline.md

线段树与离线询问

线段树与离线询问结合的问题在 OI 领域也有出现．这种技巧又被称为线段树分治．

假如你需要维护一些信息，这些信息会在某一个时间段内出现，要求在离线的前提下回答某一个时刻的信息并，则可以考虑使用线段树分治的技巧．

实际上线段树分治常有以下用途：

  1. 用原本不支持删除但是支持撤销的数据结构来模拟删除操作．如朴素的并查集无法高效支持删边操作．
  2. 不同属性的数据分别计算．如需要求出除了某一种颜色外，其他颜色数据的答案．

如果大家现在不明白没有关系，这两种用途我们都会在例题中阐述．

过程

首先我们建立一个线段树来维护时刻，每一个节点维护一个 vector 来存储位于这一段时刻的信息．

插入一个信息到线段树中和普通线段树的区间修改是类似的．

然后我们考虑如何处理每一个时间段的信息并．考虑从根节点开始分治，维护当前的信息并，然后每到一个节点的时候将这个节点的所有信息进行合并．回溯时撤销这一部分的贡献．最后到达叶子节点时的信息并就是对应的答案．

如果更改信息的时间复杂度为 𝑂(𝑇(𝑛))O(T(n))，可以通过设置一个栈保留更改，以 𝑂(𝑇(𝑛))O(T(n)) 的时间复杂度撤销．撤销不维持均摊复杂度．

整个分治流程的总时间复杂度是 𝑂(𝑛log⁡𝑛(𝑇(𝑛) +𝑀(𝑛)))O(nlog⁡n(T(n)+M(n))) 的，其中 𝑂(𝑀(𝑛))O(M(n)) 为合并信息的时间复杂度，空间复杂度为 𝑂(𝑛log⁡𝑛)O(nlog⁡n)．

实现

---|---

## 例题

[luogu P5787 二分图/【模板】线段树分治](https://www.luogu.com.cn/problem/P5787)

你需要维护一个 𝑛n![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 个点 𝑚m![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 条边的无向图．第 𝑖i![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 条边为 (𝑥𝑖,𝑦𝑖)(xi,yi)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)，出现的时刻为 [𝑙𝑖,𝑟𝑖)[li,ri)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)，其余时刻消失．

对于每一个时刻，若此时该图为二分图，输出 `Yes`，否则输出 `No`．

解题思路

使用种类并查集来维护一个图是否是二分图，然后就可以套用线段树分治了．

注意可撤销的并查集不能路径压缩，只能按秩合并．

参考代码

---|---

颜色限制 restriction

一个 𝑛n 点 𝑚m 边的无向图，有 𝑘k 种颜色编号为 0 ∼𝑘 −10∼k−1，每条边有一种颜色．

对于每种颜色，请判断假如删去所有这种颜色的边，得到的图是否连通？是否是一棵树？

输出满足删去后图连通的颜色数和删去后图是树的颜色数．

解题思路

对于每一种颜色，建立一个时间，在这个时间内没有这个颜色的边，其他边都有．用一个并查集维护一下即可．

参考代码

---|---

[luogu P4219 [BJOI2014] 大融合](https://www.luogu.com.cn/problem/P4219)

需要维护一个 𝑛n![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 个点的森林，初始时是散点．

有 𝑞q![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 个操作，支持：

  * `A x y` 连边 (𝑥,𝑦)(x,y)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．
  * `Q x y` 输出经过边 (𝑥,𝑦)(x,y)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的路径数．

允许离线．

解题思路

考虑允许离线，因此可以想到线段树分治．

然后考虑如何支持 Q 操作．如果不存在 (𝑥,𝑦)(x,y)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 这条边，答案就是 𝑥x![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 所在连通块大小乘上 𝑦y![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 所在连通块大小．可以用并查集维护．

因此你可以将 Q 拆成三个时间 𝑘 −1,𝑘,𝑘 +1k−1,k,k+1![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．其中 𝑘 −1k−1![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 是这条边的终止时刻，𝑘 +1k+1![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 是这条边的起始时刻．这样 𝑘k![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 就没有这条边，正好回答询问．

参考代码

---|---

[luogu P2056 [ZJOI2007] 捉迷藏](https://www.luogu.com.cn/problem/P2056)

出一个 𝑛n 个点的树，每个点有黑白两种颜色．初始时每个点都是黑色的．𝑞q 次操作，支持：

  • C x 将第 𝑥x 个点的颜色反转．
  • G 询问树上两个黑色点的最远距离．特别地，若不存在黑色点，输出 −1−1．

允许离线．

解题思路

首先考虑如何维护树上点集的直径，有下面的推论：

对于一个集合 𝑆S 和只有一个点的集合 {𝑃}{P}．若集合 𝑆S 的直径为 (𝑈,𝑉)(U,V)．则点集 𝑆 ∩{𝑃}S∩{P} 的直径只可能为 (𝑈,𝑉),(𝑈,𝑃)(U,V),(U,P) 或 (𝑉,𝑃)(V,P)．

然后考虑解决原问题．我们可以考虑维护黑色点集，维护每一个点在黑色点集中的若干个时间段（具体你开一个桶记录一下上一次进入黑色点集的时刻即可）．

然后就自然地想到离线，将所有时间刻插入到线段树中．然后在线段树上分治，每次线段树上的点会记录当前时间段点集新增的点，新增点可以使用上面的推论，找到新点集直径的两个端点．

撤销是平凡的，开一个栈记录一下直径端点的变化即可．

参考代码

---|---

## 习题

  * [CF601E A Museum Robbery](https://codeforces.com/problemset/problem/601/E) 线段树分治 + 背包 dp．
  * [CF19E Fairy](https://codeforces.com/problemset/problem/19/E) 线段树分治 + 种类并查集．
  * [luogu P5227 [AHOI2013] 连通图](https://www.luogu.com.cn/problem/P5227) 线段树分治 + 并查集．
  * [luogu P4319 变化的道路](https://www.luogu.com.cn/problem/P4319) 线段树分治 + Link Cut Tree 维护最小生成树．
  * [luogu P3733 [HAOI2017] 八纵八横](https://www.luogu.com.cn/problem/P3733) 线段树分治 + 线性基．

**本页面部分内容参考自博文[Deleting from a data structure](https://cp-algorithms.com/data_structures/deleting_in_log_n.html)，版权协议为 CC-BY-SA 4.0．**

* * *

>  __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/topic/segment-tree-offline.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/topic/segment-tree-offline.md "edit.link.title")
>  __本页面贡献者：[Tiphereth-A](https://github.com/Tiphereth-A), [xiezheyuan](https://github.com/xiezheyuan), [c-forrest](https://github.com/c-forrest), [Enter-tainer](https://github.com/Enter-tainer), [aofall](https://github.com/aofall), [CoelacanthusHex](https://github.com/CoelacanthusHex), [Great-designer](https://github.com/Great-designer), [Kensuke-Hinata](https://github.com/Kensuke-Hinata), [Marcythm](https://github.com/Marcythm), [Persdre](https://github.com/Persdre), [shuzhouliu](https://github.com/shuzhouliu), [TOMWT-qwq](https://github.com/TOMWT-qwq)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用