浅谈李超线段树的另一种实现方法

TianyiLemon · 2022-04-30 14:59:53 · 算法·理论

update on 2022/7/24：更正了一些错误。

update on 2022/10/26：上日报了，重构了第二部分。笔者已经高二了，不知道 12 月时还是否机会营业。

前置知识：线段树、标记永久化。

0x10 李超线段树

我们需要维护一个数据结构，支持以下两种操作：

• 插入一条线段，定义域为 [l,r]。
• 求所有与 x=x_0 相交的线段中，交点纵坐标最大的那条。

李超线段树的思想是：在每个线段树区间上维护一条 “主导线段”。

定义一条线段在 x 处最优，当且仅当该线段在 x 处的取值大于其它任何线段。

定义一条线段为区间 [l,r] 上的主导线段，当且仅当：

1. 该线段的定义域完全覆盖 [l,r]。
2. 该线段在区间 [l,r] 中点处最优。

查询:

李超线段树的查询使用标记永久化的思想：将所有包含 x_0 线段树区间的 “主导线段” 拿出来比较，找出最优的一条，时间复杂度为 O( \log n)。

int query(int p,int x){
    if(l(p)==r(p))return dom(p);
    int mid=l(p)+r(p)>>1,ans=x<=mid?query(p<<1,x):query(p<<1|1,x);
    if(val(dom(p),x)>=val(ans,x))ans=dom(p);//val 就是求点值
    return ans;
}

更新:

更新的经典实现使用了分类讨论的思想。

首先，把新插入线段分为 O(\log n) 个不相交的线段树区间。

void modify(int p,int id){
    int l=L[id].l,r=L[id].r;//新插入线段的左右端点
    if(l<=l(p)&&r(p)<=r){upd(p,id);return;}//完全覆盖
    int mid=l(p)+r(p)>>1;
    if(l<=mid)modify(p<<1,id);
    if(r>mid)modify(p<<1|1,id);
}

对于每个划分出来的区间，考虑新线段 id 和原主导线段 dom。

如果 id 在区间中点处的值大于 dom，交换 id 和 dom。

接下来分类讨论新的 id 和 dom 的斜率 k:

1. 此时 $id$ 在右半区间一定不优，递归左半区间即可。 
2. 同理，递归右半区间即可。 
3. 可以直接返回，也可以任意归入 1 或 2 的情况。

到叶节点直接返回。

void upd(int p,int id){
    int mid=l(p)+r(p)>>1;
    double now_mid=val(id,mid),pre_mid=val(id,mid);
    if(now_mid>pre_mid)swap(dom(p),id);
    if(l(p)==r(p))return;
    if(L[dom(p)].k>L[id].k)upd(p<<1,id);//比较斜率
    else upd(p<<1|1,id);
}

比较主流的实现方法还会特判掉新线段在整个区间都比原线段更优或更劣的情况，进一步减小算法常数。实际上，这种剪枝就是本文后面要讨论的核心。

复杂度:

一条线段被分到 O(\log n) 个区间上，每次 upd 的复杂度为 O(\log n)，所以总复杂度为 O(\log^2 n)。

如果每条线段都覆盖了整个线段树值域，总的复杂度就是 O(\log n)。

空间复杂度为 O(n)。

0x20 另一种实现方法

我们重新审视一下上文提到的剪枝：如果新线段在整个线段树区间上都优于原线段，这时可以把区间的主导线段改成新线段，然后直接返回。不妨称这种情况为 “完全碾压”。类似地可以定义 “完全被碾压”。

新版实现的核心是：我们特判掉完全碾压或被碾压的情况后，可以直接向两边递归，不必再判断中点处值的大小或分类讨论斜率。

void upd1(int p,int id){
    double now_l=val(id,l(p)),now_r=val(id,r(p)),pre_l=val(dom(p),l(p)),pre_r=val(dom(p),r(p));
    if(now_l<=pre_l&&now_r<=pre_r)return;//完全被碾压，不可能成为主导线段
    if(now_l>=pre_l&&now_r>=pre_r){dom(p)=id;return;}//完全碾压
    upd1(p<<1,id);upd1(p<<1|1,id);
}

测试证明，这种实现是正确的。因为往下递归时左右儿子中一定有一个会直接返回，所以复杂度也是正确的。

问题是，这样一来原先 “主导线段” 的定义就不成立了，下文中尝试给出了一个新的定义和正确性说明。

更改 “主导线段” 的第二条定义：

2. 插入该线段时，它在区间 [l,r] 上“完全碾压”之前的所有线段，且 [l,r] 是满足这样条件的极大区间。

注：插入新线段后，原先 [l,r] 上的主导线段可能在 [l,r] 的某个子区间上不完全碾压新插入的线段，但它依然是 [l,r] 上的主导线段。

关于这种实现的正确性，我们只需要说明：如果一条线段在 x 处最优，那么它必定在某个包含 x 的线段树区间上是主导线段。这一点可以用反证法说明。

小结:

这里所讲的 “另一种实现方法” 本质是对经典版李超线段树的向下递归部分作了一些优化，或者说提供一种新的写法，笔者并没有进一步深入挖掘它的本质。希望本文能起到抛砖引玉的作用，让更多人了解这一种实现，甚至能够作进一步的探索。

虽然新版代码稍短，运行常数较小，但是经典版也具有实现自然、容易理解的优点。读者可以自行评判两种实现的优劣。

这种实现方法是笔者做题的时候发现的，部分参考了一篇题解（见参考资料）。由于笔者数据结构水平很低，文中难免有错误和疏漏，欢迎批评指正。

附：segment代码（远古）

0x30 李超线段树合并

只要考虑怎么合并信息。

其实就是先递归合并左右儿子，然后把一个节点的主导线段插入到另一个节点上。

upd 用任意一种实现都行。

int merge(int p,int q,int l,int r){
    if(!p||!q)return p|q;
    int mid=l+r>>1;
    lc(p)=merge(lc(p),lc(q),l,mid);
    rc(p)=merge(rc(p),rc(q),mid+1,r);
    upd(p,dom(q),l,r);
    return p;
}

这个的应用就是维护树上的斜率优化 DP 之类的。

复杂度分析和之前类似：

设初始有 n 条线段。

如果每条线段都覆盖整个线段树值域，那么一条线段最多被下放 O(\log n) 层，时间复杂度 O(n\log n)。

如果每条线段定义域任意，相当于一条线段被分到 O(\log n) 个区间上，总的时间复杂度 O(n\log ^2 n)。（暂时没有见过这样的题）

0x40 一些题

1. 模板题：[HEOI2013]Segment。

2. 李超线段树维护凸包，和平衡树，cdq 分治相比有常数小、易实现等优点。

   • [JSOI2008]Blue Mary开公司
   • [CEOI2017]Building Bridges
   • [NOI2007] 货币兑换

3. 结合树剖的模板题：[SDOI2016]游戏

4. 李超线段树的合并：Escape Through Leaf

更多题目可以参考这个题单。

可以发现，李超线段树能解决的题大都非常套路化。

0x50 参考资料

1. 李超线段树 - OI Wiki
2. 李超线段树 - jklover 的博客