浅谈ddp

warning，这不是一篇新手向博文，最适人群为学过但忘记此算法，本篇将帮助你的回忆

一、导入

顾名思义，动态动态规划（ddp）就是支持修改操作的dp问题，常见于带修改的树形dp，一般使用线段树套广义矩阵乘法来实现

二、前置知识

线段树、矩阵乘法、树剖什么的肯定要会鸭
在处理树形问题前，我们先解决简化版的线性问题——
例题：小白逛公园
这个题当然大部分人只会关注他的奇妙纯线段树解
这是一个最大子段和问题，如果不带修，我们绝大多数情况下是用dp直接解决的，
但是，请仔细思考一下，矩阵乘法其实是一类求解过程，它虽然看起来复杂，但却可以做到与很多算法等价，譬如$floyd$求最短路，
当然，它也可以用于求解最大子段和问题，我们维护两个值$f_i$，$g_i$，分别表示$i$之前的最大子段和 和 包含且恰好截至$i$的最大子段和，那么我们就可以根据广义矩阵乘法的定义设计出相应的矩阵，
即答案矩阵为：

$\begin{bmatrix} f&g&0 \end{bmatrix}$

而过程中的矩阵则为：

$\begin{bmatrix} 0&-\infty&-\infty\\ a_i&a_i&-\infty\\ 0&0&0 \end{bmatrix}$

这道题让我们算出区间的最大子段和，那乍一看我们的做法就没法得到答案了，其实不然
根据广义矩阵乘法的结合律，我们可以把计算过程拆分为初始答案矩阵和过程答案矩阵，我们发现，只要每次快速查询出一段区间的过程矩阵积，用初始的答案矩阵乘上即可，
那带修、支持区间查询，自然就需要线段树来维护，本题就做完了。