外观
Skip to content 查看源代码：
查看源代码：
segment-tree-divide-and-conquer.md
---
title: 线段树分治
createTime: 2025/8/20
categories:
- IT
tags:
- OI
- OI-note
---
线段树分治常常用来解决以下问题：
> **修改只在某一个时间区间上成立，但是维护的数据不支持随机删除，只能支持撤销最新操作。**
这个时候，以时间顺序模拟就会失效。**此时，我们在时间轴上建一棵线段树，就可以把每个操作的事件区间放到线段树的节点上。**
{width=487 height=419 style="margin: 0 auto; display: block;"}
**接下来对这棵线段树进行 dfs，就可以在 dfs 的路上顺便执行修改与撤销。在叶节点统计答案即可。**
设询问区间个数为 $q$，时间轴长度与 $q$ 同级（否则可以离散化），单次操作/撤销复杂度为 $T$，则把区间放到树上的时间复杂度为 $O(q \log q)$，dfs 的时间复杂度为 $O(Tq)$。
## 热身：[P4588 [TJOI2018] 数学计算](https://www.luogu.com.cn/problem/P4588)
:::note 题意
维护一个数 $x$，初始为 $1$，两种操作：
1. $x \gets x \times m \mod M$
2. 移除第 $p$ 个操作，保证必为操作 1，且每个操作至多移除一次
（不模 $M$ 的值极大，不可维护，且 $M$ 为合数）
:::
发现由于 $M$ 为合数，不能做除法，也就不能实现随机删除。
所幸我们可以用一个栈记录历史值，实现撤销最新操作。因此可以用线段树分治。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxq=1e5+100;
int M, m[maxq];
int ans[maxq];
struct segt {
vector<int> op[maxq * 4];
stack<int> X;
inline int lc(int x) { return x << 1; }
inline int rc(int x) { return (x<<1)|1; }
inline int md(int x, int y) { return (x+y)>>1; }
void add_op(int tn, int tl, int tr,
int x, int y, int opi) {
if (tl > y || tr < x) {
return;
}
if (x <= tl && tr <= y) {
op[tn].push_back(opi);
return;
}
int mid = md(tl, tr);
add_op(lc(tn), tl, mid, x, y, opi);
add_op(rc(tn), mid+1, tr, x, y, opi);
}
void dfs(int tn, int tl, int tr) {
for (int opi: op[tn]) {
X.push(((ll)X.top()) * m[opi] % M); // 不开__见祖宗
}
if (tl == tr) {
ans[tl] = X.top();
} else {
int mid = md(tl, tr);
dfs(lc(tn), tl, mid);
dfs(rc(tn), mid+1, tr);
}
for (int _: op[tn]) {
// 按道理是要反转的，但是 pop 不用参数，调用次数对就行
X.pop();
}
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
segt segtree; // 这就是我的多测路线！
segtree.X.push(1);
int q;
cin >> q >> M;
set<int> alive;
for (int i=1; i<=q; i++) {
int op;
cin >> op;
if (op == 1) {
cin >> m[i];
alive.insert(i);
} else {
int pos;
cin >> pos;
segtree.add_op(1, 1, q, pos, i-1, pos);
alive.erase(pos);
}
}
for (int pos: alive) {
segtree.add_op(1, 1, q, pos, q, pos);
}
segtree.dfs(1, 1, q);
for (int i=1; i<=q; i++) {
cout << ans[i] << '\n';
}
}
return 0;
}
```
## 维护并查集：[P5227 [AHOI2013] 连通图](https://www.luogu.com.cn/problem/P5227)
:::note 题意
给定一张图，$k$ 次询问，每次询问给出 $c\le4$ 条边，问如果删除这些边，图是否仍然连通。
:::
判断连通可以使用并查集，但是发现不能删边，只能加边。
正难则反，一条边在某些时刻被删除，相当于它会在若干个时间区间内存在。
于是维护一个可撤销并查集[+可撤销并查集]，在这些时间区间上做一次线段树分治即可。
[+可撤销并查集]:
只需用栈记录每次合并的两个根即可实现撤销。
**注意**：可撤销并查集不能使用路径压缩，但是可以使用按秩合并。
由于拆出来的区间不会超过 $(m+ck)$ 个，时间复杂度 $O\bigl( (m+ck) \log k + k \log n \bigr)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+100, maxm=2e5+100;
int n, m, k;
int u[maxm], v[maxm];
bool ans[maxn];
struct history {
int x, y;
};
struct undo_dsu {
int siz[maxn], fa[maxn];
history s[maxm];
int st;
int part;
void init(int n) {
st = 0;
part = n;
for (int i=1; i<=n; i++) {
siz[i] = 1;
fa[i] = i;
}
}
inline int find(int x) {
while (x != fa[x]) {
x = fa[x];
}
return x;
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) {
s[++st] = {0, 0};
return;
}
if (siz[fx] < siz[fy]) {
swap(fx, fy);
}
siz[fx] += siz[fy];
fa[fy] = fx;
part--;
s[++st] = {fx, fy};
}
void undo() {
if (s[st].x == 0) {
st--;
return;
}
int fx=s[st].x, fy=s[st].y;
st--;
fa[fy] = fy;
siz[fx] -= siz[fy];
part++;
}
} dsu;
struct segt {
vector<int> record[maxn*4];
inline int lc(int x) { return x<<1; }
inline int rc(int x) { return (x<<1)|1; }
inline int md(int x, int y) { return (x+y)>>1; }
void add(int tn, int tl, int tr, int x, int y, int ei) {
if (tl > y || tr < x) {
return;
}
if (x <= tl && tr <= y) {
record[tn].push_back(ei);
return;
}
int mid = md(tl, tr);
add(lc(tn), tl, mid, x, y, ei);
add(rc(tn), mid+1, tr, x, y, ei);
}
void dfs(int tn, int tl, int tr) {
for (int ei: record[tn]) {
// printf("in [%d..%d], merge #%d (%d-%d)\n", tl, tr, ei, u[ei], v[ei]);
// printf("\tnow #parts: %d\n", dsu.part);
dsu.merge(u[ei], v[ei]);
}
if (tl == tr) {
ans[tl] = (dsu.part == 1);
} else {
int mid = md(tl, tr);
dfs(lc(tn), tl, mid);
dfs(rc(tn), mid+1, tr);
}
for (int _=0; _<record[tn].size(); _++) {
dsu.undo();
}
}
} segtree;
int last_delete[maxm]; // 0
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i=1; i<=m; i++) {
cin >> u[i] >> v[i];
}
dsu.init(n);
cin >> k;
for (int t=1; t<=k; t++) {
int c;
cin >> c;
while (c--) {
int ei;
cin >> ei;
segtree.add(1, 1, k, last_delete[ei]+1, t-1, ei);
last_delete[ei] = t;
}
}
for (int i=1; i<=m; i++) {
if (last_delete[i] != k) {
segtree.add(1, 1, k, last_delete[i]+1, k, i);
}
}
segtree.dfs(1, 1, k);
for (int i=1; i<=k; i++) {
cout << (ans[i]? "Connected\n": "Disconnected\n");
}
return 0;
}
```