dp，即动态规划中有一类很重要的优化，叫做线段树优化。本文将介绍几种常见的类型及其套路和一些例题。
前置知识：线性 dp、线段树。
权值线段树优化 dp
此类题目的 dp 转移通常和数值的大小关系有关，以下将介绍几道权值线段树优化 DP 题。
CF597C Subsequences
给定一个 \(1\sim n\) 的排列 \(a\)，求 \(a\) 中长度为 \(m+1\) 的上升子序列个数（IS）。
\(1\le n\le 10^5\)，\(0\le m\le 10\)，\(1\le a_i\le n\)，答案不超过 \(8\times 10^{18}\)。
首先设计 dp，\(dp_{i,k}\) 表示以第 \(i\) 位为结尾，构成长度为 \(k\) 的 IS 的个数。
转移有
\[dp_{i,k}=\sum_{j=0}^{i-1} dp_{j,k-1} (a_j < a_i) \]如果没有 \(a_j < a_i\) 的限制，显然可以前缀和优化。那有了这个限制之后，是不是可以写成：
\[dp_{i,k}=\sum_{l=1}^{a_i - 1}\sum_{j=0}^{i-1} dp_{j,k-1} (a_j = l) \]如果令 \(s_{i,k,x}\) 表示 \(\sum_{j=0}^{i-1} dp_{j,k} (a_j = x)\)，那么有：
\[dp_{i,k}=\sum_{l=1}^{a_i - 1}s_{i,k,l} \]这时候就看的很清楚了，可以把 \(s_{i,k,l}\) 丢到线段树上的第 \(l\) 位。枚举 \(k\)，那么 \(dp_{i,k}\) 就是查线段树上 \(l\in [1,a_i-1]\) 的 \(\sum s_{i,k-1,l}\)。当然，树状数组也是完全可以的。
时间复杂度 \(\mathcal{O}(nk\log n)\)。
P3431 [POI2005] AUT-The Bus
（太简单所以懒得写）
CF474E Pillars
（太简单所以懒得写）
线段树优化 dp 决策
这类题的 dp 转移方程通常有一个贡献，这个贡献会随着决策点的变化而变化。这个时候可以考虑使用线段树优化 dp 的决策。