李超线段树(Li Chao Tree)

李超线段树(Li Chao Tree)是一种特殊的线段树,用于维护平面上若干条直线或线段,并支持查询在给定横坐标处所有函数值的最大值或最小值。它以其提出者的名字命名,是斜率优化动态规划等问题的重要工具。

概述

许多优化问题最终归结为:向集合中不断插入形如 y 等于 kx 加 b 的一次函数,并多次询问某个横坐标处的函数最值。传统凸包维护(如单调队列斜率优化)对插入顺序有要求,而李超线段树不要求斜率或横坐标单调,插入任意直线都能正确处理,通用性更强。

核心原理

它以横坐标的取值范围作为线段树的下标区间,每个线段树节点存储一条在该区间中点处占优的候选线段:

• 插入一条新线段时,在对应区间递归下行,与节点已存线段比较。
• 在区间中点处保留较优的那条作为该节点的标记,较劣的那条根据两条线段在左右半区的胜负关系,递归下放到某一侧子区间。
• 由于每次插入最多向下递归对数层,单次插入复杂度为对数级;若插入的是线段而非整条直线,还需先定位区间,复杂度为对数平方级。
• 查询某点时,从根到叶累计沿途所有节点标记线段在该点的取值,取最优即为答案。

应用场景

李超线段树主要用于斜率优化类动态规划,当决策转移可写成一次函数、需要在某点求最值时特别有效。它还能配合可持久化或线段树合并处理更复杂的历史版本与树上问题,是竞赛中的常见高级数据结构。

常见问题

问:它和单调队列斜率优化相比有何优劣?答:单调队列常数更小,但要求横坐标和斜率单调;李超线段树不受此限制,能处理任意插入顺序,代价是多一个对数因子。

问:为什么每个节点只需保存一条线段?答:节点只需保证在其区间中点处取到当前最优,其余竞争者被下放到子区间,查询时沿路径累计即可得到全局最优,无需在单节点保存多条。