大体思想
线段树分治是一种用于解决区间操作和时间点查询的算法。它的主要思想是以时间为下标建立线段树，将在某一时间段内生效的操作记录在线段树上，然后对于某一时间点的查询，可以直接从线段树上得到结果。线段树是一种容易维护区间的数据结构，它通过不断以中点分治区间，形成了 \(log\) 层的树形结构。————————————————————————————————————baidu
类似一边分治，同时还代表线段树。
具体用法
在时间段中搞事情
搞什么？
将时间段加入线段树中。
在区间查询中搞事情
搞什么？
搞很多事情。
例题
二分图 /【模板】线段树分治
考虑直接将时间加入线段树，但是这里的线段树需要用vector来存当前区间内不会消失的边，再来判断二分图。
我们知道二分图的性质就是不存在奇环，但是直接使用平凡的 01染色 肯定就 TLE 了，考虑可撤销并查集（不能用普通并查集是因为在回溯的时候存在需要撤销之前的操作）维护，如果发现一条边在未加入前，其两点在并查集中在一个集合，那么就存在奇环（这个很显然吧）。
#include <bits/stdc++.h>
using namespace std;
#define il inline
#define pb(x) push_back(x)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
const int N=2e5+5;
int n,m,k;
struct node
{
int u,v;
}e[N];
stack<pii>s;
namespace dsu //并查集
{
int fa[N],h[N];
il void init(){for(int i=1;i<=n*2;i++)fa[i]=i,h[i]=0;}
il int getf(int x)
{
if(x==fa[x])return x;
return fa[x]=getf(fa[x]);
}
il void merge(int u,int v)
{
u=getf(u),v=getf(v);
if(u==v)return;
if(h[u]>h[v])swap(u,v);
s.push(mp(u,h[u]==h[v]?1:0));
fa[u]=v;
h[v]+=(h[u]==h[v]?1:0);
}
}
namespace tr //线段树
{
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid ((l+r)>>1)
vector<int>t[N<<2];
il void upd(int p,int l,int r,int L,int R,int id)
{
if(r<L||R<l)return;
if(L<=l&&r<=R){t[p].pb(id);return;}
upd(ls,l,mid,L,R,id);upd(rs,mid+1,r,L,R,id);
}
il void solve(int p,int l,int r)
{
int flag=1,now=s.size();
for(int x:t[p])
{
int fu=dsu::getf(e[x].u),fv=dsu::getf(e[x].v);
if(fu==fv)
{
for(int i=l;i<=r;i++)cout<<"No\n";
flag=0;
break;
}
dsu::merge(e[x].u+n,e[x].v);
dsu::merge(e[x].u,e[x].v+n);
}
if(flag)
{
if(l==r)cout<<"Yes\n";
else{solve(ls,l,mid);solve(rs,mid+1,r);}
}
while(s.size()>now)
{
dsu::h[dsu::fa[s.top().fi]]-=s.top().se;
dsu::fa[s.top().fi]=s.top().fi;
s.pop();
}
}
}
int main()
{
cin>>n>>m>>k;
for(int i=1,l,r;i<=m;i++)
{
cin>>e[i].u>>e[i].v>>l>>r;
if(l^r)tr::upd(1,1,k,l+1,r,i);
}
dsu::init();
tr::solve(1,1,k);
return 0;
}