李超线段树学习笔记

Eric112 · 2025-01-16 14:58:16 · 算法·理论

李超线段树

例题：Link。

题意

要求在平面直角坐标系下维护两个操作，强制在线：

1. 在平面上加入一条线段。记第 i 条被插入的线段的标号为 i。
2. 给定一个数 k，询问与直线 x = k 相交的线段中，交点纵坐标最大的线段的编号。

思路

既然名字叫线段树，那么我们就要考虑一个节点存的是什么。

答：存横坐标在 l 至 r 的区间内的线段中点纵坐标最高值。

接下来分别考虑两个操作怎么做。

对于更新操作，有以下几种情况：

1. 扫到的区间在给出线段之外，直接返回。
2. 给出线段包括一部分扫到区间，往左右分别递归。
3. 扫到区间被完全包含，此时要再分几种情况。

对于上面的第 3 种，分为：

1. 给出线段两端纵坐标均大于扫到区间最优的，区间最优更新为当前线段。
2. 都不大于，返回。
3. 不符合前两种，中间点大于，此时交换区间最优与当前线段。若交换后左端点变劣，递归左边，右边同理。

时间复杂度为找到包括区间的 \log n 乘上更新线段的 \log n，共 \log ^ 2 n。

void update(int &p, int l, int r, int ql, int qr, int now){
    if (r < ql || l > qr) return;//未包括 
    if (!p) p = ++tot; int mid = l + r >> 1;
    if (ql <= l && qr >= r){//完全包括 
        if (check(now, t[p].mx, l) && check(now, t[p].mx, r)){t[p].mx = now; return;}//两端均大于 
        if (check(t[p].mx, now, l) && check(t[p].mx, now, r)) return; //两端均小于   
        if (check(now, t[p].mx, mid)) swap(now, t[p].mx); //中间点大于
        if (check(now, t[p].mx, l)) update(t[p].l, l, mid, ql, qr, now); //左端大于，递归左边 
        if (check(now, t[p].mx, r)) update(t[p].r, mid + 1, r, ql, qr, now); //右端同理 
    }else update(t[p].l, l, mid, ql, qr, now), update(t[p].r, mid + 1, r, ql, qr, now); //未完全包括，继续递归 
}//插入线段，O(n log^2 n) 

查询操作就比较简单了，从根节点区间一直找到询问点，对于路上所有区间取 \max，因为李超线段树节点中存的是中点纵坐标最高值，不一定等于答案。

void query(int l, int r, int p, int k){
    if (!p || k > r || k < l) return;
    if (check(t[p].mx, ans, k)) ans = t[p].mx;//沿路比较所有可能是答案的线段 
    if (l == r) return; int mid = l + r >> 1;
    query(l, mid, t[p].l, k), query(mid + 1, r, t[p].r, k);
}

Code

练习与应用

Blue Mary 开公司

Link

这题也算是李超线段树的模板题，只不过这题由插入线段变成了插入直线，时间复杂度为 O(n \log n)。

void update(int &p, int l, int r, int now){
    if (!p) p = ++tot; int mid = l + r >> 1;
    if (check(now, t[p].mx, l) && check(now, t[p].mx, r)) {t[p].mx = now; return;}
    if (check(t[p].mx, now, l) && check(t[p].mx, now, r)) return; if (l == r) return;
    if (check(now, t[p].mx, mid)) swap(t[p].mx, now);
    if (check(now, t[p].mx, l)) update(t[p].l, l, mid, now);
    if (check(now, t[p].mx, r)) update(t[p].r, mid + 1, r, now);
}//插入线段 O(n log n)

Code

Building Bridges

Link

李超线段树比较直观的运用就是斜率优化了，这题就是很好的例子。

我们很容易写出 O(n ^ 2) 的 dp，设 s 代表 w 的前缀和，有：

还是拆 \min 里的式子，有：

设 k = -2h_j, x = h_i, b = f_j + {h_j} ^ 2 - s_j，有：

接下来，我们观察 x 与 y 的单调性，发现在这题 x, y 均没有单调性，也就是之前说过的二分和单调队列都不管用了，难道没办法了吗？

实际上有，可以用平衡树维护凸包或 cdq 分治，但我都不会。这里讲如何用李超线段树做。

将题意转化一下，这里就变成了每次插入一条解析式为 kx + b 的直线，求在横坐标为 x 时纵坐标最大值，那么直接从前往后扫过去更新就行了，时间复杂度 O(n \log n)。

Code