数据结构优化 DP
当 DP 转移形如“在一段历史状态中求最值”时，直接枚举前驱常为 O(n²)。应先代数变形，识别可维护的查询对象，再选择数据结构。
常用匹配
| 转移特征 | 维护结构 | 单次操作 |
|---|---|---|
| 前缀最值 | 变量/前缀数组 | O(1) |
| 动态前缀或区间最值 | 树状数组、线段树 | O(log n) |
| 按值域查询 LIS 型状态 | 离散化 + 树状数组 | O(log n) |
| 直线集合最优值 | 凸包/李超树 | O(log n) |
例：树状数组求 LIS
离散化 a[i] 后，dp[i]=1+max(dp[j]) (a[j]<a[i]) 变为查询值域前缀最大值，再在当前位置取 max 更新。
int ask(int x){int r=0;for(;x;x-=x&-x)r=max(r,bit[x]);return r;}
void add(int x,int v){for(;x<=m;x+=x&-x)bit[x]=max(bit[x],v);}
for(int x:a){ int p=rank(x); add(p,ask(p-1)+1); }使用流程
- 写出朴素状态与转移；
- 明确查询维度、更新时机和数据范围；
- 坐标大或有负数时先离散化；
- 严格处理“先查询后更新”，避免同层状态错误参与转移。
典型复杂度可由 O(n²) 降至 O(n log n)。整理自 XOJ《数据结构优化》。
