跳转至

# 李超线段树

## 引入

洛谷 4097 [HEOI2013]Segment

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

1. 在平面上加入一条线段．记第 𝑖 i 条被插入的线段的标号为 𝑖 i，该线段的两个端点分别为 (𝑥 0,𝑦 0)(x 0,y 0)，(𝑥 1,𝑦 1)(x 1,y 1)．
2. 给定一个数 𝑘 k，询问与直线 𝑥 =𝑘 x=k 相交的线段中，交点纵坐标最大的线段的编号（若有多条线段与查询直线的交点纵坐标都是最大的，则输出编号最小的线段）．特别地，若不存在线段与给定直线相交，输出 0 0．

数据满足：操作总数 1 ≤𝑛 ≤1 0 5 1≤n≤10 5，1 ≤𝑘,𝑥 0,𝑥 1 ≤3 9 9 8 9 1≤k,x 0,x 1≤39989，1 ≤𝑦 0,𝑦 1 ≤1 0 9 1≤y 0,y 1≤10 9．

我们发现，传统的线段树无法很好地维护这样的信息．这种情况下，李超线段树 便应运而生．

## 过程

我们可以把任务转化为维护如下操作：

- 加入一个一次函数，定义域为 [𝑙,𝑟][l,r]；
- 给定 𝑘 k，求定义域包含 𝑘 k 的所有一次函数中，在 𝑥 =𝑘 x=k 处取值最大的那个，如果有多个函数取值相同，选编号最小的．

注意

当线段垂直于 𝑥 x 轴时，会出现除以零的情况．假设线段两端点分别为 (𝑥,𝑦 0)(x,y 0) 和 (𝑥,𝑦 1)(x,y 1)，𝑦 0 <𝑦 1 y 0<y 1，则插入定义域为 [𝑥,𝑥][x,x] 的一次函数 𝑓(𝑥) =0 ⋅𝑥 +𝑦 1 f(x)=0⋅x+y 1．

看到区间修改，我们按照线段树解决区间问题的常见方法，给每个节点一个懒标记．每个节点 𝑖 i 的懒标记都是一条线段，记为 𝑙 𝑖 l i，表示要用 𝑙 𝑖 l i 更新该节点所表示的整个区间．

现在我们需要插入一条线段 𝑓 f，考虑某个被新线段 𝑓 f 完整覆盖的线段树区间．若该区间无标记，直接打上用该线段更新的标记．

如果该区间已经有标记了，由于标记难以合并，只能把标记下传．但是子节点也有自己的标记，也可能产生冲突，所以我们要递归下传标记．

如图，按新线段 𝑓 f 取值是否大于原标记 𝑔 g，我们可以把当前区间分为两个子区间．其中 肯定有一个子区间被左区间或右区间完全包含，也就是说，在两条线段中，肯定有一条线段，只可能成为左区间的答案，或者只可能成为右区间的答案．我们用这条线段递归更新对应子树，用另一条线段作为懒标记更新整个区间，这就保证了递归下传的复杂度．当一条线段只可能成为左或右区间的答案时，才会被下传，所以不用担心漏掉某些线段．

具体来说，设当前区间的中点为 𝑚 m，我们拿新线段 𝑓 f 在中点处的值与原最优线段 𝑔 g 在中点处的值作比较．

如果新线段 𝑓 f 更优，则将 𝑓 f 和 𝑔 g 交换．那么现在考虑在中点处 𝑓 f 不如 𝑔 g 优的情况：

1. 若在左端点处 𝑓 f 更优，那么 𝑓 f 和 𝑔 g 必然在左半区间中产生了交点，𝑓 f 只有在左区间才可能优于 𝑔 g，递归到左儿子中进行下传；
2. 若在右端点处 𝑓 f 更优，那么 𝑓 f 和 𝑔 g 必然在右半区间中产生了交点，𝑓 f 只有在右区间才可能优于 𝑔 g，递归到右儿子中进行下传；
3. 若在左右端点处 𝑔 g 都更优，那么 𝑓 f 不可能成为答案，不需要继续下传．

除了这两种情况之外，还有一种情况是 𝑓 f 和 𝑔 g 刚好交于中点，在程序实现时可以归入中点处 𝑓 f 不如 𝑔 g 优的情况，结果会往 𝑓 f 更优的一个端点进行递归下传．

最后将 𝑔 g 作为当前区间的懒标记．

下传标记：

实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    constexpr double eps = 1e-9;

    int cmp(double x, double y) {  // 因为用到了浮点数，所以会有精度误差
      if (x - y > eps) return 1;
      if (y - x > eps) return -1;
      return 0;
    }

    //...

    void upd(int root, int cl, int cr, int u) {  // 对线段完全覆盖到的区间进行修改
      int &v = s[root], mid = (cl + cr) >> 1;
      int bmid = cmp(calc(u, mid), calc(v, mid));
      if (bmid == 1 || (!bmid && u < v))  // 在此题中记得判线段编号
        swap(u, v);
      int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
      if (bl == 1 || (!bl && u < v)) upd(root << 1, cl, mid, u);
      if (br == 1 || (!br && u < v)) upd(root << 1 | 1, mid + 1, cr, u);
      // 上面两个 if 的条件最多只有一个成立，这保证了李超树的时间复杂度
    }

拆分线段：

实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    void update(int root, int cl, int cr, int l, int r,
                int u) {  // 定位插入线段完全覆盖到的区间
      if (l <= cl && cr <= r) {
        upd(root, cl, cr, u);  // 完全覆盖当前区间，更新当前区间的标记
        return;
      }
      int mid = (cl + cr) >> 1;
      if (l <= mid) update(root << 1, cl, mid, l, r, u);  // 递归拆分区间
      if (mid < r) update(root << 1 | 1, mid + 1, cr, l, r, u);
    }

注意懒标记并不等价于在区间中点处取值最大的线段．

如图，加入黄色线段后，只有红色节点的标记被更新，而绿色节点的标记还未被改变．但在第二、三、四个绿色区间的中点处显然黄色线段取值最大．

查询时，我们可以利用标记永久化思想，在包含 𝑥 x 的所有线段树区间（不超过 𝑂(l o g⁡𝑛)O(log⁡n) 个）的标记线段中，比较得出最终答案．

查询：

实现

    1
    2
    3
    4
    5
    6
    7
    8
    pdi query(int root, int l, int r, int d) {  // 查询
      if (r < d || d < l) return {0, 0};
      int mid = (l + r) >> 1;
      double res = calc(s[root], d);
      if (l == r) return {res, s[root]};
      return pmax({res, s[root]}, pmax(query(root << 1, l, mid, d),
                                       query(root << 1 | 1, mid + 1, r, d)));
    }

根据上面的描述，查询过程的时间复杂度显然为 𝑂(l o g⁡𝑛)O(log⁡n)，而插入过程中，我们需要将原线段拆分到 𝑂(l o g⁡𝑛)O(log⁡n) 个区间中，对于每个区间，我们又需要花费 𝑂(l o g⁡𝑛)O(log⁡n) 的时间递归下传，从而插入过程的时间复杂度为 𝑂(l o g 2⁡𝑛)O(log 2⁡n)．

[HEOI2013]Segment 参考代码

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    #include <iostream>
    constexpr int MOD1 = 39989;
    constexpr int MOD2 = 1000000000;
    constexpr int MAXT = 40000;
    using namespace std;
    using pdi = pair<double, int>;

    constexpr double eps = 1e-9;

    int cmp(double x, double y) {
      if (x - y > eps) return 1;
      if (y - x > eps) return -1;
      return 0;
    }

    struct line {
      double k, b;
    } p[100005];

    int s[160005];
    int cnt;

    double calc(int id, int d) { return p[id].b + p[id].k * d; }

    void add(int x0, int y0, int x1, int y1) {
      cnt++;
      if (x0 == x1)  // 特判直线斜率不存在的情况
        p[cnt].k = 0, p[cnt].b = max(y0, y1);
      else
        p[cnt].k = 1.0 * (y1 - y0) / (x1 - x0), p[cnt].b = y0 - p[cnt].k * x0;
    }

    void upd(int root, int cl, int cr, int u) {  // 对线段完全覆盖到的区间进行修改
      int &v = s[root], mid = (cl + cr) >> 1;
      int bmid = cmp(calc(u, mid), calc(v, mid));
      if (bmid == 1 || (!bmid && u < v)) swap(u, v);
      int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
      if (bl == 1 || (!bl && u < v)) upd(root << 1, cl, mid, u);
      if (br == 1 || (!br && u < v)) upd(root << 1 | 1, mid + 1, cr, u);
    }

    void update(int root, int cl, int cr, int l, int r,
                int u) {  // 定位插入线段完全覆盖到的区间
      if (l <= cl && cr <= r) {
        upd(root, cl, cr, u);
        return;
      }
      int mid = (cl + cr) >> 1;
      if (l <= mid) update(root << 1, cl, mid, l, r, u);
      if (mid < r) update(root << 1 | 1, mid + 1, cr, l, r, u);
    }

    pdi pmax(pdi x, pdi y) {  // pair max函数
      if (cmp(x.first, y.first) == -1)
        return y;
      else if (cmp(x.first, y.first) == 1)
        return x;
      else
        return x.second < y.second ? x : y;
    }

    pdi query(int root, int l, int r, int d) {  // 查询
      if (r < d || d < l) return {0, 0};
      int mid = (l + r) >> 1;
      double res = calc(s[root], d);
      if (l == r) return {res, s[root]};
      return pmax({res, s[root]}, pmax(query(root << 1, l, mid, d),
                                       query(root << 1 | 1, mid + 1, r, d)));
    }

    int main() {
      ios::sync_with_stdio(false);
      int n, lastans = 0;
      cin >> n;
      while (n--) {
        int op;
        cin >> op;
        if (op == 1) {
          int x0, y0, x1, y1;
          cin >> x0 >> y0 >> x1 >> y1;
          x0 = (x0 + lastans - 1 + MOD1) % MOD1 + 1,
          x1 = (x1 + lastans - 1 + MOD1) % MOD1 + 1;
          y0 = (y0 + lastans - 1 + MOD2) % MOD2 + 1,
          y1 = (y1 + lastans - 1 + MOD2) % MOD2 + 1;
          if (x0 > x1) swap(x0, x1), swap(y0, y1);
          add(x0, y0, x1, y1);
          update(1, 1, MOD1, x0, x1, cnt);
        } else {
          int x;
          cin >> x;
          x = (x + lastans - 1 + MOD1) % MOD1 + 1;
          cout << (lastans = query(1, 1, MOD1, x).second) << endl;
        }
      }
      return 0;
    }

## 合并

类似于普通线段树的合并，我们定义以下过程来将两个李超线段树节点 𝑢,𝑣 u,v 合并，并以 𝑢 u 作为新的根．

1. 如果 𝑣 v 为空，结束过程．

2. 如果 𝑢 u 为空，将 𝑣 v 复制给 𝑢 u．

3. 将 𝑣 v 对应线段插入到 𝑢 u 为根的子树．

4. 递归将 𝑢,𝑣 u,v 的左右子树对应合并．

若合并若干李超线段树涉及的总点数为 𝑛 n，则该过程的复杂度为 𝑂(𝑛 l o g⁡𝑛)O(n log⁡n)：对于任意线段在树上对应的节点，每次涉及移动它时，我们要么使其深度 +1+1，要么直接从树上删除，这两个操作的代价都是 𝑂(1)O(1) 的，而每个点深度至多为 𝑂(l o g⁡𝑛)O(log⁡n)，于是复杂度如上．

实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    void upd(int &root, int cl, int cr,
             int u) {  // 涉及多棵李超线段树合并，使用动态开点．
      static int idx = 0;
      if (!root) {
        s[root = ++idx] = u;
        return;
      }
      int &v = s[root], mid = (cl + cr) >> 1;
      int bmid = cmp(calc(u, mid), calc(v, mid));
      if (bmid == 1 || (!bmid && u < v)) swap(u, v);
      int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
      if (bl == 1 || (!bl && u < v)) upd(ls[root], cl, mid, u);
      if (br == 1 || (!br && u < v)) upd(rs[root], mid + 1, cr, u);
    }

    int merge(int &u, int &v, int l, int r) {
      if (!u || !v) {
        return u + v;
      }
      if (l == r) {
        int b = cmp(calc(s[v], l), calc(s[u], l));
        if (b == 1 || (!b && s[v] < s[u])) return v;
        return u;
      }
      upd(u, l, r, s[v]);
      int mid = (l + r) >> 1;
      ls[u] = merge(ls[u], ls[v], l, mid);
      rs[u] = merge(rs[u], rs[v], mid + 1, r);
      return u;
    }

## 习题

「JSOI2008」Blue Mary 开公司

「CodeChef」TSUM2 Sum on Tree

「USACO13MAR」Hill Walk G

「CF932F」Escape Through Leaf

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：StudyingFather, Tiphereth-A, do-while-true, iamtwz, aofall, c-forrest, ChungZH, codewasp942, CoelacanthusHex, Enter-tainer, henrytbtrue, HeRaNO, Ir1d, Jelefy, kenlig, ksyx, leoleoasd, Marcythm, mcendu, Persdre, shuzhouliu, usada-pekora-286
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用