线段树分治总结

2024.12.21 update: fix formula.

以前曾经写过一个总结，但写得超级烂，于是再写一个。

以下都是口胡的，可能有不正确的地方请求指点 QAQ。

首先我们要理解线段树（现在指狭义的线段树）是什么。

线段树是一种容易维护区间的数据结构，是一种区间分治实体化的产物。

准确来说，比如你维护区间 [L,R]，其实就可以不断以中点分治下去。由于每次分治区间长度都会除以 2，所以最多分治 \log 层，就形成了线段树。

那么线段树分治指什么呢？

实际上是一种维护时间区间的数据结构，同样是利用线段树的分治性，让复杂度保证在了 \log 级别。

但是，维护时间区间的东西还有很多，比如 CDQ 分治，比如 KD-Tree，这一类数据结构都能维护时间区间，那线段树分治的特殊作用在哪里呢？实际上，一般而言，它的作用就是支持撤销操作，或者说就是维护了一个操作影响的时间区间，这是 CDQ 分治等不容易做到的，是它这种结构的特殊优势所在。

我们考虑如何维护一个操作影响的时间区间。假设一个操作影响的时间是 [L,R]，将其呈现在线段树上就会变成 \log 段影响区间，那么对于一个询问，我们只要在线段树上找这个询问所在时间点，把根到叶子路径上的所有影响计算一遍，就能得出这个询问的答案。我们稍微估计一下复杂度，假设有 N 种操作，算 S 种操作的影响的复杂度是 f(S)。那么一次询问的复杂度就大概是 O(f(N))。好像这种复杂度不太行，那我们再优化一下。我们把询问也插入到线段树里。每次递归整棵线段树，对于一个结点就直接计算影响，并改变插入到这个节点的询问答案。这样的复杂度就变成 O(\sum f(i)) 即 O(f(N\log N)) ，保证了复杂度。

这样干说好像没什么用，来看几道例题。

[CTSC2016]时空旅行

题意：你要维护若干个集合，每个集合都是有一个编号比他小的集合扩展而来，扩展内容为加入一个新的元素 (x,c) 或者删除一个已有元素。集合的扩展关系之间构成一个树形结构。有 m 次询问，每次给出一个 X，询问第 s 个集合中 (x-X)^2+c 的最小值。（题意剽的）

询问和操作级别都是 n，n\leq 5\ast 10^5。

题解：这是一道非常经典的线段树分治的题。将树形结构建出来后，可以发现的是一个元素就是它第一次出现的点的子树中扣掉把它删除的点的子树，即可以看做一段连续的区间(dfs 序)。我们把这个东西看做影响的时间区间，丢到线段树上，考虑如何对于一个查询计算答案。我们在线段树上的每个结点维护关于 (x-X)^2+c 的凸壳（半平面交或者单调栈），然后把询问都插入到线段树里，递归整棵线段树即可得到答案。关于维护这个凸壳有两种想法，一种是直接维护，那就要带一个 \log。更优秀的办法是在插入之前直接按凸壳的先后顺序排好，再插入，这样可以去掉 \log，f(S) 就会等于 O(S)，于是总复杂度就保证在了 O(n\log n)。

[FJOI2015]火星商店问题

题意：有 n 家商店，操作使 s 号商店在第 i 天进一个价值为 val 的货物（当日就会卖掉），询问是给出一个数 x，在 [l,r] 天里 [L,R] 号商店与 x 异或最大的 val 是多少。每个商店都会有个永远的货物。

询问和操作级别都是 n，n\leq 10^5,val,x\leq 10^5

题解：这也是一道经典的线段树分治的题。它与上题的区别，一是计算操作影响的方式，这题需要Trie树。另一方面，这题变成了询问时间区间，操作是单点的。同样的思路，对于询问，我们把它询问的时间区间插入到线段树上，操作也插入到线段树上，同样的递归处理，由于每个询问依旧会得到操作的影响，所以复杂度和正确性依旧可以保证。具体实现的话，每次递归到一个结点，对于 n 个商店建一棵可持久化 Trie 树，这就能处理 [L,R] 的问题了，f(S)=S\log x，总复杂度是 O(n\log n\log x)。

[CF938G]Shortest Path Queries

题意：给出一个连通带权无向图,边有边权,要求支持 q 个操作:

1、x,y,d: 在原图中加入一条 x 到 y 权值为 d 的边.

2、x,y: 把图中 x 到 y 的边删掉

3、x,y: 表示询问 x 到 y 的异或最短路

保证任意操作后原图连通无重边自环且操作均合法

图的点数和边数级别为 n，n,q\leq 2\ast 10^5,d\leq 2^{30}-1

题解：这也算是一道线段树分治的经典题了。这题与上面两题其实没有太大的区别，更多的是作为一道线段树分治的熟悉/练手题来做。线段树维护时间轴，将每一条边的影响区间插入到线段树上，然后把询问也插入到线段树上，递归整棵线段树就可以了。具体实现上，利用并查集和线性基，由于这里并查集无法压缩（因为并查集上的每条边维护了边权），所以按秩合并。在递归回来的时候，利用可撤销并查集的性质，撤销之前区间的影响即可。这样的 f(S)=S\log S\log d，总复杂度就是 O(n\log^2n\ast \log d)。

[CF576E]Painting Edges

题意：给你一张 n 个点，m 条边的无向图，每条边是 k 种颜色中的一种，满足所有颜色相同的边内部形成一个二分图。有 q 个询问，每次询问给出 a,b 代表将编号为 a 的边染成颜色 b，但如果染色后不能满足所有颜色相同的边内部都是二分图就不染。问你每次是否能染成功。

n,m,q\leq 5\ast 10^5,k\leq 50

题解：这并不是一道线段树分治的经典题。这题有个难点，就是染色后的判断，判断出来后可能撤销这次操作，导致了每条边的存在时间不固定。众所周知，二分图判断可以用奇环，奇环可以利用并查集。问题是如何固定来保证正确性和复杂度的正确性。有一种优秀的做法就是利用线段树分治的思想，我们将修改操作影响的区间定义为从现在开始到下次这条边修改的时间区间，然后插入到线段树里。然后每次递归到某个时间点 i 时，判断是否构成二分图，如果没有，撤销时间点 i 时的操作。这样的话，递归回去的时候就可以保证每次判断的正确性以及真正的影响区间，于是就做好了。具体实现的话可以对每个颜色写个可撤销并查集，每次撤销和递归的时候都撤销回来，f(S)=S\log S，总复杂度是 O(n\log n\log S)。

下面再给出几道题：

[HAOI2017]八纵八横

[SHOI2014]神奇化合物

[APIO2018]New Home 新家

[CF678F]Lena and Queries

[bzoj4311]向量

[bzoj4184]shallot

最后给出一种模板（其实我感觉没什么用):

void insertmodify(res rt,res l,res r,res L,res R,SEG id){
    if(L<=l&&R>=r){
        f[rt].push_back(id);
        return;
    }
    if(l==r)return;
    res mid=(l+r)>>1;
    if(L<=mid)insertmodify(rt<<1,l,mid,L,R,id);
    if(mid<R)insertmodify(rt<<1|1,mid+1,r,L,R,id);
}
void insertquery(res rt,res l,res r,res p,QUE id){
    g[rt].push_back(id);
    if(l==r)return;
    res mid=(l+r)>>1;
    if(p<=mid)insertquery(rt<<1,l,mid,p,id);
    else insertquery(rt<<1|1,mid+1,r,p,id);
}
void segdiv(res rt,res l,res r){
    solve(f[rt],g[rt]);
    if(l==r){get(l);return;}
    res mid=(l+r)>>1;
    segdiv(rt<<1,l,mid),segdiv(rt<<1|1,mid+1,r);
}

总结：线段树分治作为一种较为优秀的维护时间轴的数据结构，在很多功能上它或许不如 CDQ 分治这种可以缩小数据规模的数据结构，但无疑在撤销操作上它已经登峰造极了。（雾

在最后，表示上面全在口胡，有错误请各位指出（鞠躬