前言

“李超线段树，简称李超树。它支持插入 直线 或 线段，并查询某个横坐标处的 最值。”

本文以最大值为例，讨论广义李超线段树，与传统的李超线段树不同，它插入的是 函数 而非直线或线段，但为了保证正确的时间复杂度，对函数有较严格限制，见条件。

不展开讨论对于 \(x=k\) 时函数值相等时的具体处理，可依题意而定。

正文

广义李超线段树可以 在线 解决下述问题添加 函数 \(f_i\) 或给定 \(x\) 求 \(\max\{f_i(x)\}\).

条件

定义 \(f(x)\) 和 \(g(x)\) 的大小关系交换为从 \(f(x)>g(x)\) 变为 \(f(x)<g(x)\)，或反之，则有：当 \(f\) 和 \(g\) 的大小关系交换次数 \(\le 1\) 时，函数 \(\text{v}(f,g)=1\)，否则 \(\text{v}(f,g)=0\) 。当函数集合 \(F\) 满足 \(\forall \alpha,\beta\in F,\text{v}(\alpha,\beta)=1\)，则 \(F\) 可以用李超线段树维护。

过程

• 考虑区间 \([l_i,r_i]:\)

  1. 去除区间绝对劣势函数 \(f_{\text{bad}}:\forall x\in[l_i,r_i],f_{\text{bad}}(x)<f_{\text{tag}_i}(x)\)，一定不是解；

  2. 保留优势函数 \(f_{\text{tag}_i}:\forall \phi,f_{\text{tag}_i}(m_i)>\phi(m_i)\) 不下放；

  3. 下放相对优势函数 \(f_{\text{good}}:\exists x\in[l_i,r_i],f_{\text{good}}(x)>f_{\text{tag}_i}(x),\text{good}\neq\text{tag}_i\) 至子区间，条件保证其在某一区间绝对劣势。

以上是插入新函数时区间需要做的事，时间复杂度 \(O(\log V)\).

• 考虑整体：
  1. 叶子节点 \([w,w]\) 的函数中除了其区间优势函数，其他都是绝对劣势函数，会被筛掉（不考虑相同）；
  2. 非叶子节点，除区间优势函数和绝对劣势函数，其他函数都下放直至成为区间绝对劣势函数，或区间优势函数留在某结点；
  3. 相对优势函数不会存在。

查询 \(k\) 时是在所有剩下的 \(\log V\) 个区间的优势函数，即非绝对劣函数内选取最大，这显然正确，时间复杂度 \(O(\log V)\).

实现

核心思想是维护 区间最优函数，及时排除不优答案，实现时，维护 \(\text{tag}_i\) 表示 \([l_i,r_i]\) 的最优函数编号，即定义域完全覆盖 \([l_i,r_i]\) 并且在 \(m_i=\dfrac{l_i+r_i}{2}\) 处 取值最大 的函数。

不考虑定义域，插入函数 \(f_j\)，设当前区间为 \([l_i,r_i]\)，中点为 \(m_i\)。若 \(f_j(m)>f_{\text{tag}_i}(m)\)，则 \(f_j\) 比 \(f_{\text{tag}_i}\) 更优，交换 \(\text{tag}_i\) 和 \(j\)；讨论 \(f_j(m)<f_{\text{tag}_i}(m)\)：若 \(f_j(l_i)>f_{\text{tag}_i}(l_i)\) ，则 \(f_j,f_{\text{tag}_i}\) 大小关系交换发生在 \((l_i,m_i)\)，向 \([l_i,m_i]\) 递归插入 \(f_j\)；同理，若 \(f_j(r_i)>f_{\text{tag}_i}(r_i)\) ，则 \(f_j,f_{\text{tag}_i}\) 大小关系交换发生在 \((m_i,r_i)\)，向 \((m_i,r_i]\) 递归插入 \(f_j\)；否则，\(f_j\) 在该区间绝对劣势，舍去。

根据 Condition，两个分支至多进入一个，因此时间复杂度 \(O(\log V)\)，\(V\) 为定义域。

查询 \(x=k\) 的答案，需要找到线段树上从 \([1,V]\) 到 \([k,k]\) 的路径 \(\text{Path}\)，则 \(\text{ans}=\max\limits_{i\in\text{Path}} f_{\text{tag}_i}(k)\)；时间复杂度 \(O(\log V)\).

引用

Alex_Wei 的 线段树合集 \(\text{Section}\) 李超线段树。

Hanghang007 和不知名大佬的 广义李超线段树。

注：只有一个交点非必要条件，反例见下；请参考 Content#Condition.

附注：由于保证 \(F\) 满足 \(\forall \alpha,\beta\in F,\text{v}(\alpha,\beta)=1\) 构造随机函数是困难的，所以广义李超线段树更多用于维护题目给出的近似线性或有良好性质的图形。