浅谈李超线段树
huangzirui
2020-10-24 14:20:46
### 引入：
有时候我们被给定一些直线，需要求 $x=a$ 时最值的问题。
在某些斜率优化的题目中，这个问题经常出现。
一般的斜率优化题都满足一些单调性质，可以支持 $O(1) /O(\log n)$ 查询。
但是在失去了某些单调性后，就需要用数据结构维护。
#### 例：
给定一些柱子的高度 $h_i$ 与拆除它们的代价 $w_i$ ，你需要在柱子之间建立一些桥来连接 $1$ 号和 $n$ 号柱子并拆除没有连接桥的柱子。建立一座从 $i$ 到 $j$ 的桥需要花费 $(h_i-h_j)^2$ 的代价。求代价最小值。
$n \leq 10^5\ \ 0 \leq |w_i|,h_i \leq 10^6$
---
显然可以列出一个状态转移方程，设 $dp_x$ 为转移到 $x$ 号柱子并选择它的最小代价：
$$dp_x=min\{dp_i+(h_i-h_x)^2-W_i+W_x\}$$
其中 $W_x = \sum_{i=1}^{x-1}w_i$
那么可以转化成一个类似斜率优化的式子：
$$dp_x-W_x-{h_x}^2=dp_i+{h_i}^2-W_i-2h_ih_x$$
可以把每个转移点抽象为一条斜率为 $-2h_i$ ，截距为 $dp_i+{h_i}^2-W_i$ 的直线，需要求的就是 $x=h_x$ 时，$y$ 最小的直线。
这个问题是李超线段树的经典问题，要解决它，我们先要了解李超线段树。
---
### 李超线段树
简单来说，李超线段树和线段树类似，都是每个节点维护 $[L,R]$ 的最优值。但是与一般线段树不一样的是，每个节点的“最优线段”是满足在 $x=mid$ 时 $y$ 值最大/最小且覆盖了全区域的线段。
查询某个点 $x=a$ 的最优值时，只需要查询**所有满足 $L \leq a \leq R$ 的节点上的最优线段**，并求出它们的最优值即可。
这里以 [P4097](https://www.luogu.com.cn/problem/P4097) 为例说明。
代码实现如下：
```cpp
#define l(x) tree[x].l
#define ls(x) (tree[x].son[0])
#define rs(x) (tree[x].son[1])
#define ll long long
#define Mid ((L+R)>>1)
const double inf=1e18;
struct line{
double k,b;int id;
double calc(int x){return k*x+b;}
};
struct segment_tree{
int son[2];
line l;
}tree[maxn*8];
```
代码实现了直线和节点，其中 $\text{calc}(x)$ 是计算直线在 $x$ 时的 $y$ 值。
```cpp
void insert(int &root,int L,int R,int l,int r,line g){
if(!root)root=++cnt,tree[root]={0,0,0};
if(L==l && R==r){
if(l(root).calc(Mid)<g.calc(Mid))swap(l(root),g);
if(L!=R){
if(l(root).k<g.k)insert(rs(root),Mid+1,R,Mid+1,r,g);
else if(l(root).k>g.k)insert(ls(root),L,Mid,l,Mid,g);
}return;
}
if(r<=Mid)insert(ls(root),L,Mid,l,r,g);
else if(l>Mid)insert(rs(root),Mid+1,R,l,r,g);
else insert(ls(root),L,Mid,l,Mid,g),insert(rs(root),Mid+1,R,Mid+1,r,g);
}
```
代码实现了插入一条线段，这个操作的复杂度是 $O(\log^2S)$ 的。（$S$ 为值域）
首先，将一条线段分割为 $\log S$ 份，且每份都可以在线段树上找到一条对应的可以包含 $[L,R]$ 的节点。
然后判断是否可以取代原最优线段，如果是就把原最优线段下传，否则下传当前的线段，下传时需要分类讨论。
具体来说，如果当前的线段比最优线段差，假设当前线段是$\color{red}\text{红色}$，最优线段是$\text{\text{黑色}}$，那么：
（使用了 OI wiki 的图片）
如果当前线段斜率大于最优线段，那么只可能在右侧区间更优，直接下传。
同理，下传至左侧即可。
因此每条线段最多下传 $\log S$ 层，所以复杂度为 $O(\log^2S)$ 。
**注意：插入直线的复杂度为 $O(\log S)$ ！**
```cpp
inline line MAX(line a,line b,int x){
return a.calc(x)>b.calc(x) || (fabs(a.calc(x)-b.calc(x))<1e-9 && a.id<b.id)?a:b;
}
line find(int root,int L,int R,int x){
if(!root)return {0,0,0};
if(L==R)return l(root);
if(x<=Mid)return MAX(find(ls(root),L,Mid,x),l(root),x);
return MAX(find(rs(root),Mid+1,R,x),l(root),x);
}
```
代码实现了寻找一条 $x=a$ 时的最优线段，查找时**不应直接返回节点 $[a,a]$ 的线段**，而要返回所有**节点包含 $a$ 的线段**中最优的那个，才能保证正确性。复杂度显然是 $O(\log S)$ 的。
以上是李超线段树的基本操作。接下来讲一下例题：
---
### 例题
[[HEOI2013]Segment](https://www.luogu.com.cn/problem/P4097)
模板题，需要注意斜率不存在的情况。
[[CEOI2017]Building Bridges](https://www.luogu.com.cn/problem/P4655)
引入题。
这道题提示我们，在解决一些动态规划问题时，可以利用李超线段树维护转移过程。
一些其他的解决方法有 cdq 分治等，但是个人认为李超树更简单一些（
[[SDOI2016]游戏](https://www.luogu.com.cn/problem/P4069)
> “总是有出题人喜欢把序列上用线段树解决的题目出到树上，让选手强行写个树链剖分或树分治或某种动态树数据结构。 这种行为已经很无趣了。 所以我们想让大家知道，不光可以放在静态树上，动态仙人掌也是可以的。”
期待有出题人把李超线段树放到动态仙人掌上（