浅谈李超线段树

浅谈李超线段树

概论

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

• 在平面上加入一条线段。
  
• 给定一个数 \(k\)，询问与直线 \(x = k\) 相交的线段的交点的纵坐标最值。
  

李超线段树就是能够维护以上两个操作的数据结构。
基本概念

首先需要明确：李超树是一种线段树，它的一个节点存储的是一个区间 \([l,r]\) 上值最大的线段的编号的懒标记。
为什么说是懒标记？就是指这条线段并不一定最大（小），而是可能取到最值。
这就需要谈到，李超线段树是一种基于标记永久化的线段树。
标记永久化就是指修改时一路更改被影响到的节点，询问时则一路累加路上的标记，从而省去标记上传下传的操作。
也就是说，我们不保证存储 \([l,r]\) 的节点的编号一定在整个区间上取到最值，但保证对于任意 \(x=p\) ，结合所有包含 \(p\) 的区间 \([l,r]\) 取最值一定可以取到 \(p\) 的最值。
举个例子，假设现在横坐标范围是 \([1,4]\)，对于 \(x=2\)，我们需要保证区间 \([1,4]\)、\([1,2]\)，\([2,2]\) 中存储的线段编号至少有一个在 \(x=2\) 可以取到最值，也就是说取这三个区间的最值就是这个点的最值。
以上就是标记永久化的思想，可以方便修改，也不会使查询复杂度升高。
插入直线

我们先来考虑插入直线，即覆盖整个区间的线，下面默认取最大值，最小值同理。
分类讨论，对于每一个区间 \([l,r]\)：
<ul>若区间 \([l,r]\) 没有直线覆盖，直接将标记改为这条直线的编号然后返回即可。
若区间 \([l,r]\) 有直线覆盖，考虑此区间的懒标记所表示的直线 \(f\) 和插入的直线 \(g\)，不妨令原来的懒标记直线 \(f\) 在中点 \(mid\) 处取值大，即 \(f(mid)\ge g(mid)\)（代码上，如果插入线段在中点处取值大就和懒标记 swap 即可）。<ul>
如果 \(f(l)\ge g(l)\) 则在左区间 \([l,mid]\) 上 \(f\) 一定不比 \(g\) 劣，也就是说 \(g\) 对左区间最值不可能有影响，不需要再递归处理左区间，右区间同理。
如果 \(f(l) eps)        {                swap(k, dat[x]);        }        if (p[k].calc(l) - p[dat[x]].calc(l) > eps)        {                update(ls, l, mid, k);        }        if (p[k].calc(r) - p[dat[x]].calc(r) > eps)        {                update(rs, mid + 1, r, k);        }}[/code]插入线段

与插入直线不同的是，插入线段有定义域的限制。
与普通线段树一样，我们可以把要插入的区间分成至多 \(\log n\) 个在线段树上的区间，然后对每一个被插入区间包含的区间像插入直线一样下传标记即可。

线段树区间操作的本质就是将一个区间分成至多 \(\log n\) 个在线段树上的区间
—— KevinLikesCoding 大神

代码：

1. struct line
2. {
3.         double k, b;
4.         int id;
6.         inline double calc(int x)
7.         {
8.                 return k * x + b;
9.         }
10. } p[N];
12. void update(int x, int l, int r, int k)
13. {
14.         if (!dat[x])
15.         {
16.                 dat[x] = k;
17.                 return;
18.         }
19.         if (p[k].calc(mid) - p[dat[x]].calc(mid) > eps)
20.         {
21.                 swap(k, dat[x]);
22.         }
23.         if (p[k].calc(l) - p[dat[x]].calc(l) > eps)
24.         {
25.                 update(ls, l, mid, k);
26.         }
27.         if (p[k].calc(r) - p[dat[x]].calc(r) > eps)
28.         {
29.                 update(rs, mid + 1, r, k);
30.         }
31. }

复制代码

查询最值

根据标记永久化的性质，我们只需递归遍历所有包含这个点的区间再取最大值即可。
代码（需要说明的是，我这里建了一个虚拟线段 \(0\)，如果 dat[x]==0，\(res\) 就会被赋值为虚拟线段在 \(k\) 处的值，最大值就赋值为负无限，最小值赋值为正无限即可）：

1. void update(int x, int l, int r, int ql, int qr, int k)
2. {
3.     if (r < ql || l > qr)
4.     {
5.         return;
6.     }
7.     if (ql <= l && r <= qr)
8.     {
9.         if (!dat[x])
10.         {
11.             dat[x] = k;
12.             return;
13.         }
14.         if (p[k].calc(mid) - p[dat[x]].calc(mid) > eps)
15.         {
16.             swap(k, dat[x]);
17.         }
18.         if (p[k].calc(l) - p[dat[x]].calc(l) > eps)
19.         {
20.             update(ls, l, mid, ql, qr, k);
21.         }
22.         if (p[k].calc(r) - p[dat[x]].calc(r) > eps)
23.         {
24.             update(rs, mid + 1, r, ql, qr, k);
25.         }
26.         return;
27.     }
28.     update(ls, l, mid, ql, qr, k);
29.     update(rs, mid + 1, r, ql, qr, k);
30. }

复制代码

例题

【模板】李超线段树 / [HEOI2013] Segment

题目描述

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

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

本题输入强制在线。
数据范围

对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^5\)，\(1 \leq k, x_0, x_1 \leq 39989\)，\(1 \leq y_0, y_1 \leq 10^9\)。
解题思路

李超线段树板子，上面已经讲的很清楚了。
代码

1. double query(int x, int l, int r, int k)
2. {
3.     if (r < k || l > k)
4.     {
5.         return INT_MIN;
6.     }
7.     double res = p[dat[x]].calc(k);
8.     if (l == r)
9.     {
10.         return res;
11.     }
12.     return max(res, max(query(ls, l, mid, k), query(rs, mid + 1, r, k)));
13. }

复制代码

结语

恭喜你学会了李超线段树！
可以看到，我给出的李超线段树的例题只有一道板子，这是因为单独应用李超线段树的题目很少，李超线段树大多都和斜率化一起使用。
有关斜率优化的内容，我在 浅谈斜率优化 中都有讲到，欢迎继续学习！

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！