浅谈线段树分治

xiao7_Mr_10_ · 2025-03-25 17:09:01 · 个人记录

引入

线段树分治，本质上是离线问题与线段树的结合，在算法竞赛中也常有出现，用于快速维护某些时间段的信息。这种思想的出现替代了很多动态数据结构，比如说 LCT（动态树的一种，是用 Splay 树维护树的轻重链剖分的算法，可以高效支持连边和断边操作，并快速维护路径信息，缺点是不能有效维护子树信息）。

经典选讲

这一部分介绍了线段树分治的经典例题，以及常用的可撤销数据结构。

连通性问题

我们先以例题 P2147 展开。

题目大意: 给你一个 n 个点的无向图，初始图内没有边。你需要支持加一条边，断一条边，查询两点连通性这三个操作。

维护动态图连通性在算法竞赛一直都是一个非常困难的问题，当然也有能够在线维护的算法(HLT，这是一种通过对图分层并配合动态树维护无向图连通性问题的一种算法，能够在删边加边的情况下高效维护整张图的连通性)。但是题目没有要求我们在线，所以我们可以离线处理问题。

我们把操作序列看做一个时间轴，第 i 个操作在第 i 刻发生，将加边和删边操作转化一下，转化为维护每条边出现的时间段。现在我们的问题在于如何维护某个时刻整张图的联通性。

回想一下线段树的原理：一个询问或修改会被拆成 \log n 个区间，维护这些区间从而降低时间复杂度。

同理，我们可以用线段树维护这些边的出现时间段，线段树上每个节点用一个 vector 存边，把一个区间按线段树的拆分方法拆分为 \log n 个区间，这样总空间复杂度就被限制到了 O(n \log n) 级别。

然后考虑怎么处理询问答案，我们发现对于时刻 i，出现的边是线段树上所对应的叶节点到根节点的路径上的所有边。很好理解，和线段树单点查询的原理一样，只不过是把信息换成了边。

所以我们可以直接递归搜索这颗线段树，进入节点 u 时我们加入这个节点所存的所有边，退出节点 u 时我们删除这个节点的边。只要能维护连通性，问题就得以解决。

维护连通性我们不难想到并查集，但是普通并查集不支持删边。我们回想刚刚的算法过程：对这棵树做深度优先搜索。如果把目前的边集看做队列 S，本质上退出节点 u 时，u 所存的边实际上都在 S 的队尾。实际上，我们发现需要执行的是若干次类似退队操作而不是删除操作，换句话说我们需要撤销最后一次操作带来的影响。

而并查集撤销是好做的，我们只用按秩合并，然后用一个栈来维护合并操作信息所带来的影响 (x,y)，其中 (x,y) 表示把 x 的父亲改成了 y。撤销时只需要把 x 的父亲改成 x 即可，并且退栈。

综上，我们已经能够在离线的情况下维护无向图连通性。算法流程如下:

1. 预处理所有边出现的时间段，并将其插入线段树中。

2. 遍历整棵线段树，进入节点 u 时并查集合并对应边集合

3. 在递归到叶节点时回答询问，注意不要直接退出，因为我们还没有撤销该节点的边信息。

4. 在递归回溯后撤销节点 u 的边信息，具体实现可以在加边前记录操作栈的大小 last，然后退栈直到栈的大小等于 last。

5. 输出所有询问对应答案。

我们来分析一下算法的时空复杂度：空间复杂度是 O(m \log m) 的，因为一共有 m 条边，把其中一条拆分成了 \log m 级别，总量就是 O(m \log m)。时间复杂度是 O(m \log m^2) 的，因为加入和删除边的量级是 O(m \log m) 且每条边只会把加入或删除一次，加入一次需要 O(\log m) 的时间复杂度，所以总量是 O(m \log m^2)。

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct Point{
    int x,y;
    bool operator <(const Point &a)const{
        return x==a.x?y<a.y:x<a.x;
    }
};
vector <Point> e[N<<1];
map <Point,int> mp;
string x;
struct ques{
    int op,x,y;
}wt[N];
int n,m,f[N],siz[N],s[N],top,ans[N];
void insert(int x,int l,int r,int s,int t,Point k){
    if(l>=s&&r<=t){
        e[x].push_back(k);
        return;
    }
    int mid=(l+r)>>1;
    if(s<=mid)insert(x<<1,l,mid,s,t,k);
    if(t>mid)insert(x<<1|1,mid+1,r,s,t,k);
}
int getf(int u){
    if(f[u]==u)return u;
    return getf(f[u]);
}
void merge(int x,int y){
    x=getf(x),y=getf(y);
    if(siz[x]<siz[y])swap(x,y);
    s[++top]=y;
    if(x!=y)siz[x]+=siz[y];
    f[y]=x;
}
void del(){
    int x=s[top];
    if(top==0)return;
    if(x!=f[x])siz[f[x]]-=siz[x];
    f[x]=x;
    top--;
}
void dfs(int x,int l,int r){
    int last=top;
    for(int i = 0;i < e[x].size();i++)merge(e[x][i].x,e[x][i].y);
    if(l==r){
        if(ans[l]){
            if(getf(wt[l].x)==getf(wt[l].y)) cout << "Yes\n";
            else cout << "No\n";
        }
    }
    else{
        int mid=(l+r)>>1;
        dfs(x<<1,l,mid);
        dfs(x<<1|1,mid+1,r);
    }
    while(last<top)del();
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)siz[i]=1,f[i]=i;
    for(int i = 1;i <= m;i++){
        cin >> x >> wt[i].x >> wt[i].y;
        if(x[0]=='C')wt[i].op=1;
        else if(x[0]=='D')wt[i].op=2;
        else wt[i].op=3;
    }
    for(int i = 1;i <= m;i++){
        if(wt[i].x>wt[i].y)swap(wt[i].x,wt[i].y);
        Point ed=(Point){wt[i].x,wt[i].y};
        if(wt[i].op==1)mp[ed]=i;
        if(wt[i].op==2){
            insert(1,1,m,mp[ed],i-1,ed);
            mp[ed]=-1;
        }
        if(wt[i].op==3)ans[i]=1;
    }
    for(int i = 1;i <= m;i++){
        Point ed=(Point){wt[i].x,wt[i].y};
        if(mp[ed]!=-1&&wt[i].op==1){
            insert(1,1,m,mp[ed],m,ed);
        }   
    }
    dfs(1,1,m);
    return 0;
}

可以发现，实际上线段树分治可以配合任何可以支持回溯操作的数据结构，可撤销数据结构的范围广泛于可持久化数据结构，因此线段树分治算法可以解决很多可持久化数据结构解决不了的问题。

而对于不同的数据结构，其应用在线段树分治上的空间复杂度为 O(n \log n \times t)，其中 t 的撤销时所带来的空间消耗，一般 t=1。而时间复杂度为 O(n \log n \times r)，其中 r 是撤销时所带来的时间消耗，一般是 \log 级别的。

其他问题

线段树分治其实一般都是辅助可撤销数据结构处理离线问题的，比如我们可以用可持久化 01-Tire 来维护某个时间段内的信息，又或者说可以用 LCT(动态树) 来维护最小生成树。本质上这类问题的难点只在于分析时间轴的实际意义以及维护数据结构。

例题

这里给出一个题单，里面有 luogu 上几乎所有的线段树分治例题。

相关链接

浅谈分治系列算法

浅谈 CDQ 分治