学习笔记 - 暂别平衡树:李超线段树

以前做斜率不单调的斜率DP(或者说凸包优化),因为不知道CDQ分治怎么弄,然后就学了一下 Splay 的做法……

思想挺简单,但是写起来就…… :< 写完Splay过后又尝试用非旋Treap写,结果一直Wa几天都没调出来 QwQ

幸亏还有李超线段树~


# 斜率不单调的凸包优化

至于什么是凸包优化,也可以看看我写的博客 学习笔记 - 告别精度:从斜率优化到凸包优化(写得比较烂,reader们大概看一下了解意思就可以了)

凸包优化有几种层次:

  1. 插入线段的斜率单调,且询问点单调(也就是说插入线段斜率单减或单增,询问点只向一个方向移动):这样的话就可以用单调栈/队列 维护凸包(需要看单调性以及维护的是什么凸包),并且由于询问点单调,那么栈顶/队头就是最优转移点

    这样是线性 $O(n)$ 的。

  2. 插入线段的斜率单调,询问点不单调:只能保证最优转移点在维护的凸包上,但是不一定是队头/栈顶是最优的;于是需要在凸包上二分 找最优值。

    多了一个二分的复杂度 $O(n\log n)$。

  3. 插入线段的斜率不单调(询问点随便单不单调):插入的线段可能会插入到凸包的中间,所以单调栈/队列就不行了,此时可以用平衡树Splay 来插入并且查询。

    ——但是,还有一个更好用的东西叫做李超线段树


# 什么是李超线段树

先以一个问题引入:

在平面上有两种操作(强制在线):

  1. 插入一条表达式为 $l: y=kx+b$ 的直线,给出 $k,b$。
  2. 给出 $t$,求当前所有直线中与直线 $x=t$ 交点的纵坐标最大是多少($t\in[1,3\times10^5]$)。

有斜率优化/凸包优化基础的OIer们应该知道,直线取 max 应该是得到一个下凸包,像这样(黑色的):

jpg1

强制在线嘛……

李超线段树是什么?线段树,当然是要维护区间 $[l,r]$ 的一个信息,李超线段树维护的就是中点处最高的直线。

比如下图,区间 $[0,4]$ 的中点 $x=2$ 的最高直线为红色直线。

jpg2

利用这一信息,可以在 $O(\log n)$ 的复杂度内插入直线、查询与 $x=t$ 相交的最高点。(这里的 $n$ 指的是查询的 $t$ 的值域范围)


# 实现李超线段树

- 插入直线

李超线段树有一个非常重要的思想:标记永久化

于是我们可以这样实现李超线段树,假如要把直线 $l_1$ 插入某一区间:

  1. 如果当前区间还没有直线标记(不代表没有直线覆盖,因为标记永久化),那么就把标记记为 $l_1$;

  2. 如果 $l_1$ 完全覆盖原有线段,像这样(蓝色是 $l_1$,红色是原有线段):

    jpg3

    那么 $x=t\in[left,right]$ 与 $l_1$ 的交点一定高于原线段,于是把原有线段直接替换为 $l_1$;

  3. 如果 $l_1$ 被原有线段完全覆盖(就是2.反过来),那么 $l_1$ 一定没有原有线段优;这样的话就舍弃 $l_1$ 不做任何更新

  4. 如果 $l_1$ 和原有线段在 $[left,right]$ 中有交点,像这样:

    jpg4

    这种情况就无法确定 $x=t\in[left,right]$ 与哪条直线交点更高。根据李超线段树维护的信息,我们需要在两条直线中取与 $x=mid$ 交点更高的一条直线作为标记(也就是上图的黄色直线,剩下的那条就是绿色直线)。

    再判断交点:如果在左区间,那么绿色直线在左区间可能比黄色直线高,然后就尝试把绿色直线往左区间插入;右区间类似。

- 查询

由于是标记永久化,查询就比较类似于标记永久化的线段树。比如查询 $x=pos$ 的最高交点,那么就要从线段树一层层递归,直到递归到 $[pos,pos]$ 这个区间——把每个区间的最优线段的交点取 max。

比如这样:

jpg5

(下面的黄、绿、蓝、橙色线段表现了递归区间的过程)

可以看到橙色区间是没有对应的直线的……


# 源代码

- 插入直线

实际上并不会真的计算交点……精度差别太大了,可以参考下面的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//Calc(l,x) 是计算 l 这条直线在 x 位置的纵坐标
void Insert(int u,int lef,int rig,int now){ //now 是要插入的节点
//idx[u] 是 u 这个区间的最优线段标记
if(!idx[u]) {idx[u]=now;return;}
int &org=idx[u];
if(Calc(org,lef)<Calc(now,lef) && Calc(org,rig)<Calc(now,rig)){org=now;return;}
//完全覆盖
if(Calc(org,lef)>=Calc(now,lef) && Calc(org,rig)>=Calc(now,rig)) return;
//被完全覆盖
int mid=(lef+rig)>>1;
if(Calc(org,lef)<Calc(now,lef)) swap(org,now); //暂时把标记设置为左端点较高的
if(Calc(org,mid)>Calc(now,mid)) Insert(u<<1|1,mid+1,rig,now); //画一下图可以知道交点在右区间
else swap(org,now),Insert(u<<1,lef,mid,now);
}

- 查询

就非常直白了……

1
2
3
4
5
6
7
//强行设置 Calc(0,x) 为 -INF (awa)
int Query(int u,int lef,int rig,int x){
if(lef==rig) return Calc(idx[u],x);
int mid=(lef+rig)>>1;
if(x<=mid) return max(Query(u<<1,lef,mid,x),Calc(idx[u],x));
else return max(Query(u<<1|1,mid+1,rig,x),Calc(idx[u],x));
}

# 后续

为了使李超线段树更棒 (<-_<-),就需要很多优化:

  1. 离散化:就可以缩小线段树维护的区间范围了;而且很好理解它的正确性;
  2. 动态开点:懒人必备,只是指针的占用的空间略大;
  3. 可持久化:李超线段树“不可减”,但是加上可持久化就可以撤回了~

嗨呀,忘了还有什么了……就这样吧


The End

Thanks for reading!

咕咕咕……

0%