例题：最大子段和问题，区间询问版本。
https://www.luogu.com.cn/problem/SP1043
考虑 dp。
\[dp_{l} = a_l \\ dp_{i} = \max(dp_{i - 1} + a_i, a_i) \]根据矩阵乘法的重新定义，我们可以把它写成矩阵，其中“乘”->“加”，“加”->“\(\max\)”。也就是：
\[\begin{bmatrix} a_k & a_k \\ -\inf & 0\end{bmatrix} \begin{bmatrix} dp_{k-1} \\ 0\end{bmatrix} = \begin{bmatrix} dp_k \\ 0\end{bmatrix} \]考虑求
\[\begin{bmatrix} dp_R \\ 0\end{bmatrix} \]有
\[\begin{bmatrix} dp_R \\ 0\end{bmatrix} = \mathbf{A_R} \begin{bmatrix} dp_{R-1} \\ 0\end{bmatrix} = ... = \mathbf{A_R}\mathbf{A_{R-1}}...\mathbf{A_{L+1}} \begin{bmatrix} a_L \\ 0\end{bmatrix} \]也就是我们对于每次询问需要求出 $ \mathbf{A_R}\mathbf{A_{R-1}}...\mathbf{A_{L+1}}$。
怎么求？考虑我们做序列连续和怎么做。前缀和/差分；树状数组；线段树...
考虑前缀积，但是由于矩阵不一定存在逆（需要高斯消元方程有解），不行。
【待补充】
标签：...,begin,end,DP,bmatrix,mathbf,动态,dp From： https://www.cnblogs.com/Zeardoe/p/16915812.html