浅谈李超线段树

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 的代价。求代价最小值。

显然可以列出一个状态转移方程，设 dp_x 为转移到 x 号柱子并选择它的最小代价：

其中 W_x = \sum_{i=1}^{x-1}w_i

那么可以转化成一个类似斜率优化的式子：

可以把每个转移点抽象为一条斜率为 -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 为例说明。

代码实现如下：

#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 值。

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) ！

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

模板题，需要注意斜率不存在的情况。

[CEOI2017]Building Bridges

引入题。

这道题提示我们，在解决一些动态规划问题时，可以利用李超线段树维护转移过程。

一些其他的解决方法有 cdq 分治等，但是个人认为李超树更简单一些（

[SDOI2016]游戏

“总是有出题人喜欢把序列上用线段树解决的题目出到树上，让选手强行写个树链剖分或树分治或某种动态树数据结构。 这种行为已经很无趣了。 所以我们想让大家知道，不光可以放在静态树上，动态仙人掌也是可以的。”

期待有出题人把李超线段树放到动态仙人掌上（