李超数支持动态插入线段/直线,查询单点极值。
算法思想
排除不可能成为最优解的,维护在当前区间能成为最优解的线段,即该线段在当前区间的某个取值上有最优解。
查询的时间复杂度是 \(O(\log n)\) 的,修改时通过替换和下放,也能达到 \(O(\log n)\) 的复杂度,区间修改能达到 \(O(\log^2 n)\),(证明:最多把每条直线的值域分到 \(\log n\) 个区间,每个区间最多把标记下传 \(\log n\)层,所以区间修改的复杂度为 \(O(\log ^2 n\))。
未完待续。
标签:log,复杂度,区间,最优,线段,李超树 From: https://www.cnblogs.com/XYini/p/17617093.html