用于解决一些 $\text{dp}$ 递推式简单但需要支持修改的问题，时间复杂度为 $O(nk^3\log n)$，其中 $k$ 为递推式的相关项。
给定一个长度为 $n$ 的十进制数 $D$。
设 $a_i$ 表示 $A$ 从低到高的第 $i$ 位，其他定义类同。$A+B$ 表示字符串 $\{a_n+b_n\cdots a_2+b_2,a_1+b_1\}$。
例如 $3248+908=\{3+0,2+9,4+0,8+8\}=\{3,11,4,16\}=311416$。
接下来 $q$ 次修改，每次修改 $D$ 的某一位，问每次修改后有多少组 $(A,B)$ 满足 $A+B=D$。
从低位到高位考虑 $\text{dp}$。设 $\text{dp}(i)$ 表示 $A+B=D[1,i]$ 的方案数。
若 $d_i$ 不是通过进位得到的，则有 $\text{dp}(i)\gets (d_i+1)\text{dp}(i-1)$。
若 $d_i$ 是通过进位得到的，则有 $\text{dp}(i)\gets [10\le d_id_{i-1}\le 18](19-d_id_{i-1})\text{dp}(i-2)$。
于是有状态转移方程
$$ \begin{bmatrix}(d_i+1) & [10\le d_id_{i-1}\le 18](19-d_id_{i-1}) \\1 & 0 \\ \end{bmatrix} \begin{bmatrix}\text{dp}(i-1)\\ \text{dp}(i-2)\end{bmatrix} =\begin{bmatrix}\text{dp}(i)\\ \text{dp}(i-1)\end{bmatrix} $$
注意每次更新需要更新 $i,i+1$ 两个位置的矩阵，另外把 $d_0$ 设置成 $19$ 防止影响位置 $1$ 的矩阵。另外初始值为
$$ \begin{bmatrix}\text{dp}(0)\\ \text{dp}(-1)\end{bmatrix} =\begin{bmatrix}1\\ 1\end{bmatrix} $$
最后还有一点：矩阵乘法不满足交换律，而我们是从左往右 $\text{dp}$，所以线段树 $\text{push_up}$ 的时候需要用右区间矩阵乘上左区间矩阵。
总时间复杂度 $O(q\log n)$。
给定长度为 $n$ 的序列，接下来两种操作：
首先考虑如何进行 $\text{dp}$ 递推，设 $f(i)$ 表示所有 $[1,i]$ 的后缀的最大元素和，$g(i)$ 表示所有 $[1,i]$ 的连续子序列的最大元素和。
$$ f(i)=\max(f(i-1)+a_i,a_i),g_i=\max(g(i-1),f(i))=\max(f(i-1)+a_i,g(i-1),a_i) $$
考虑用广义矩阵乘法维护转移，线段树要求广义矩阵乘法需要满足结合律。
$$ \begin{equation}\begin{split} (ABC)_{i,j}&=\sum_{k=1}^n (AB)_{i,k}\oplus C_{k,j} \\ &=\sum_{k=1}^n \left(\left(\sum_{t=1}^nA_{i,t}\oplus B_{t,k}\right)\oplus C_{k,j}\right)\\ & =\sum_{k=1}^n\sum_{t=1}^nA_{i,t}\oplus B_{t,k}\oplus C_{k,j}\\ & =\sum_{t=1}^n\left(A_{i,t}\oplus\left(\sum_{k=1}^nB_{t,k}\oplus C_{k,j}\right)\right)\\ & =\sum_{t=1}^nA_{i,t}\oplus (BC)_{t,j}\\ \end{split}\end{equation} $$ 不难发现，为了使得上式成立，应该有 $a\oplus\sum_{i=1}^n b_i=\sum_{i=1}^n a\oplus b_i$。
普通矩阵乘法中 $\sum$ 表示求和，$\oplus$ 表示乘法。本题可以用 $\max$ 代替 $\sum$，$+$ 代替 $\oplus$。
于是有
$$ \begin{bmatrix}a_i & -\infty & a_i \\a_i & 0 & a_i \\-\infty & -\infty & 0 \\ \end{bmatrix} \begin{bmatrix}f(i-1)\\g(i-1)\\0\end{bmatrix} =\begin{bmatrix}f(i)\\g(i)\\0\end{bmatrix} $$
注意查询的初始值和正常 $\text{dp}$ 相同
$$ \begin{bmatrix}f(0)\\g(0)\\0\end{bmatrix} =\begin{bmatrix}0\\-\infty\\0\end{bmatrix} \text{或}\begin{bmatrix}-\infty\\-\infty\\0\end{bmatrix} $$
ps. 这题从左往右 $\text{dp}$ 和从右往左 $\text{dp}$ 状态转移完全相同，所以 $\text{push_up}$ 写反也不影响正确性，但要注意 $\text{query}$ 和 $\text{push_up}$ 的一致性。
给定一棵点权树，每次修改一个点的点权后查询最大权独立集。
首先考虑不带修的情况，设 $f(u,0/1)$ 表示不选择/选择 $u$ 时 $u$ 的子树的最大独立集，于是有
$$ f(u,0)=\sum_{v\in son(u)}\max(f(v,0),f(v,1))\\ f(u,1)=w_u+\sum_{v\in son(u)}f(v,0) $$
然后考虑怎么将树型 $\text{dp}$ 转化为序列 $\text{dp}$，很容易想到用仅用重儿子进行转移。
设 $g(u,0/1)$ 表示删除重儿子及其子树后不选择/选择 $u$ 时 $u$ 的子树的最大独立集。记 $u$ 的重儿子为 $h$，于是有
$$ f(u,0)=\max(f(h,0),f(h,1))+g(u,0)\\ f(u,1)=f(h,0)+g(u,1)\\ \begin{bmatrix}g(u,0) & g(u,0) \\g(u,1) & -\infty \\ \end{bmatrix} \begin{bmatrix}f(h,0)\\ f(h,1)\end{bmatrix} =\begin{bmatrix}f(u,0)\\ f(u,1)\end{bmatrix} $$
重链的末端点均为叶子结点，于是要查询 $f(u,0/1)$，只需要查询 $u$ 到 $u$ 所在重链末端点的叶子结点所代表的矩阵的乘积即可。
对于叶子结点，有
$$ \begin{bmatrix}f(h,0)\\ f(h,1)\end{bmatrix} =\begin{bmatrix}0\\ 0\end{bmatrix} $$
于是每次查询的时间复杂度为 $O(\log n)$。而对于修改操作，只需要维护所有 $g(u,0/1)$ 即可。
$$ g(u,0)=\sum_{v\in son(u)}^{v\neq h}\max(f(v,0),f(v,1))\\ g(u,1)=w_u+\sum_{v\in son(u)}^{v\neq h}f(v,0) $$
对 $u$ 的权值进行修改，只会影响 $u$ 的所有祖先结点的 $f$ 值，而重链上子节点的 $f$ 对祖先结点的 $g$ 不产生贡献。
于是每次只需要更新 $u$ 到根节点路径上所有轻边的父结点的 $g$ 即可，共 $O(\log n)$ 个父结点。
而更新 $g$ 只需要查询轻边对应的子节点的新旧 $f$ 值，然后减去旧值贡献再补上新值贡献即可，于是每次修改总复杂度 $O(\log^2 n)$。
需要注意儿子结点编号比父结点大，所以对应线段树上是从右向左转移，所以 $\text{push_up,query}$ 用左区间乘以右区间即可。
总时间复杂度 $O(q\log^2n)$。