动态DP
最大子段和
考虑设\(f_i\)表示以i为结尾的最大子段和，\(g_i\)表示i以内的最大子段和
\[f_i=\max(f_{i-1}+a_i,a_i) \]\[g_i=\max(g_{i-1},f_i) \]然后非常容易将每个权值变成一个矩阵，然后每次修改就变成修改一个矩阵
用线段树维护即可
树上最大独立集（没有上司的舞会带修）
考虑基础的做法，设\(f_{i,0/1}\)表示以i为根的子树中，i放/不放的最大独立集
\[f_{i,0}=\sum_{son}\max(f_{son,0},f_{son,1}) \]\[f_{i,1}=\sum_{son}f_{son,0} \]然后考虑带修，想到树剖
然后就可以再设\(f_{i,0/1}\)表示以i为根的子树（不包括i的重儿子）中，i放/不放的最大独立集
\[g_{i,0}=\sum_{son\in light}\max(g_{son,0},g_{son,1}) \]\[g_{i,1}=\sum_{son\in light}f_{son,0} \]然后为什么要把矩阵立起来？考虑到树剖的dfn序在链中，是上到下升序，so要倒过来（自行理解）
然后就可以简单的解决，因为修改时一个重链中的矩阵不会相互影响（g的DP转移式中可以看出）
时间复杂度\(O(q\log^2N)\)
标签：子段,max,sum,矩阵,son,动态,DP From： https://www.cnblogs.com/zhy114514/p/18024044