线段树全家桶_成型笔记

线段树全家桶

简单的东西通常蕴含着深刻的道理。

这大概并不是一篇入门博客，而是一篇较为完整的梳理。

并不会有太多的例题，只有强烈凸显算法特点的例题会被展示。

目录：

• 简介：线段树维护的信息
• 线段树写法/技巧
  • 框架
  • 动态开点
  • 可持久化
  • 标记永久化
• 成体系的单侧递归线段树
  • 楼房重建线段树
  • 李超线段树
• 线段树进阶技巧
  • 线段树合并
  • 线段树分治
    • 时间区间修改时间单点询问
    • 时间单点修改时间区间询问
  • 线段树上二分
• 复杂信息线段树
  • 历史和
  • 历史最值
• 均摊线段树
  • 吉司机线段树
  • 其他均摊线段树：开根，函数嵌套
• 与树的结合
  • 树链剖分
    • 应用：动态 $\text{dp}$。
  • 树上线段树合并优化 $\text{dp}$。

简介：线段树维护的信息

线段树维护双半群信息或双幺半群信息。

下面定义 $\mathbb {O,T}$ 分别为所有节点信息以及所有懒标记信息构成的集合，定义 $+$ 为信息与信息的结合，$+$ 的左右操作数是有方向的。

线段树维护的信息应当满足：

1. $\forall x,y\in\mathbb O,x+y\in\mathbb O$（pushup()）。
2. $\forall x\in \mathbb O,y\in\mathbb T,x+y\in \mathbb O$（pushr()）。
3. $\forall x,y\in\mathbb T,x+y\in \mathbb T$（pushdown()）。
4. $\forall x,y,z\in \mathbb O\cup\mathbb T,x+(y+z)=(x+y)+z$。

满足了以上条件，便可以使用线段树维护你的信息。

若维护的是幺半群信息，则还需要具有一个单位元 $e$，满足 $\forall x\in \mathbb O,x+e=e+x=x$。

线段树写法/技巧

警告：该内容偏向主观且浅薄，建议略过。

框架

我的线段树写法较为简短，每个函数两到三行。

首先是 #define 的开头，关于 #define mid (L+R>>1)，实测是要比大多数线段树写法都要快的。

#define l(x) (x<<1)
#define r(x) (x<<1|1)
#define mid (L+R>>1)

如果维护的信息不多，可以使用数组来完成信息的维护，多的话，建议采用结构体。

理论最快的线段树写法是把任何能压到结构体中的信息压到结构体中，包括区间左右端点，这是因为寻址的连续性。

但这种写法个人认为偏丑，所以我退而求其次使用数组或不带左右端点的结构体维护，左右端点信息作为参数传递。

（pushup(),pushdown(),pushr() 等作用简单的函数可以 #define 实现以减小代码长度和函数调用开销。）

struct node {
    /*你需要维护的信息*/
    node friend operator+(node a,node b) {
        /*合并两个区间*/
        return;
    }
} c[N<<2];
void up(int d) {c[d]=c[l(d)]+c[r(d)];}
/*这里的加法是泛化概念，实际对应的是信息的合并，你可以自定义一个节点结构体然后重载加法*/
//当然比较简单的区间和之类直接用数值的加法就行
void bd(int L,int R,int d) {
    if(L==R) return /*单点初始化*/,void();
    bd(L,mid,l(d));bd(mid+1,R,r(d));up(d);
}
void mo(int id,int v,int L,int R,int d) {
    if(L==R) return /*单点修改*/,void();
    x<=mid?mo(id,v,L,mid,l(d)):mo(id,v,mid+1,R,r(d));up(d);
}
node q(int l,int r,int L,int R,int d) {
    if(R<l||r<L) return e0/*单位元，即合并上这个值不变，加法是0，乘法是1，max是-inf*/;
    if(l<=L&&R<=r) return c[d]/*节点信息*/;
    return q(l,r,L,mid,l(d))+q(l,r,mid+1,R,r(d));
}
//若你维护的信息无单位元，则需要采用以下写法：
node q(int l,int r,int L,int R,int d) {
    if(l<=L&&R<=r) return c[d]/*节点信息*/;
    if(r<=mid) return q(l,r,L,mid,l(d));
    if(l>mid) return q(l,r,mid+1,R,r(d));
    return q(l,r,L,mid,l(d))+q(l,r,mid+1,R,r(d));
}

//区间改，单点/区间查
void up() {}
void bd() {}
void pr(int d,int v) {}//对d这个线段树节点进行大小为v的区间修改。
//用区间加来示例是下面代码，传不传L,R看自己需要
//void pr(int L,int R,int d,int v) {tg[d]+=v;sum[d]+=(R-L+1)*v;}
void down(int d) {if(tg[d]) pr(l(d),tg[d]),pr(r(d),tg[d]),tg[d]=0;}
void mo(int l,int r,int v,int L,int R,int d) {
    if(R<l||r<L) return;if(l<=L&&R<=r) return pr(d,v);
    down(d);mo(l,r,v,L,mid,l(d));mo(l,r,v,mid+1,R,r(d));up(d);
}
node q(int id,int L,int R,int d) {
    if(L==R) return c[d];
    return down(d),id<=mid?q(id,L,mid,l(d)):q(id,mid+1,R,r(d));
}
node q(int l,int r,int L,int R,int d) {
    if(R<l||r<L) return e0;if(l<=L&&R<=r) return c[d];
    return down(d),q(l,r,L,mid,l(d))+q(l,r,mid+1,R,r(d));
}

//普通线段树主函数调用
main() {bd(1,n,1);mo(l,r,v,1,n,1);q(l,r,1,n,1);}
//你可以用默认参数的形式将后三个参数设为固定的1,n,1，这样就可以简洁调用了
void mo(int l,int r,int v,int L=1,int R=n,int d=1) {}
main() {mo(l,r,v);}

动态开点

这是一类节省空间的小技巧，我们不去建树，而是用到节点信息的时候如果这个节点不存在现场建出来。

很多操作依赖于动态开点，例如线段树合并或可持久化。

实现动态开点只需要我们在上述框架中做如下改动：

int d -> int &d
#define l(x) ls[x]
#define r(x) rs[x]
int l(N<<2),r(N<<2),snt;
//每个函数前加上：
!d&&(d=++snt,/*对节点的初始化，例如求最大值就将值设为-inf*/);
//原来的操作中将 int d 的位置传一个变量作为根，那么以后就可以靠这个变量访问你修改过的树了

中心思想就是现用现开，没用的节点统一是 $0$，记得给节点 $0$ 的信息填上默认值。

可持久化

基于动态开点，原理是线段树的每个操作访问到的节点总数是 $\Theta(\log n)$ 的，只需要将其复制一遍连上原来的儿子就可以看作我们拥有了一棵新的树，于是我们就可以把每个版本的树都求出来。

比网上大多数版本都要清爽。

你需要在框架上做如下改动以将原线段树可持久化。

int d -> int &d
#define l(x) ls[x]
#define r(x) rs[x]
int l(N<<2),r(N<<2),snt;
int cpy(int d) {int nd=++snt;l(nd)=l(d);r(nd)=r(d);c[nd]=c[d];/*复制一切信息*/}
//每个函数前加上：
d=cpy(d);
//原来的操作中将 int d 的位置传一个变量作为版本，若你想直接修改版本就直接传 newver。
//若你想在某个版本的基础上修改就传 newver=oldver
//例如以下代码在rt[i-1]的版本修改存到rt[i]中：
modify(l,r,1,n,rt[i]=rt[i-1]);

标记永久化

用处并不大，主要思想是将标记记录在节点上永不下传，适用的范围有限，其最明显的特征是标记要具有交换律。

void modify(int l,int r,tag x,int L,int R,int d) {/*下方+泛指标记结合*/
    if(R<l||r<L) return;if(l<=L&&R<=r) return c[d]=c[d]+x,tg[d]=tg[d]+x,void();
    modify(l,r,x,L,mid,l(d));modify(l,r,x,mid+1,R,r(d));up(d);
}
node query(int l,int r,tag t,int L,int R,int d) {//t表示累加标记
    if(R<l||r<L) return e0;if(l<=L&&R<=r) return c[d]+t;
    return query(l,r,t+tg[d],L,mid,l(d))+query(l,r,t+tg[d],mid+1,R,r(d));
}

成体系的单侧递归线段树

整理完烦人的模板，来一点小清新理论体系。

楼房重建线段树

可以处理的问题：区间本质不同前缀极值的和（或在这个区间前面加 $\Theta(1)$ 个数，也能做）。

每个点的权值可以有两个（或更多）：用于计算前缀极值的权值以及用于计算和的权值。

对每个点需要维护 $(mn,sum)$，表示节点内极值和答案。

关键在于 up() 是 $\Theta(\log n)$ 的，形如一个单侧递归。

细说的话就是如果左区间内没有前缀极值就直接递归到右区间，否则右区间一定被“左区间”而不是“用来限制的值”限制。

ll o(int k,int L,int R,int d) {
    if(L==R) return sum[d]*(mn[d]<k);
    return mn[l(d)]<k?o(k,L,mid,l(d))+sum[d]-sum[l(d)]:o(k,mid+1,R,r(d));
}
void up(int L,int R,int d) {
    mn[d]=min(mn[l(d)],mn[r(d)]);sum[d]=sum[l(d)]+o(mn[l(d)],mid+1,R,r(d));
}
void mo(int id,int v,int L,int R,int &d) {
    !d&&(d=++snt);if(L==R) return /*modify*/,void();
    id<=mid?mo(id,v,L,mid,l(d)):mo(id,v,mid+1,R,r(d));up(L,R,d); 
}
ll Sum;int Mn;
void q(int l,int r,int L,int R,int d) {
    if(R<l||r<L) return;if(l<=L&&R<=r) return Sum+=o(Mn,L,R,d),Mn=min(Mn,mn[d]),void();
    q(l,r,L,mid,l(d));q(l,r,mid+1,R,r(d));
}//(这个可恶的代码结构)
ll q(int mn,int l,int r,int rt) {
    if(l>r) return 0;
    return Mn=mn,Sum=0,q(l,r,1,vnt,rt),Sum;
}

看起来好像非常没用对吧。

实际上不仅仅能求和，还能求任何信息的合并。

具体来说，可以求区间内所有在某个量的前缀极值位置上的信息的合并。

例如说所有 $a$ 的前缀极值位置上的 $b$ 构成的序列的最大子段和。

可以参考粉兔的 blog（见参考资料）。

具体来说就是你上传信息的时候不能用 sum[d]-sum[l(d)] 来求左区间对右区间的影响之后的信息了，而是应该在上传的时候记录。

node o(int k,int L,int R,int d) {
    if(L==R) return sum[d]*(mn[d]<k);
    return mn[l(d)]<k?o(k,L,mid,l(d))+cnt[d]:o(k,mid+1,R,r(d));
}
void up(int L,int R,int d) {
    mn[d]=min(mn[l(d)],mn[r(d)]);
    cnt[d]=o(mn[l(d)],mid+1,R,r(d));
    sum[d]=sum[l(d)]+cnt[d];
}
void mo(int id,int v,int L,int R,int &d) {
    !d&&(d=++snt);if(L==R) return mn[d]=v==-1?inf:T[L],sum[d]=(mn[d]!=inf)*V[L],void();
    id<=mid?mo(id,v,L,mid,l(d)):mo(id,v,mid+1,R,r(d));up(L,R,d); 
}
node Sum;int Mn;
void q(int l,int r,int L,int R,int d) {
    if(R<l||r<L) return;if(l<=L&&R<=r) return Sum+=o(Mn,L,R,d),Mn=min(Mn,mn[d]),void();
    q(l,r,L,mid,l(d));q(l,r,mid+1,R,r(d));
}
node q(int mn,int l,int r,int rt) {
    if(l>r) return e0;
    return Mn=mn,Sum=e0,q(l,r,1,vnt,rt),Sum;
}

实际上感觉做到这一步之后就可以无脑堆出大量的 idea 了。

例题：

P4198 楼房重建

一个人站在平面直角坐标系的 $(0,0)$，他的面前在不断拆楼盖楼，第 $i$ 天把横坐标在 $x_i$ 的楼房高度改为 $y_i$。

问每天他能看到多少栋楼。

$n\le10^5$。

显然这个人只能看到 $s_i=\frac{y_i}{x_i}$ 是 $s$ 序列前缀最大值的那些楼房。

套上面的板子。

树套二叉搜索树

给你一棵树，每个点初始有一个空的 $\text{BST}$，你需要支持两种操作：

• $1 \ u\ v\ k$，把 $(u,v)$ 链上的 $\text {BST}$ 都插入 $k$（从根往下插入，若小于当前元素则往左子树走，否则往右子树走，直到走到空节点）。
• $2\ u\ k$，询问如果在 $u$ 节点处插入 $k$，经过的结点的权值和。

$n\le 2\times10^5,k$ 互不相同。

先考虑只有一个 $\text{BST}$ 怎么做。

考虑这个 $\text{BST}$ 的性质，除了满足普通的中序遍历有序，还满足关于时间戳是小根堆的性质。

那你不如提前把所有元素插进去，然后给每个点安排一个时间戳权值，你发现这相当于一个笛卡尔树。

那我们就顺势而为，将其视为按照权值拍扁的笛卡尔树。

（把时间视作权值然后离线是很经典的思想。）

那求这个答案就形如一个区间的本质不同的前缀（后缀） $\min$ 的权值和，直接上楼房重建线段树。

实际上不需要两棵线段树的代码，只需要维护成一样的线段树然后有一棵倒着插。

接下来是在树链上批量做这个事情。

我们既然离线了，直接递归，对于插入 $(x,y,s)$，回溯到 $x$ 和 $y$ 的时候插入，回溯到 $fa_{lca(x,y)}$ 的时候删除，套一个线段树合并即可。

李超线段树

这个好像比上一个有用的多是怎么回事。

可能发现的比较早吧。

可以维护区间插入类直线状物，区间求极值。

这个类直线状物可以先理解成直线，区间插直线实质上就是插线段。

其运用的原理是两条直线如果在一个区间中没有完全替代关系，那么固定住在中点处更优的直线，另一条直线最多往下递归一侧。

这构成了李超线段树的复杂度保证。

基础的模板是插直线插线段单点求极值（笔者上网学习该算法时遇到了大量的堆积丑陋代码，希望这份略显清新的代码可以帮到读者）：

struct L {
    ll k,b;L(ll k=0,ll b=-inf):k(k),b(b) {}
    ll operator[](ll x){return k*x+b;}
} l[N];
void mo(int x,int L,int R,int &d) {
    !d&&(d=++snt);int &y=c[d];if(!y) return y=x,void();
    if(l[x][mid]>l[y][mid]) swap(x,y);
    if(l[x][L]>l[y][L]) mo(x,L,mid,l(d));
    if(l[x][R]>l[y][R]) mo(x,mid+1,R,r(d));
}
void mo(int l,int r,int x,int L,int R,int &d) {
    !d&&(d=++snt);if(R<l||r<L) return;
    if(l<=L&&R<=r) return mo(x,L,R,d);
    mo(l,r,x,L,mid,l(d));mo(l,r,x,mid+1,R,r(d));
}
ll q(int x,int L,int R,int d) {
    if(L==R) return l[c[d]][x];
    return max(l[c[d]][x],x<=mid?q(x,L,mid,l(d)):q(x,mid+1,R,r(d)));
}

如果想区间求极值的话其实也挺简单，类似于标记永久化，每段求个极值传上去即可。

struct L {
    ll k,b;L(ll k=0,ll b=-inf):k(k),b(b) {}
    ll operator[](ll x){return k*x+b;}
} l[N];
#define up(L,R,d) mi[d]=min(min(mi[l(d)],mi[r(d)]),min(li[c[d]][L],li[c[d]][R]));
void mo(int x,int L,int R,int &d) {
    !d&&(d=++snt);int &y=c[d];if(!y) return y=x,up(L,R,d),void();
    if(l[x][mid]>l[y][mid]) swap(x,y);
    if(l[x][L]>l[y][L]) mo(x,L,mid,l(d));
    if(l[x][R]>l[y][R]) mo(x,mid+1,R,r(d));up(L,R,d);
}
void mo(int l,int r,int x,int L,int R,int &d) {
    !d&&(d=++snt);if(R<l||r<L) return;
    if(l<=L&&R<=r) return mo(x,L,R,d);
    mo(l,r,x,L,mid,l(d));mo(l,r,x,mid+1,R,r(d));up(L,R,d);
}
ll q(int x,int L,int R,int d) {
    if(L==R) return l[c[d]][x];
    return max(l[c[d]][x],x<=mid?q(x,L,mid,l(d)):q(x,mid+1,R,r(d)));
}
ll q(int l,int r,int L,int R,int d) {
    if(l<=L&&R<=r) return mi[d];
    if(R<l||r<L) return inf;
    return min(min(li[c[d]][max(l,L)],li[c[d]][min(r,R)]),
            min(query(l,r,L,mid,l(d)),query(l,r,mid+1,R,r(d))));
}

例题

P4254 [JSOI2008]Blue Mary开公司

题意不赘述，板子。

[P4097 HEOI2013]Segment

属于是不正常的例题。

题意不赘述，不同点是需要支持与 $y$ 轴平行以及求的是编号而不是极值。

加点讨论即可。

P4069 [SDOI2016]游戏

给定一棵树，你要维护树链插入一次函数（路径上每个点的权值是关于到路径起点的距离的一次函数），树链查询最小权值。

$n\le10^5$。

那这个时候就要说一说上方提到的类直线状物是什么东西了。

大概就是你发现想维护一些函数，但是你发现这玩意可能是一段一段的直线或者某种曲线。

那这个时候你把李超线段树的核心部分，也就是是否满足取中点最优之后剩下的一条“线”可以单侧递归，套上去看一看成立了那就可以维护。

举个例子，往树上添加函数 $(\forall v \text{ in x}),f(v)=k\text{dis}(x,v)+b$，就不能用 dfs 序配合李超线段树维护，因为虽然在 dfs 序中 $x$ 的子树是连续的一段，但函数的 $x$ 在 dfs 序上乱序。

但像往树链上添加类似的函数就可以用李超线段树维护，因为重链在 dfs 序上是连续的，并且函数的 $x$ 也递增。

代码。

那我们其实有了一些启发，比如说如果横坐标的范围是 $\mathbb N\cap[0,10^9]$，那我们可以离散化之后使用李超线段树而不必动态开点，虽然离散化后的图像失去了直线的图形，但不影响李超线段树的单侧递归。

CF932F Escape Through Leaf

给定一棵树，根为 $1$，每个节点有两个权值 $a_i,b_i$，你可以从一个节点向子树中另一个节点跳，从 $x$ 跳到 $y$ 的代价是 $a_x\times b_y$，跳跃多次的代价是每次代价之和，对于每个节点求它到达任意一个叶子节点的最小权值。

李超线段树合并优化 $\text{dp}$。

考虑 $\text{dp}$，设 $f_x$ 表示 $x$ 到叶子的最小代价，则：

$$f_x\gets \min_{v\text{ in }x}(f_v+a_xb_v)$$

把 $f_v$ 和 $b_v$ 写成关于 $a_x$ 的一次函数，则我们要求出一个子树的李超线段树，使用李超线段树合并即可。

合并两个节点的过程相当于两条线段在竞争，落败的一条需要下传。

（突然发现没讲线段树合并也没讲线段树优化 $\text{dp}$。）

void merge(int L,int R,int &x,int y) {
    if(!x||!y) return x|=y,void();
    if(L==R) return x=li[c[x]][L]<li[c[y]][L]?x:y,void();
    modify(c[y],L,R,x);
    merge(L,mid,l(x),l(y));merge(mid+1,R,r(x),r(y));
}

Loj#6546. 简单的数列题

给定两个数列 $a,b$，有 $m$ 个操作，每个操作形如：

• $\text{1 l r w}$，将数列 $a$ 中 $[l,r]$ 的所有数加上 $w$。
• $\text{2 x y}$，交换 $b_x$ 和 $b_y$。
• $\text{3 l r}$，求 $\max\limits_{i=l}^ra_ib_i$。

$n,m\le 10^5,\text{1.5 seconds}$。

可以用 $\text{KTT}$ 达到 $\Theta(n\log^3 n)$，但分块 + 李超树无论是码量还是能做的事情都严格强于 $\text{KTT}$。

虽然 $\Theta(n\sqrt n\log n)$ 跑的挺慢。

考虑分块，加法肯定要打加法 $\text{tag}$，那我们就要实现对一个块给定一个 $\text{tag}$ 快速求答案。

我们可以把答案写成 $(a_i+t)b_i=b_it+a_ib_i$，将 $t$ 视作自变量，维护出该块的李超线段树。

$2$ 操作就是把该块重构。

代码。

trick：小数横坐标无法离散化？

直接按照最大精度把小数映射到整数即可。

其实不用，直接把小数当作线段树的 $L,R$ 即可，常数会小很多，参照 [ABC341G] Highest Ratio 的分数规划 + 李超树做法。

线段树进阶技巧

线段树合并

没见过线段树分裂有用的时候，遇到了建议右转平衡树。

线段树合并是一类极为有用的技巧。

对于若干棵你自己造出来的单点修改动态开点线段树，以任意顺序合并的总复杂度为总点数。

这个定理比隔壁的启发式合并还猛，直接连 $\log$ 也没了。

先说算法流程：

void mer(int L,int R,int &x,int y) {
    if(!x||!y) return void(x|=y);if(L==R) return (leafmerge),void();
    mer(L,mid,l(x),l(y));mer(mid+1,R,r(x),r(y));up(x);
}

有那么一瞬间觉得比启发式还短。

为了进行线段树合并，你需要支持叶子节点处信息的合并以及 pushup() 操作，仅此而已。

复杂度分析：调用一次算法的复杂度是两棵树重合的节点个数，在调用完成后重合的节点就被我们删掉了，所以最多不会删除总点数个数。

而如果到了区间修改，就不是那么美好了。

两棵树合并的方式可能是不同于节点信息和标记信息的合并的，我们需要保证合并存在一种合并两个带有标记的节点信息的方式，使得合并之后节点的信息等价于递归下去合并叶子再 pushup() 上来。

这通常是难以办到的，例如经典例子：区间加，区间求和，合并两棵树的方式是叶子对应点取 $\max$。

你会发现合并两棵树的复杂度从 $\Theta(|x\cap y|)$ 变成了 $\Theta(|x|+|y|)$，如果对应位置一个节点空有标记没有实际信息而另一个节点有信息那你依然不能停下。

判断能否进行区间修改和线段树合并通常需要考虑合并一个带标记的空节点和一个正常的节点，如果可以快速合并，那么这个线段树合并就是可行的。

例如两棵树加起来，区间取 $\max$，区间求和，合并空节点方式就是吉司机线段树。

如果你排除了万难，达到了以上条件，记得不要使用传统的 pushdown()，否则会递归整个子树。

你可以选择标记永久化，或特判一个节点是否是整个子树全空。

线段树分裂可以完全被平衡树代替，这里不涉及。

感觉线段树合并的题目就是要先想到线段树合并，然后套板子，感觉没有典题，或者说全是典题。

来记几个不平凡的题。

P8959 「CGOI-3」灵气

给定一棵树，边是单向的，还有一个空集合，有若干操作：

• 向集合中加入一个点。
• 将一个点从集合中删除。
• 求集合中能到达 $x$ 的点的点权和的历史最大值。

$n\le2\times 10^5$。

考虑离线，对每个点求出一个时间轴，询问就是查询 $[1,i]$ 的时间轴上的最大值，考虑我们不能真的开出那么多空间，所以使用可持久化线段树合并。

具体来说，本题采用以下流程：

• 首先对每个点建立线段树，类似于线段树分治将这个点的出现区间全部加上 $a_x$（在这个点自己的动态开点线段树上）。
• 然后随便一个根开始 $\text{dfs}$，先递归指向 $x$ 的儿子（因为这些儿子会影响到其他的儿子），递归完成后将儿子的线段树合并到自己身上。
• 再递归 $x$ 指向的儿子，递归前将 $x$ 的线段树合并到儿子身上。
• 所有递归结束后在 $x$ 处统计所有询问的答案。

关于线段树合并为什么要可持久化，一个点的线段树要多次给儿子们复用，而普通的线段树合并会将原树变成新树的一部分，破坏了原结构。

关于复杂度的证明，可以理解为当且仅当两个点的路径上有 $\le 1$ 个交汇点，$=0$ 个分叉点，这两个点的线段树才会发生 $1$ 次合并，所以并不会有两棵原始树发生了多次合并，而我们知道一直合并的复杂度是跟节点个数成正比的，所以复杂度 $\Theta(n\log n)$。

关于区间修改的线段树合并，并不是所有区间修改的线段树都能合并，需要看叶子节点的合并和标记的合并是否吻合，本题就是相当于把两棵“区间加区间求 $\max$”的线段树给“加”起来，所以直接使用标记永久化合并即可，叶子处和非叶子处都要将标记相加。

原题解。

P5298 [PKUWC2018] Minimax

一棵 $n$ 个结点的有根树，根是 $1$ 号结点，且每个结点最多有两个子结点。

定义结点 $x$ 的权值为：

1.若 $x$ 没有子结点，那么它的权值会在输入里给出，保证这类点中每个结点的权值互不相同。

2.若 $x$ 有子结点，那么它的权值有 $p_x$ 的概率是它的子结点的权值的最大值，有 $1-p_x$ 的概率是它的子结点的权值的最小值。

现在小 $C$ 想知道，假设 $1$ 号结点的权值有 $m$ 种可能性，权值第 $i$ 小的可能性的权值是 $V_i$，它的概率为 $D_i(D_i>0)$，求：

$$\sum_{i=1}^{m}i\cdot V_i\cdot D_i^2\pmod {998244353}$$

$1\leq n\leq 3\times 10^5$，$1\leq w_i\leq 10^9$。

看所求这么麻烦，肯定是要求出每个 $D_i$ 才行了。

考虑最后每个点都要求出这样一个数组，那我们使用线段树合并。

考虑如何合并两个子节点。

根据题意，设节点 $x$ 权值是 $v$ 的概率为 $p_{x,v}$，则：

$$f_{x,v}=f_{l,v}\left(p_x\sum_{k\le v}f_{r,k} +(1-p_x)\sum_{k\ge v}f_{r,k}\right)+f_{r,v}\left(p_x\sum_{k\le v}f_{l,k} +(1-p_x)\sum_{k\ge v}f_{l,k}\right)$$

那么我们在计算线段树叶子节点的值时显然需要前后缀和，那我们可以在递归左子树时顺便传下去右子树的和，右子树同理。

所以我们的线段树节点还需要记录区间和，然后我们考虑如果一棵树空了另一棵树应当直接乘上对应的权值，所以标记需要维护区间乘。

需要特别注意的一点是递归前应当记录好左右子树的和，否则递归下去这个值就变了。

void merge(int L,int R,int &x,int &y,int sumx,int sumy,int p) {
    if(!x&&!y) return;
    if(!x) return pushr(y,sumy),x|=y,void();
    if(!y) return pushr(x,sumx),void();
    down(x);down(y);int ry=sum[r(y)],rx=sum[r(x)],ly=sum[l(y)],lx=sum[l(x)];
    merge(L,mid,l(x),l(y),(sumx+1ll*ry*(1-p+md))%md,(sumy+1ll*rx*(1-p+md))%md,p);
    merge(mid+1,R,r(x),r(y),(sumx+1ll*ly*p)%md,(sumy+1ll*lx*p)%md,p);up(x);
}

P6773 [NOI2020] 命运

给定一棵根为 $1$ 的树和若干个祖先点对，对方案计数，使得给每条边赋上一个 $0/1$ 的权值，每个点对对应的链上至少有一条 $1$ 边。

$n\le 5\times 10^5$。

线段树合并优化 $\text{dp}$ 通常都需要先设计 $\Theta(n^2)$ 的 $\text{dp}$，且保证有值的位置不多，合并后有值的位置不会急剧增加。

所以设 $f_{x,d}$ 表示 $x$ 位置，最靠下的一个还没有满足的点对的上节点深度为 $d$，这样设计状态的好处是满足了一个限制，那么更靠上的限制也满足了。

转移：

$$\begin{aligned}f_{x,d}'&\gets f_{x,d}\sum_kf_{v,k}+\sum_{k_1,k_2,\max(k_1,k_2)=d}f_{x,k_1}f_{v,k_2}\\&=f_{x,d}\sum_kf_{v,k}+f_{v,d}\sum_{k\le d}f_{x,k}+f_{x,d}\sum_{k<d}f_{v,k}\end{aligned}$$

需要用到前缀信息，跟上题没什么大区别。

线段树分治

欸很多人感觉线段树分治就只有朴素的时间区间修改时间单点询问，那就让我撬开你的思路吧。

时间区间修改时间单点询问

你需要支持加入一个元素，删除之前加入的某个元素，求某个值。

如果你不方便删除但是方便撤销且答案与加入顺序无关，那么你就能用上线段树分治。

思路很简单，计算出每个物品的“存活区间”，将其加入线段树中，最后时刻遍历整颗线段树，进入一个节点的时候把存在这个节点上的所有元素加入，退出一个节点的时候把所有元素撤销。

代码也很简单，跟线段树的关系不大，最后的时刻遍历即可。

和线段树合并一样属于工具属性，也没有很典的题，通常是你需要往一个题里先套一步线段树分治，然后想怎么做。

例如 P9168 [省选联考 2023] 人员调度，看到加入删除，先套一步线段树分治，再继续后面的操作，由于不是本文重点，此处略过。

时间单点修改时间区间询问

一般的线段树都是单点修改简单区间修改麻烦，而线段树分治刚好反过来了。

需要保证的一点是你的统计必须要统计出当前加入元素的所有子集的最优权值。

好处是你并不需要支持撤销操作了。

例如背包问题，你多加一个元素不会让答案变劣。

对于单点修改，我们把每一层都 push 一个修改进去。

对于区间询问，挂在拆出来的 $\log$ 个区间上。

每次到一个新的节点我们直接舍弃掉之前的信息，重新加入这个点的所有修改，回答所有询问。

注意一个询问会被回答很多次，我们需要取极值。

典型的例题是 P4585 [FJOI2015] 火星商店问题：

有一个时间轴和一个商店，其中有 $n$ 件永恒商品和 $m$ 件只在某一天上架的限时商品，每个商品有一个权值和一个编号，每天会有火星人买上架了 $d$ 天以内，编号在 $[l,r]$ 中的商品或永恒商品，使得这个商品的权值与这个火星人的幸运数字的异或值最大。

$n,m\le 10^5$。

很有意思的题，同时兼顾编号、时间轴和权值三个维度。

首先考虑扔掉时间轴如何尽可能快的求答案，显然我们只需要一棵可持久化 $\text{Trie}$，版本号是编号，这样使用差分就可以搞掉编号的限制，异或值最大是朴素的。

然后我们加上时间轴，其中限时商品可以直接套用上面的板子来处理（注意插入前按照编号排序），永恒商品怎么办呢，如果令永恒商品都在里面的一棵 $\text{Trie}$ 作为初始 $\text{Trie}$ 的话，那就无法兼顾 $[l,r]$ 的编号限制了。

哎其实只需要最开始的时候对每个人买永恒商品的情况取一遍极值就可以了，意外朴素的处理方式。

线段树上二分

其实就是线段树本身是一个二分结构，所以很多时候要想一想你的“二分套线段树”能不能改成线段树上二分。

绝大多数的二分套线段树都是能改成线段树上二分的。

随便来举个例子。

T395975 芙宁娜

给定一棵树，有若干个点对 $(a_i,b_i)$，其权值为 $c_i$，还有若干条链 $(u_i,v_i,w_i)$，其效果是将 $(u_i,v_i)$ 链上全部加上$w_i$。

现在按顺序执行这些链加，对于每个点对求出两个点上被加的总权值 $\ge c_i$ 的时刻。

$n\le10^5$。

有整体二分的简单 $\Theta(n\log^2 n)$ 做法，以及在线的神秘减半警报器做法。

来介绍一个 $\Theta(n\log n)$ 做法。

首先考虑构建主席树，二分版本来检测，看起来两边都是 $\Theta(n\log^2n)$ 的。

第一步我们可以差分链加单点查为单点加子树查。

欸重点在第二步，如何把这个二分套线段树变成线段树上二分？这可是二分版本啊！

非常彪悍的一点是，单点修改主席树的本质就是二维平面上的若干点，那我们旋转一下坐标系，即我们互换版本和下标，就可以变成线段树上二分了。

原来的区间 dfn 直接变成两个横坐标差分即可。

复杂信息线段树

大概就是你维护的东西不是那么明显了，或者说你很难知道你究竟要维护什么东西。

包括模拟流模拟割还有历史信息。

CF1919F2 *2800

F1：

有 $n$ 个酒桶，每个酒桶初始有 $a_i$ 升水，酿酒能力是 $b_i$，现进行 $n$ 轮操作，对于第 $i$ 轮操作，我们会：

• 令 $(a_i,ans)\gets(a_i-\min(a_i,b_i),ans+\min(a_i,b_i))$，即酿造至多 $b_i$ 升酒。
• 若 $i\ne n$，则令 $a_{i+1}\gets a_{i+1}+a_i$。

现在有 $q$ 轮修改操作，每轮修改一个酒桶的 $a_i,b_i$，并询问进行一次上述操作得到的答案。

$n,q\le 5\times 10^5,5\text{ seconds}$。

在 F1 的基础上加上了第 $i$ 个水管流到下一个水管的最大水量 $c_i$，修改的时候也会修改。

线段树/分块。

很多时候可以直接从线段树维护信息的角度去想应该怎么合并两个区间，好处是比矩阵乘法更丰富，例如可以同时用 $\max/\min$，坏处是不好想。

感觉模拟流/模拟割是一种很神秘的东西，有时间整理下。

其他做法感觉题解区也说的明白，这里采用模拟割。

考虑建网络流模型：

$$\newcommand{\rt}{\xrightarrow}\begin{align}S&\rt{a_i} i\\i&\rt {b_i}T\\i&\rt{c_i}i+1\end{align}$$

我们要求最大流，也就是最小割。

（能把求一个最大的东西转化成求一个最小的东西是最猛的地方。）

可以证明，对于这个网络流模型，其最小割一定拥有该性质：对于每个 $i$，其 $(1)$ 边和其 $(2)$ 边一定恰好割掉一条。

$\text{Proof}$：

首先至少得割一条，要不然就通了。

然后我们假设 $i$ 在最优方案中同时割掉了 $(1)(2)$。

若存在 $S\to i$ 路径，则我们可以不割 $(1)$，不变劣。

若不存在 $S\to i$ 路径，则 $i\to T$ 就没必要割了，我们可以不割 $(2)$，不变劣。

考虑模拟这个经典割：线段树每个节点维护 $f_{0/1,0/1}$ 表示区间左端割 $(1)/(2)$，右端割 $(1)/(2)$，合并区间时若左区间右端割了 $(2)$，右区间左端割了 $(1)$，则要割掉 $(3)_i$。

代码。

P8868 [NOIP2022] 比赛

（这是之前写的，懒得改了，可以从中看出构造标记的思路。）

（事实上将本题的覆盖理解为加法会远远更容易构造信息。）

线段树历史和。

双半群模型。

线段树的双半群模型简单来说就是构造两个 struct，$tag$ 和 $node$。

我们要实现 $tag+tag\to tag,node+tag\to node,node+node\to node$。

应用场景分别为 pushdown()、pushr()、pushup()。

关于思索如何构造信息，一般来说需要逆向地想，类似于区间最大子段和的思考历程。

可以阅读本文来理解双半群的本质。

这个题首先离线扫描线，然后我们就需要动态维护三个数组，$X,Y,S$。

具体的意义就是，$X_i$ 为 $\max_i^ra_i$，$Y_i$ 为 $\max_i^rb_i$，$S_i$ 为以 $i$ 为子区间左端点的所有答案，即 $X_iY_i$ 的每个历史版本之和。

那么询问相当于 $S$ 区间和。

扫描线右移相当于做三个操作：$X$ 区间赋值，$Y$ 区间赋值，$S$ 区间 $S_i\gets S_i+X_iY_i$。

然后我们想需要维护什么。

首先 $node$ 里肯定有 $(x,y,s)$（$x,y$ 在长度为 $1$ 的区间中要表现为 $X_i,Y_i$，$s$ 是 $\sum_{i=l}^rS_i$），$tag$ 里肯定有 $(=_x,=_y)$（区间赋值 $x,y$）。

主要的关键点是解决操作“$S$ 区间 $S_i\gets S_i+X_iY_i$”。

由于这个加的最高次数是 $2$，我们直接对 $tag$ 维护所有 $2$ 次以下的信息。

即 $(=_x,=_y,+_c,+_x,+_y,+_{xy})$，每个 $tag$ 的值都代表对 $S$ 加的系数（注意不是对数组操作的系数，别混了）。

根据正常的套路，我们规定 $=_x,=_y$ 的优先级高于 $+_c,+_x,+_y,+_{xy}$，$tag+tag$ 传递时若有 $=$ 则原来的 $+$ 清空。

这句话是本来写的，错的很离谱，因为这个不是对 $X,Y$ 区间加，而是对 $S_i$ 区间加 $X_iY_i$。

但标记总要有个顺序，思索半响后发现先 $=$ 再 $+$ 的话，对 $=$ 之前的系数就没有办法在 $tag$ 自己处理了，所以我们规定先 $+$ 再 $=$，这顺便提示了我们在后续的 $node+tag\to node$ 中我们需要先执行 $+$ 再赋值，时刻牢记 $+$ 是对原来的区间和的。

那么 $tag_1+tag_2$ 就可以尝试构造了（$tag_1+tag_2$ 是前者被后者作用，为了方便描述 $=$ 用 $e$ 代替，$+$ 用 $a$ 代替，$tag_2$ 的标记是大写的 $E,A$）：

首先对于最后的 $=$ 标记是如果 $E$ 标记存在则为 $E$ 标记，否则为 $e$ 标记，下面我们仅讨论最终 $+$ 标记的转化：

• 若 $e_x\neq0$ 且 $e_y\neq0$，则结果为 $(A_c+a_c+A_xe_x+A_ye_y+A_{xy}e_xe_y,a_x,a_y,a_{xy})$。
• 若 $e_x\neq0$ 且 $e_y=0$，则结果为 $(A_c+a_c+A_xe_x,a_x,A_{xy}e_x+A_y+a_y,a_{xy})$。
• $e_y\neq0$ 的情况同理。
• 若 $e_x=e_y=0$，则结果为 $(A_c+a_c,A_x+a_x,A_y+a_y,A_{xy}+a_{xy})$。

发现可以统一成一个式子：$(A_xe_x+A_ye_y+A_{xy}e_xe_y+A_c+a_c,(A_{xy}e_y+A_x)[e_x=0]+a_x,(A_{xy}e_x+A_y)[e_y=0]+a_y,A_{xy}[e_x=0][e_y=0]+a_{xy})$。

中间加的括号很重要，因为这个调了一下午。

然后我们考虑 $node$ 应该维护什么，看到这题是历史版本和，我们可以大胆猜测 $x,y$ 就表示 $\sum_{i=l}^rX_i,\sum_{i=l}^rY_i$。

然后我们尝试完成 $node_1+node_2$ 和 $node+tag$：

• $(x,y,s)+(X,Y,S)\to (x+X,y+Y,s+S)$。

对于 $node+tag$，我们首先可以写出 $(x,y)$ 的变化：

• 若 $e_x\neq0$ 且 $e_y\neq0$，$(x,y)+(e_x,e_y,a_c,a_x,a_y,a_{xy})\to(e_xp,e_yp)$。
• 若 $e_x\neq0$ 且 $e_y=0$，$(x,y)+(e_x,e_y,a_c,a_x,a_y,a_{xy})\to(e_xp,y)$。
• $e_y\neq0$ 的情况同理。
• 若 $e_x=0$ 且 $e_y=0$，$(x,y)+(e_x,e_y,a_c,a_x,a_y,a_{xy})\to(x,y)$。

对于 $s$ 的变化，由于我们之前给出的 $+$ 标记是原区间和的系数，我们可以写一个统一的式子（$p$ 为区间长度）：$s'=pa_c+xa_x+ya_y+?a_{xy}$。

我们遇到了一个问题，我们不知道该如何维护了。

但很明显 $?$ 处应当是 $\sum_{i=l}^rX_iY_i$，那我们就多维护一个这个，$node=(x,y,s,k=\sum_{i=l}^rX_iY_i)$。

• $(x,y,s,k)+(X,Y,S,K)\to (x+X,y+Y,s+S,k+K)$。

写出 $(x,y,k)$ 的变化：

• 若 $e_x\neq0$ 且 $e_y\neq0$，$(x,y,k)+(e_x,e_y,a_c,a_x,a_y,a_{xy})\to(e_xp,e_yp,e_xe_yp)$。
• 若 $e_x\neq0$ 且 $e_y=0$，$(x,y,k)+(e_x,e_y,a_c,a_x,a_y,a_{xy})\to(e_xp,y,e_xy)$。
• $e_y\neq0$ 的情况同理。
• 若 $e_x=0$ 且 $e_y=0$，$(x,y,k)+(e_x,e_y,a_c,a_x,a_y,a_{xy})\to(x,y,k)$。

$s$ 的变化：

• $s\gets s+pa_c+xa_x+ya_y+ka_{xy}$。

由此，我们便完成了双半群信息的构造。

P4314 CPU 监控

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

$n\le10^5$。

先想一些基础的维护：节点信息肯定要至少要维护 $(m,p)$ 表示最大值和历史最大值，标记信息至少要维护 $(a,e)$ 表示区间加标记和区间赋值标记，我们把顺序定义为先加再赋值，这样我们可以轻易的合并标记。

然后利用区间历史最大值的套路我们需要在标记额外维护 $h$ 表示历史 $a$ 的最大值，同时我们需要另一个标记 $o$ 表示该区间被区间赋值后产生过的最大值。

$$(m,p)\cdot(M,P)\to(\max(m,M),\max(p,P))\\(m,p)\cdot(a,e,h,o)\to\left\{\begin{aligned}&(e,\max\{p,m+h,o\}),&&\text{if }e\\&(m+a,\max(p,m+h)),&&\text{else}\end{aligned}\right.\\(a,e,h,o)\cdot(A,E,H,O)\to\left\{\begin{aligned}&(a,E,h,\max\{o,e+H,O\}),&&e\wedge\ E\\&(a,e+A,h,\max(o,e+H)),&&e\wedge\neg E\\&(a+A,E,\max(h,a+H),O),&&\neg e\wedge E\\&(a+A,\varnothing,\max(h,a+H),\varnothing),&&\neg e\wedge\neg E\\\end{aligned}\right.$$

P3246 [HNOI2016] 序列

每次询问一个区间的所有子区间最小值的和。

$n\le 10^5$。

是 NOIP2022 比赛的弱化版。

离线扫描线，右端点右移时单调栈区间赋值更新最小值，则我们要求每个位置的历史和。

先想基础信息：$(s,p,l)$ 表示区间和，区间历史和，区间长，$(o,e,c)$ 表示本来的区间对历史和贡献 $o$ 次，区间赋值为 $e$，历史和每个位置加了 $c$ 的常数。

尝试推一下：

$$(s,p,l)\cdot(S,P,L)\to(s+S,p+P,l+L)\\(s,p,l)+(o,e,c)\to\left\{\begin{aligned}&(le,p+os+cl,l),&&e\\&(s,p+os+cl,l),&&\neg e\end{aligned}\right.\\(o,e,c)\cdot(O,E,C)\to\left\{\begin{aligned}&(o,E,c+C+Oe),&&e\wedge E\\&(o,e,c+C+Oe),&&e\wedge \neg E\\&(o+O,E,c+C),&&\neg e\wedge E\\&(o+O,\varnothing,c+C),&&\neg e\wedge\neg E\\\end{aligned}\right.$$

那就没问题了。

CF526F Pudding Monsters

给定一个排列，询问有多少个子区间满足值域上连续。

$n\le 3\times 10^5$。

我们化一化式子：

$\max-\min+1=r-l+1\iff \max-\min\ +\ l=r$。

（把 $l$ 挪到左边是因为我们需要考虑扫描线枚举 $r$。）

然后因为这是一个排列，所以有 $\max-\min\ +\ l\ge r$。

于是你发现你可以用单调栈把前缀取 $\max,\min$ 变成区间加减，于是你要做的就是区间加，区间求 $\min$，区间求 $\min$ 的个数。

做完了。

CF997E Good Subsegments

上面那题改成区间询问。

其实就是把 $\min$ 的个数这件事给历史和一下，且子区间 $\min=$ 该区间 $\min$ 时才将历史和标记下传。

但这个玩意方便历史和吗。

我们尝试一下。

设 $(m,c,p)$ 表示区间 $\min$、区间 $\min$ 的个数、区间历史和，$(a,h)$ 表示区间加了多少，区间 $\min$ 的个数应该贡献给历史和多少。

$$(m,c,p)\cdot(M,C,P)\to(\min(m,M),c[m\le M]+C[M\le m],p+P)\\(a,h)\cdot(A,H)\to(a+A,h+H)\\(m,c,p)\cdot(a,h)\to(m+a,c,p+ch)$$

你发现设计出标记系统其实是比较简单的，唯一不同的点其实是下传标记。

---

文太长了，吉司机单开了，与树的结合鸽了。

参考资料

从《楼房重建》出发浅谈一类使用线段树维护前缀最大值的算法