别样的线段树大战

· · 算法·理论

前言

偶遇线段树强如怪物，拼尽全力终于战胜。于是就有了这篇学习笔记大合集。

目前聚集了大部分我认为较为常考的进阶线段树知识。文章较长，如果有误请告诉我。

大部分题目的完整代码在这里

更新

应该会长久更新，例如添加更多例题和算法。

2022.12.19：先整合了一下已经写完的部分，其实大部分已经可以看了。

线段树上二分

模板题

给定一个序列，多次询问求 [l,r] 中第一个大于 v 的位置。可以附带上若干操作。

基础的想法是二分这个位置 p，然后查询 [l,p] 的最大值与 v 比较，O(q\log^2n)。

然后再考虑假如询问 [1,n] 怎么做。假设现在递归到 [l,r]（答案在这个区间内），则可以看 [l,mid] 的最小值，因为这里的 [l,mid] 是一个完整的区间所以查询是 O(1) 的。如果其小于 v 说明答案肯定在右边的子区间，否则在左边。每次只会往一个方向递归下去，线段树最大深度级别是 log 的，所以整体复杂度也是 log 的。

如果询问在 [l,r]，一种写法是需要多考虑一些细节，除去在询问区间外的部分即可，一次 dfs 即可完成。

另一种（个人常用）是先 dfs 找出完全包含的这几个区间（共 log 个），然后按顺序扫描每一个，如果遇到某个区间第一个满足条件就递归进去，后面的直接 break 掉。这样的好处是不用处理 corner case，而且遇到较为复杂的线段树二分也能处理。

线段树维护单调栈

楼房重建

给你一个序列 a，支持单点修改。每次修改后求出前缀最大值的数量。

考虑如何在线段树上维护这个东西。我们记 mx,ans 分别代表区间的最大值和区间前缀最大值的数量（即答案）。

考虑如何 pushup，我们分为左右区间考虑，首先左区间的前缀最大值肯定全部都会选到，而右区间由于还需要满足大于左区间的 mx，所以我们需要快速求出区间内大于某个值的前缀最大值数量。

前缀最大值肯定是单调增的，也就是说选出来的是一段后缀。我们发现这个东西可以使用线段树上二分解决。具体地，现在查询值大于 v 的前缀最大值数量：

il int qry(int x,int l,int r,double v){
    if(l==r)return mx[x]>v; // 注意特判
    else if(mx[x]<v)return 0;
    int mid=(l+r)>>1;
    return (mx[x<<1]<v)?qry(x<<1|1,mid+1,r,v):(qry(x<<1,l,mid,v)+ans[x]-ans[x<<1]);
    // 这里使用 ans[x]-ans[x<<1] 的原因是右侧区间还需要满足前缀最大值大于左侧的。
}

发现每次只会从一侧递归下去，线段树二分的复杂度是 log 的。而每次 pushup 时都要进行一次线段树二分，整体的复杂度就是 O(n\log^2n) 的。

il void upd(int x, int l, int r, int p, double v) {
    if(l==r)return mx[x]=v,ans[x]=1,void();
    int mid=(l+r)>>1;
    (p<=mid)?upd(x<<1,l,mid,p,v):upd(x<<1|1,mid+1,r,p,v);
    mx[x]=max(mx[x<<1],mx[x<<1|1]);
    ans[x]=ans[x<<1]+qry(x<<1|1,mid+1,r,mx[x<<1]);
}

区间维护单调栈的操作需要在 pushup 同时递归下去处理。

JSC2019Final-H Distinct Integers

题解文章传送门，本篇文章讲的更详细一点。

给定一个序列 a，q 次操作分别为单点修改和查询 [l,r] 内有多少子区间满足该区间内不存在相等的数。

对于值相等的题有一个套路：使用 set 维护 pre_i 表示上一个与 i 相等的值的下标。

考虑将点 i 作为右端点有多少个满足条件的区间。先处理询问 [1,n] 的子区间有多少满足。

我们发现如果没有值不能相同的限制，显然有 i 的区间数就是 i。如果加入相同的限制呢？此时 i 的区间数为 i-\max_{j\le i}pre_j，也就是左端点不能小于前缀的 pre 最大值。

到区间 [l,r] 上，答案则为 \frac{(l+r)(r-l+1)}{2}-\sum_{i=l}^r\max_{j\le i}pre_j。我们只需要求出区间内前缀最大值的和即可。

首先看每个完整的区间怎么维护，和上一题类似，只不过本题需要维护的是最大值的和。

int mx[N*5];ll sum[N*5];
il ll getval(int x,int l,int r,int lim){
    if(l==r)return max(mx[x],lim);
    int mid=(l+r)>>1;
    if(mx[x<<1]<lim)return 1ll*(mid-l+1)*lim+getval(x<<1|1,mid+1,r,lim);
    else return getval(x<<1,l,mid,lim)+sum[x]-sum[x<<1];
}

那么遇到不完整的询问区间 [l,r] 呢？这里可以先把可行的区间拎出来。然后对于每个区间依次考虑，记录上个区间传下来的最大值即可。

struct Dat{int x,l,r;};
vector<Dat>v;
il void query(int x,int l,int r,int bg,int ed){
    if(bg<=l&&r<=ed){v.eb((Dat){x,l,r});return;}
    int mid=(l+r)>>1;
    if(bg<=mid)query(x<<1,l,mid,bg,ed);
    if(mid<ed)query(x<<1|1,mid+1,r,bg,ed);
}
il ll query(int bg,int ed){
    v.clear();query(1,1,n,bg,ed);
    ll sum=0;
    int premax=bg-1;
    forv(i,v.size()){
        sum+=getval(v[i].x,v[i].l,v[i].r,premax);
        premax=max(premax,mx[v[i].x]);
    }
    return sum;
}

这一步的复杂度也是两只 log 的。

线段树维护复杂信息

线段树基本上满足结合律的都可以维护，例如矩阵之类。

区间 gcd

给你一个字符串，多次询问给出 [l,r] 求满足 l\le a<b<c\le r 且 a,b,c 在字符串内分别为 gcd 的数量。

考虑合并两个区间时 gcd 的数量。首先左右子区间内的 gcd 都满足条件，且可能两侧区间合并会产生一些新的，此时有两种情况是 g+cd 和 gc+d。

然后变成如何维护 gc 和 cd 的数量，也是只要分别拆成从两侧来的和在中间组成的即可。

struct Node{ // 这类型题目封装后更方便一些。
    ll g,c,d,gc,cd,gcd;
    il friend Node operator+(Node x,Node y){
        Node ans;
        ans.g=x.g+y.g,ans.c=x.c+y.c,ans.d=x.d+y.d;
        ans.gc=x.gc+y.gc+x.g*y.c,ans.cd=x.cd+y.cd+x.c*y.d;
        ans.gcd=x.gcd+y.gcd+x.gc*y.d+x.g*y.cd;
        return ans;
    }
};

还有一些有关前后缀的题目。

小白逛公园

给你一个序列，求 \max_{L\le l\le r\le R}\sum_{i=l}^r a_i，支持单点修改和多次询问。

考虑 pushup 时最大子段和可以怎么贡献过来。首先两边分别的答案可以贡献。

然后左区间的后缀与右区间的前缀也可以拼起来产生贡献，由于两侧是独立的，那么我们需要分别知道一个区间的最大前缀和和最大后缀和。

以最大前缀和为例，其是左侧的最大前缀和与右侧的最大前缀和加上左侧全部和的最大值。

ans[x]=max(ans[l],ans[r],mxr[l]+mxl[r]);
mxl[x]=max(mxl[l],sum[l]+mxl[r]);
mxr[x]=max(mxr[r],sum[r]+mxr[l]);
sum[x]=sum[l]+sum[r];

势能线段树

A Simple Data Structure Problem V

单点修改，区间 a_x\gets\lfloor\ln a_x\rfloor，查询区间和。

考虑一种看似暴力的解法：建线段树，区间操作时如果该区间内所有数都已经变成 0（即无法进行操作）则剪枝跳过，否则暴力往两侧子区间递归。

但是这种做法其实是对的，因为我们发现一个数进行 \ln V 操作就变成 0 了，因此所有叶子节点加起来最多修改 O((n+m)\ln V) 次。每次修改的复杂度最多只能是 O(\log n)，所以整体的复杂度就是 O((n+m)\ln V\log n) 了。

那么如果有单点修改呢？单点修改每次只会修改一个点，而把这个点重新变为 0 需要 \ln V 次，每次复杂度为一只 log，所以整体复杂度还是两只 log 的。

il void upd(int x,int l,int r,int bg,int ed){
    if(sum[x]==0)return;// 重点
    else if(l==r)return sum[x]=(int)floor(log((long double)sum[x])),void();
    int mid=(l+r)>>1;
    (bg<=mid)?upd(x<<1,l,mid,bg,ed):void(),(mid<ed)?upd(x<<1|1,mid+1,r,bg,ed):void();
    sum[x]=sum[x<<1]+sum[x<<1|1];
}

类似的题目有很多：

吉司机线段树

节选自这篇文章，修改了一下。

区间取 min 区间和

给你一个序列，操作是对于区间内每个数进行 a_i\gets\min(a_i,v)，求区间和。

建立线段树，我们维护出一个区间的最大和严格次大值 mx1,mx2。分类讨论当前更新的值 val：

复杂度看 OI-wiki，单纯做是 O(m\log n) 的，加上其它标记然后下传是 O(m\log^2n) 的。和上文的道理是类似的。

CPU 监控 弱化版

区间加，求区间历史最大值。

首先看最基础的区间加，我们将一个加法标记（记为 \operatorname{add}_{val}）存入某个打懒标记的区间代表的操作序列中，此时我们就无需递归下去了。

操作序列可以分成两部分：一部分代表这个区间内的答案序列。第二部分则是懒标记序列。pushdown 时，我们将当前的懒标记序列接到子区间的答案序列后，然后清空当前的懒标记。

为了满足算法的复杂度要求，我们可以将操作序列压缩，对于加法操作有 \operatorname{add}_{a}+\operatorname{add}_{b}=\operatorname{add}_{a+b}。

在线段树上记一个 hmx 表示区间内的历史最大值，查询是常规的取 max，然后考虑如何更新。由于每次加法都是加全局（对于当前区间），所以全局最大值只需考虑区间当前 max 加上区间最大加 tag（从父节点继承来的懒标记），即 hmx\gets\max\{hmx,mx+mxtag\}

对于一段操作序列我们要记什么：sum 表示这段全部操作的和，mx 表示一个前缀的最大值。pushdown 的过程就是操作序列的合并过程，那么就有：

\begin{gather*} sum_{now}=sum_a+sum_b \\ mx_{now}=\max\{mx_a,sum_a+mx_b\} \end{gather*}

这个东西对于当前标记和懒标记都是适用的。

然后如果还有修改操作呢？发现先加法再赋值是不好合并的，因为值不确定。但是先赋值再加较为容易，因为当前值已知所以可以加法转赋值。这样子多维护一个赋值的 tag 和一个历史最大赋值（同理）就可以了。

线段树 3（区间最值操作、区间历史最值）

区间加、区间取 min，求区间和、最大值、历史最大值。

结合这两种方法，我们考虑对于区间取 min 如何转化成其它操作。

从加法角度，我们可以看作每次将最大值的集合加上 val-mx1，且这样 mx1 仍然是最大值。此时我们求区间取 min 区间最值操作只需维护成区间加区间取 min，维护最大的前缀加 tag 即可。这里的区间加全部只会加在 mx1 上。

如果加入区间加操作呢？我们发现此时其不在意数值的大小，即 mx1 和 mx2 都会加上 val。那么我们将最大值和次大值及以下分开考虑，每次操作变成选择其中一个集合加上值。由于除了整体加之外只会加最大值，所以最大值不会被次大值代替。

所以只需在 pushup 时找出最大次大值即可，如果还要维护 sum 也可以，只需要再找出子树内有多少个最大值，这些值按最大值的方式加，其它的按次大值方式加。

il void pushup(int x){
    sum[x]=sum[lc]+sum[rc];
    mx1[x]=max(mx1[lc],mx1[rc]),mxh[x]=max(mxh[lc],mxh[rc]);
    if(mx1[lc]==mx1[rc])mx2[x]=max(mx2[lc],mx2[rc]),mxc[x]=mxc[lc]+mxc[rc];
    else if(mx1[lc]>mx1[rc])mx2[x]=max(mx2[lc],mx1[rc]),mxc[x]=mxc[lc];
    else mx2[x]=max(mx1[lc],mx2[rc]),mxc[x]=mxc[rc];
}

是严格次大值所以需要判断多种情况。

il void update(int x,int l,int r,int mxa,int mxah,int a,int ah){
    sum[x]+=mxa*mxc[x]+a*(r-l+1-mxc[x]);
    mxh[x]=max(mxh[x],mx1[x]+mxah);
    mx1[x]+=mxa;if(mx2[x]!=-INF)mx2[x]+=a;
    mxaddh[x]=max(mxaddh[x],mxadd[x]+mxah),mxadd[x]+=mxa;
    addh[x]=max(addh[x],add[x]+ah),add[x]+=a;
}

这里 lazytag 加的顺序和上文的 sum_{now}=sum_a+sum_b,mx_{now}=\max\{mx_a,sum_a+mx_b\} 是对应的（这里的 sum 是懒标记的和，mx 是最大的懒标记前缀和）。

il void pushdown(int x,int l,int r){
    ll mx=max(mx1[lc],mx1[rc]),mid=(l+r)>>1;
    if(mx1[lc]==mx)update(lc,l,mid,mxadd[x],mxaddh[x],add[x],addh[x]);
    else update(lc,l,mid,add[x],addh[x],add[x],addh[x]);
    if(mx1[rc]==mx)update(rc,mid+1,r,mxadd[x],mxaddh[x],add[x],addh[x]);
    else update(rc,mid+1,r,add[x],addh[x],add[x],addh[x]);
    mxadd[x]=mxaddh[x]=add[x]=addh[x]=0;
}

这是因为当前的最大值不一定再某个子树内，如果不在就不能按最大值的方式加上，而是变成加其它值的方式。

动态开点线段树

是后面实现一些线段树操作的基础。

帕秋莉的魔导书

记 s_i 为 a_i 的前缀和，单点修改 a_i 和多次询问求 \sum_{i=l}^rs_i。下标范围是 [-2^{31},2^{31})

首先发现操作就是对一段后缀加和查询区间和，使用线段树维护。但是前缀和操作如果直接离散化后可能会出一些问题。所以使用动态开点线段树。

相对于常规的线段树，动态开点需要额外记录其左右儿子的编号。pushdown 时如果没有左右儿子则需要加上去。每次操作最多增加 log 个节点，空间复杂度 O(n\log q)。

struct Node{
    int sum,lazy,l,r;
    Node(){sum=lazy=l=r=0;}
}t[8000040];int tot=1;
#define add(x) ((x)?(x):(x=++tot))
il void pushdown(int x,int l,int r){
    if(!t[x].lazy)return;int mid=(l+r)>>1;
    add(t[x].l);add(t[x].r);
    t[t[x].l].lazy+=t[x].lazy,t[t[x].l].sum+=t[x].lazy*(mid-l+1);
    t[t[x].r].lazy+=t[x].lazy,t[t[x].r].sum+=t[x].lazy*(r-mid);
    t[x].lazy=0;
}
il void _upd(int x,int l,int r,int bg,int ed,int v){
    if(bg<=l&&r<=ed)return t[x].lazy+=v,t[x].sum+=v*(r-l+1),void();
    int mid=(l+r)>>1;pushdown(x,l,r);
    if(bg<=mid)_upd(add(t[x].l),l,mid,bg,ed,v);
    if(mid<ed)_upd(add(t[x].r),mid+1,r,bg,ed,v);
    t[x].sum=t[t[x].l].sum+t[t[x].r].sum;
}il void upd(int bg,int ed,int v){_upd(1,1,2147483647,bg,ed,v);}
il int _qry(int x,int l,int r,int bg,int ed){
    if(bg<=l&&r<=ed)return t[x].sum;
    int mid=(l+r)>>1,ans=0;pushdown(x,l,r);
    if(bg<=mid&&t[x].l)ans+=_qry(t[x].l,l,mid,bg,ed);
    if(mid<ed&&t[x].r)ans+=_qry(t[x].r,mid+1,r,bg,ed);
    return ans;
}il int qry(int bg,int ed){return _qry(1,1,2147483647,bg,ed);}

可持久化线段树 / 主席树

可持久化线段树 1（可持久化数组）

从某个历史版本加上一个数或单点查询某个版本的值。

发现每次操作都会新建一个版本，复杂度瓶颈就在复制这个版本的过程。但是发现修改操作只会从之前的某个版本上修改一个位置，考虑充分利用其它未被修改的位置。

使用线段树，那些没有被修改的位置指向的就是旧的版本，所以每次只会添加包含当前修改位置的区间，也就是 log 个。注意旧的节点的信息保持不变。

每次操作都会产生 log 个点，空间复杂度均为 O(n\log q)。通过上文的动态开点线段树实现。

il void upd(int &x,int y,int l,int r,int p,int v){
    x=++tot;
    if(l==r)return val[x]=v,void();
    int mid=(l+r)/2;
    lc[x]=lc[y],rc[x]=rc[y];
    (p<=mid)?upd(lc[x],lc[y],l,mid,p,v):upd(rc[x],rc[y],mid+1,r,p,v);
}
il int qry(int x,int l,int r,int p){
    if(l==r)return val[x];
    int mid=(l+r)/2;
    return (p<=mid)?qry(lc[x],l,mid,p):qry(rc[x],mid+1,r,p);
}

[NOI2018] 归程

一个 n 个点 m 条边的无向图，每个边有长度和海拔两个值，多次询问，求从 v 点出发之经过海拔大于 p 的边能走到的点中与 1 节点距离最近的点的距离。强制在线。

假设没有强制在线考虑怎么做：我们把询问按 p 从大到小排序，依次加入那些新的可以走的边，对于每个连通块维护其中到 1 距离最小的点，直接使用并查集即可。

那么遇到强制在线后我们就需要随时查询当 p 等于某个值时的并查集。于是考虑可持久化。我们记录并查集的 fa 数组，由于不能其被修改太多次，我们使用启发式合并不进行路径压缩，合并两个连通块只会修改一次 fa。

可持久化线段树 2

给你一个序列，多次询问求区间 [l,r] 第 k 小。

首先对序列进行离散化。假设只询问 [1,n]，我们可以把所有值丢到一颗权值线段树内，即按照值而不是下标存储。然后使用线段树二分的方式向下查找第 k 小。每个区间节点都需要记录里面包含了多少个值。

进一步地，考虑询问 [1,r]，考虑建出 n 个权值线段树，第 i 个存的是 [1,i] 内值的分布情况。这样只需要在询问对应的区间上寻找即可。发现相邻两个线段树只会有一个值改变（即当前新加入的这个值），所以我们可以使用可持久化，每次从上一个版本新建出一个线段树。

然后变成了询问 [l,r]，通过类似前缀和的方式，我们同时在编号为 l-1,r 的版本上查找，这样对于当前的一个区间，我们能找出值在区间内、下标在 [l,r] 中的数的个数。此时再二分即可。

il void upd(int &x,int y,int l,int r,int v){
    x=++tot,ch[x][0]=ch[y][0],ch[x][1]=ch[y][1],sum[x]=sum[y]+1;
    if(l==r)return;int mid=(l+r)>>1;
    if(v<=mid)ch[x][0]=upd(l,mid,v,ch[y][0]);
    else ch[x][1]=upd(mid+1,r,v,ch[y][1]);
    return x;
}

il int qry(int x,int y,int l,int r,int k){
    if(l==r)return l;
    int mid=(l+r)>>1,s=sum[ch[y][0]]-sum[ch[x][0]];
    return (k<=s)?qry(l,mid,k,ch[x][0],ch[y][0]):qry(mid+1,r,k-s,ch[x][1],ch[y][1]);
}

线段树合并

[Vani有约会] 雨天的尾巴

给你一棵树，每次选择树上两个点，在这两个点和连接它们的路径上的每一个点放上颜色为 x 的一个物品。

求操作结束后每个点存放最多的是哪个颜色。

直接考虑一个路径似乎不太好处理，首先可以考虑差分一下，即分成两条通向根节点的路径，分别在起点加上这个颜色的贡献，在终点父亲减去。那么关键点就只有 O(n) 个。

对于一个节点，我们把它子树内的贡献加起来，出现次数最多的点就是答案。考虑把这个操作丢到权值线段树上，每个节点记录区间内出现次数的最大值。并且我们只需要记录那些存在于子树内的点。

对每个点都开一个线段树，然后 dfs，每次把当前点 x 的子结点 y 的线段树合并到自己。合并的过程如下：

分析复杂度，最后能 dfs 到的叶子节点一定是 x,y 共有的，假设这样有 c 个，最坏情况下每个共有的叶子都需要从根节点向下搜 log 层才能达到，那么总体的时空复杂度就是 O(c\log n)。

然后再考虑所有合并操作的 \sum c 会是多少，对于一个颜色，发现总共重叠的次数最多就是该颜色的次数，即其会对 c 产生与颜色出现数量相等的贡献。同时颜色出现数量加起来是等于 n 的，那么 \sum c 级别也是 n 的，时空复杂度就是 O(n\log n) 了。

// 返回的是更新后的坐标，只有当 x 指向 y 时会变
il int merge(int x,int y,int l,int r){
    if(!x||!y)return x+y;
    else if(l==r)return t[x].mxv+=t[y].mxv,x;
    int mid=(l+r)>>1;
    t[x].lc=merge(t[x].lc,t[y].lc,l,mid),t[x].rc=merge(t[x].rc,t[y].rc,mid+1,r);
    return pushup(x),x;
}

线段树合并常用来优化一类 dp，接下来以几道例题介绍。

[CEOI2019] Magic Tree

给你一棵以 1 为根的树，第 i 个价值为 w_i 的果子会在第 d_i 天出现在点 v_i 上。对于某一天，你可以进行任意次操作，每次操作为砍掉这棵树的某个子树，获得这个子树上当天所有出现的果子的价值之和，砍掉后的子树就消失了。求你能获得的果子价值和的最大值。

首先把这个限制转化为选择果子的限制。发现某个果子和它的一个祖先果子均被选中，则这个果子的出现时间必须小于等于祖先果子的出现时间，否则祖先那边树就已经先被砍了。我们把问题转化成：在树上选择若干个果子，不存在一个果子的出现时间大于祖先果子的出现时间。

我们先写出一个朴素的 dp。考虑可以记子树内出现时间最大的果子，然后当前的果子出现时间就必须大于等于这个。记 f_{x,j} 表示子树 x 出现时间最大为 j 时的最大权值。类似于树上背包合并：

f_{x,i}=\max(\max_{j\le i}(f_{x,i}+f_{y,j}),\max_{j\le i}(f_{x,j}+f_{y,i}))=\max(f_{x,i}+\max_{j\le i}f_{y,j},f_{y,i}+\max_{j\le i}f_{x,j})

这样我们就有了一个 O(n^2) 的做法。

接下来的优化需要发现一个关键性质：每个点有用的 dp 状态并不多，我们发现，只有是子树内的某个果子的 d_i 才有用。而所有果子一共 m 个。

对于每个点，我们只记录其中有用的状态（其它的状态可以视为 -\infty），那么我们就需要一种高效的数据结构维护两个状态（当前点和它的子结点）的合并。

结合上一题，我们想到线段树合并。由于 dp 的过程中涉及到 f_x,f_y 的前缀最大值，我们考虑在合并时记录全局变量 xmax,ymax 表示当前扫到的最大值。然后 merge 时递归下去分类讨论：

注意上文的操作前都需要及时更新 xmax,ymax。

我们发现这些操作都是基于线段树合并的，所以复杂度当然也是正确的 O(n\log n)。

il void merge(int &x,int y,int l,int r,ll &vx,ll &vy){
    if(!x&&!y)return;
    else if(!x)vy=max(vy,t[y].mx),t[y].mx+=vx,t[y].lz+=vx,x=y;
    else if(!y)vx=max(vx,t[x].mx),t[x].mx+=vy,t[x].lz+=vy;
    else if(l==r)vx=max(vx,t[x].mx),vy=max(vy,t[y].mx),t[x].mx=max(t[x].mx+vy,t[y].mx+vx);
    else{
        int mid=(l+r)>>1;pd(x),pd(y);
        merge(t[x].lc,t[y].lc,l,mid,vx,vy),merge(t[x].rc,t[y].rc,mid+1,r,vx,vy);
        t[x].mx=max(t[t[x].lc].mx,t[t[x].rc].mx);
    }
}

[NOI2020] 命运

给你一棵树和一些连接 (u,v) 的路径，求有多少种对边染色成 0/1 的方案使得所有路径上都有至少一条边被置为 1。

看起来就很可以 dp 的样子。发现对于一些从子树内向上延伸的限制，只需要满足其中深度最大的限制。于是我们记 f_{i,d} 表示子树 i 中未被满足的限制的最大深度为 d 时对子树内染色的方案数。当限制都被满足就记为 f_{i,0}。

通过类似树上背包的形式合并。枚举当前选不选这条连接到儿子的边，合并子结点时肯定是两个取 max。

f_{x,i}=\sum_{j=0}^if_{x,i}f_{y,j}+\sum_{j=0}^{i-1}f_{x,j}f_{y,i}+\sum_{j=0}^{dep_x}f_{x,i}f_{y,j}

前面的两个求和代表不选这条边，同时需要扣掉 f_{x,i}f_{y,i} 这一重复的点。后面则代表选择这条边，此时子树内就可以任意选了。

套路地，继续优化这个式子：记 s_{i,j}=\sum_{k=0}^jf_{i,k}，有：

f_{x,i}=f_{x,i}(s_{y,i}+s_{y,dep_x})+s_{x,i-1}f_{y,i}

发现每个节点有用的状态不多，数量即为子树内延伸出来的限制的数量。使用线段树合并。

dp 方程的形式是对每个节点乘上一个标记然后再加上一些东西。由于方程涉及到前缀和，我们还需要在合并时记 sumx,sumy 分别代表当前扫到的 f_x,f_y 的前缀和。考虑两种情况：

其它的都和上题差不多。

il void merge(int &x,int y,int l,int r,int &sx,int &sy){
    if(!x&&!y)return;
    else if(!x)sy=(sy+t[y].sum)%P,t[y].sum=1ll*t[y].sum*sx%P,t[y].mul=1ll*t[y].mul*sx%P,x=y;
    else if(!y)sx=(sx+t[x].sum)%P,t[x].sum=1ll*t[x].sum*sy%P,t[x].mul=1ll*t[x].mul*sy%P;
    else if(l==r){
        sy=(sy+t[y].sum)%P;int tmp=t[x].sum;
        t[x].sum=(1ll*t[x].sum*sy%P+1ll*sx*t[y].sum%P)%P,sx=(sx+tmp)%P;
    }else{
        int mid=(l+r)>>1;pushdown(x),pushdown(y);
        merge(t[x].lc,t[y].lc,l,mid,sx,sy),merge(t[x].rc,t[y].rc,mid+1,r,sx,sy);
        pushup(x);
    }
}

线段树分裂

目前不会，咕。

猫树

目前不会，咕。

zkw 线段树

目前不会，咕。

线段树优化 dp

施工中...

动态 dp

施工中...

优化建图

施工中...

线段树分治

前置：可撤销并查集

就是可以撤销的并查集，只需要在更新同时维护一个栈代表将哪两个点连在一起即可。由于需要撤销所以不能使用路径压缩。代码：

struct DSU{
    int fa[N],siz[N];
    vector<pii>op;
    il void init(int n){
        forto(i,1,n)fa[i]=i,siz[i]=1;
    }
    il int find(int x){return (x==fa[x])?x:find(fa[x]);}
    il void merge(int x,int y){
        x=find(x),y=find(y);
        if(siz[x]<siz[y])swap(x,y);
        fa[y]=x,siz[x]+=siz[y];op.eb(mp(x,y));
    }
    il void pop_back(){
        if(op.empty())return;
        int x=op.back().first,y=op.back().second;op.pop_back();
        siz[x]-=siz[y],fa[y]=y;
    }
};

二分图

一张 n 个点的图，有 m 条无向边会分别在 [l_i,r_i] 时刻存在，每个时刻判断是否是一张二分图。

先考虑对于一个确定的图如何判断是否为二分图。

这里提一下扩展域并查集，把点 i 拆成两个节点 i,i+n，则每条边必须连接两个不同集合中的点，即 x\leftrightarrow y+n,x+n\leftrightarrow y。每次 check 时如果这个点拆出的两个新点被并到一起去了就不是二分图。

并查集加边是容易的，即对于某时刻加入当前插入的边。但是删除较为困难（区分撤销，撤销指的是上一次操作取消，删除是任意某个操作）。

我们能否通过某种方式把删除转化成撤销呢？

发现 i 在 [l_i,r_i] 存在是可以拆分成能并起来等于原来的两段。如果需要保证较优的复杂度，最好将其拆分成 \log 段。

此时线段树分治登场。线段树是按时间建立的。
像区间修改一样把每个边存在的时间用 vector 存到每个节点上。
然后就是最重要的操作：最后统计答案时，对于某个节点 x，它的区间起始点均相同，且能覆盖到 x 的两个儿子。此时用可撤销并查集先加入 x 上存在的边，再递归左右儿子，同时返回时只需撤销刚刚加入的边即可。

这样的复杂度就是分治的 O(n\log n) 了（不算并查集）。

[BJOI2014] 大融合

动态加边和查询经过某条边的路径数量。

首先加入加边时查询贡献，显然有答案等于 siz_x\times siz_y（此时 x,y 未联通）。

这启发我们使用并查集维护节点 siz。加边就可以看作边从 t_i 开始一直存在到结束。直接按上题做法上线段树分治即可维护某时刻的森林。

但是怎么查询呢？好像只有在边连接的 x,y 断开时才能查询，这启发我们把区间 [st,ed] 拆成 [st,t) 和 [t,ed]，即在查询前把边断掉然后再连起来看贡献。这样就做完了。

由这两题可见，线段树分治可以用来维护容易插入而删除困难的数据结构。代码：

int n,q;
ll ans[N];
namespace SegT{
    struct Qry{
        int x,y,initid;
    };
    vector<Qry>qry[N];
    vector<pii>op[N*5];
    int bg,ed;pii dat;
    il void _insert(int x,int l,int r){
        if(bg<=l&&r<=ed){op[x].eb(dat);return;}
        int mid=(l+r)>>1;
        if(bg<=mid)_insert(x<<1,l,mid);
        if(mid<ed)_insert(x<<1|1,mid+1,r);
    }
    il void insert(int _bg,int _ed,pii _dat){
        if(_bg>_ed)return;
        bg=_bg,ed=_ed,dat=_dat;_insert(1,1,q);
    }
    il void solve(int x,int l,int r){
        for(pii p:op[x])DSU::merge(p.first,p.second);
        if(l==r){
            for(Qry q:qry[l])ans[q.initid]=1ll*DSU::getsiz(q.x)*DSU::getsiz(q.y);
        }else{
            int mid=(l+r)>>1;
            solve(x<<1,l,mid);solve(x<<1|1,mid+1,r);
        }
        forv(i,op[x].size())DSU::pop_back();
    }
}

注：下面题目原还需要图上维护线性基的技巧，与主题关系较小略过不讲，例题经过笔者转化。如有需要了解的可以看[WC2011] 最大XOR和路径。

[HAOI2017] 八纵八横 二次转化版

有一个集合 S，多次插入和删除元素。求每个操作后集合内选择任意数字能获得的最大异或和。每个元素 x<2^m\ (m\le1000)。插入和删除的操作次数较小。

首先对于一个确定的集合，使用线性基即可求得最大异或和。注意到 m 较大需要使用 bitset。

我们注意到普通的线性基是难以删除和撤销的，这启发我们使用线段树分治。按照上题的套路，将每个元素存在的时间段找出来，然后将区间插入线段树。

但是你发现维护时出了困难：线性基没办法撤销，如何回溯呢？直接暴力记下线段树上每个点一开始的线性基，回溯时赋值回去即可。

但是线段树有 n\log n 个节点，而线性基需要的空间是 O(\frac{m^2}{w}) 的，这就爆炸了！发现赋值完后记的线性基就没用了，而由于线段树最高 \log n 层，则最多递归 \log n 层，每层只需要记一个线性基就行了。

时间复杂度 O(\frac{m^2n\log n}{w})，空间复杂度是 O(\frac{m^2\log n}{w}) 的。

LB 是线性基，bst 是长度为 m 的 bitset。

namespace SegT{
    vector<bst>upd[N*5];
    bst ans[N];
    int bg,ed;bst add;
    il void insert(int x,int l,int r){
        if(bg<=l&&r<=ed){upd[x].eb(add);return;}
        int mid=(l+r)>>1;
        if(bg<=mid)insert(x<<1,l,mid);
        if(mid<ed)insert(x<<1|1,mid+1,r);
    }
    il void insert(int _bg,int _ed,bst _add){
        if(_bg>_ed)return;
        bg=_bg,ed=_ed,add=_add;
        insert(1,1,q);
    }
    il void solve(int x,int l,int r){
        if(l>r)return;
        LB tmp;tmp.init(base);
        forv(i,upd[x].size())base.insert(upd[x][i]);
        if(l==r){
            ans[l]=base.getmax();
        }else{
            int mid=(l+r)>>1;
            solve(x<<1,l,mid);solve(x<<1|1,mid+1,r);
        }
        base.init(tmp);
    }
}