李超线段树
算法简介
一个支持动态加入折线段和查询某个区间内所有折线段最高/最低点的数据结构。
算法模板
全局修改单点查询
题意
支持以下两种操作：
- 加入直线 $y=kx+b$
- 询问当前所有直线在 $x_0$ 处的最大值
题解
考虑线段树维护坐标轴，每个区间维护一条直线。当一个区间加入一条新直线时，若该区间原来没有直线，则直接用新直线覆盖。
否则，考虑新旧直线的优势长度，这里一条直线的优势长度定义该直线作为区间更优解的长度。
通过比较区间中点的取值可以得到优势长度更大的直线，然后将该区间用优势长度更大的直线的线段覆盖。
另外，优势长度更大的直线一定是整个左区间或整个右区间的更优解，而在另一个区间新旧直线可能各自占用一部分长度的更优解。
于是需要将被取代的直线下放到两个线段自占用一部分长度的更优解的区间来更新答案。
对于查询操作，类似懒标记永久化的线段树，递归过程中不停更新最优解即可。时间复杂度 $O(q\log n)$。
区间修改单点查询
题意
支持以下两种操作：
- 加入线段 $(x_0,y_0)\to (x_1,y_1)$
- 询问所有与 $x=x_0$ 直线相交的线段中纵坐标最大的线段编号
题解
将线段拆成 $O(\log n)$ 个线段树上的区间，然后套用全局修改算法即可，于是修改操作时间复杂度变为 $O\left(q\log^2 n\right)$。
另外，对于斜率不存在的线段，可以将 $(x,y_0)\to (x,y_1)$ 转化为 $(x,\max(y_0,y_1))$。
区间修改区间查询
题意
给定一棵树，支持以下两种操作：
- $w(u)=\max(w(u),a\times \text{dis}(u,s)+b)(u\in s\to t)$
- 询问 $\max(w(u))(u\in s\to t)$
题解
考虑树剖转化为序列问题，接下来考虑处理更新操作。设 $d(u)$ 表示根节点到 $u$ 的距离，$p=\text{LCA}(s,t)$，分两种情况：
- $u\in p\to s$，此时有 $\text{dis}(u,s)=d(s)-d(u)$，代入得 $w(u)=-a\times d(u)+b+a\times d(s)$
- $u\in p\to t$，此时有 $\text{dis}(u,s)=d(s)+d(u)-2d(p)$，代入得 $w(u)=a\times d(u)+b+a\times (d(s)-2d(p))$
接下来考虑区间查询操作，需要动态维护区间最优解，同时查询过程需要考虑当前区间覆盖线段的影响。
算法例题
斜率优化 $\text{DP}$
题意
给定 $n$ 个点，第 $i$ 个点有两个权值 $h_i,w_i$。要求选定若干个点，记为 $a_1,a_2\cdots a_k$，其中 $1,n$ 号点必选。
费用为 $\sum_{i=1}^{k-1} (a_{i+1}-a_i)^2+\sum_{i \not \in a}w_i$。要求最小化费用。
题解
设 $s_i=\sum_{j=1}^i w_i$，$f(i)$ 表示 $n=i$ 的情况下的最小费用，于是有状态转移
$$ f(i)=\min\left(f(j)+\sum_{k=j+1}^{i-1}w_i+(h_i-h_j)^2\right)=\min\left(-2h_jh_i+f_j+h_j^2-s_j\right)+h_i+s_{i-1} $$
不难发现问题转化为求 $y=-2h_jx+f_j+h_j^2-s_j(j=1\sim i-1)$ 在 $x=h_i$ 处的最小值，李超线段树模板，时间复杂度 $O(n\log V)$。
