动态 dp
泛化ψ(｀∇´)ψ
动态 dp 大概是这样的一类问题，你有一个 dp 题，现在每次带修，你需要支持多次询问，每次回答这种情况下的 dp 值，或者是询问某个区间的 dp 值。
如果我们每次暴力修改，都需要重新计算 dp，复杂度是 \(O(qT)\) 的，其中 \(O(T)\) 是在原问题中计算 dp 所需的时间复杂度。
可以注意到，其实有一些 dp 值在我们修改之后仍然是不变的，我们能否找出所有会变化的子问题呢？
然后就要用到一个比较人类智慧的技巧，我们知道所有 dp 转移都可以写作矩阵乘法的形式，我们把 dp 方程写作广义矩阵乘法的样子。
如果能写成正确的广义矩阵乘法，意思是这个新的矩阵运算仍旧满足结合律，我们就可以观察到，问题可以转化为，求出一个区间的 dp 值实际上是对 \(O(len)\) 个矩阵做广义矩阵乘法，那么我们每次修改就只需要找到修改对应的矩阵利用数据结构维护即可。
然后需要注意的是，我们新定义的矩阵运算有结合律的前提是广义乘法满足对广义加法的分配律。
比如乘法对加法有分配律，加法对 \(\max\) 有分配律。
然后还有就是因为存在奇异矩阵这种没有逆的矩阵，所以我们不能用 BIT 这种数据结构维护，只能拿线段树一类的数据结构维护。
这么说有点抽象，放两个题来看看
单点修改区间最大子段和ψ(｀∇´)ψ
首先考虑没有修改没有区间怎么做。
设 \(dp(i)\) 表示以 \(i\) 结尾的最大子段和。
\(dp(i) = \max\limits_{k < i}\{dp(k) + a(i), a(i)\}, dp(1) = a(1)\)。
设 \(ans(i)\) 表示前缀 \(i\) 的答案：\(ans(i) = \max(ans(i - 1), dp(i)), ans(1) = dp(1) = a(1)\)。
然后考虑没有单点修改，有区间查询怎么做。
考虑把转移写成一个 \(A_{k - 1} \times T_{k} \to A_{k}\) 的形式，其中 \(A\) 是包含 \(dp(), ans()\) 的一个列向量，不妨假设就为 \(\begin{bmatrix}dp(k)\\ans(k)\end{bmatrix}\)。
然后尝试把转移矩阵 \(T\) 写出来。
注意到这里不能使用一般的矩阵乘法，因为有个 \(\max\) 操作，我们不妨换成 \((\max, +)\) 的广义矩阵乘法。
然后就是：
尝试把转移方程表达出来，用列向量的话就是，结果的第 \(i\) 个位置就是转移矩阵的第 \(i\) 行和原来的列向量对应相乘。
呃呃，好像只表示了 \(dp(k - 1) + a(k)\)，没表示出 \(a(k)\)。
那么只能加一个位置了，\(0\) 那边是好处理的。
然后你发现我们不太好处理 \(ans(k)\) 那里的 \(dp(k)\)，因为原来的列向量 \(A_{k - 1}\) 里没有。
咋办呢，把 dp 的转移带进来就行了，于是变成：
然后每一个位置就对应一个转移矩阵 \(T_k = \begin{bmatrix} a(k) & -\infty & a(k)\\ a(k) & 0 & a(k) \\ -\infty & -\infty & 0 \\\end{bmatrix}\)
于是你发现列向量 \(A\) 之间存在关系，比如 \(A_l \to A_r\)，乘上一个 \(\prod\limits_{i = l + 1}^{r}T_i\) 就行了，这部分广义乘积可以用线段树一类的数据结构维护。
于是单次询问就是直接查 \(A_r[0, 1]\) 了，这个可以做到 \(O(\log n)\) 带一个 \(3^3\) 的常数。
单点直接改矩阵对应位置就行，也是 \(O(\log n)\) 的。
实现应该很好做，就略过了。
动态树上最大权独立集ψ(｀∇´)ψ
没有上司的舞会那一题的动态版本，支持单点修改权值。
很显然这也是一个板子，我在此直接给出转移矩阵了，然后树剖可以 \(O(\log^2n)\) 维护，LCT 只要 access 可以 1log 但是我不会 LCT。
下面大部分来自 OI wiki，因为我们树链剖分维护的是重链，所以需要把方程改写成和重链信息相关的样子。
设 \(g_{i,0}\) 表示不选择 \(i\) 且只允许选择 \(i\) 的轻儿子所在子树的最大答案，\(g_{i,1}\) 表示不考虑 \(son_i\) 的情况下选择 \(i\) 的最大答案，\(son_i\) 表示 \(i\) 的重儿子。
假设我们已知 \(g_{i,0/1}\) 那么有 DP 方程：
答案是 \(\max(f_{root,0},f_{root,1})\).
可以构造出矩阵：
注意，我们这里使用的是广义乘法规则。
可以发现，修改操作时只需要修改 \(g_{i,1}\) 和每条往上的重链即可。
然后记得维护一下重链的末端点，转移的时候需要用到。