最大部分配列問題(連続部分列の総和の最大値)をセグ木に載せる

これを事前に読んで欲しいです。
分割統治法の方針でセグ木に乗せられます
これにより、

が出来ます

$( (左端を含む最大部分配列),(右端を含む最大部分配列),(区間の最大部分配列),(区間の総和))$
からなるベクトルを考えると、これがモノイドになっています。

試しにベクトル $s$ とベクトル $t$ をくっつけて $s\times t$ を作ってみます。

$(sの左端を含む最大部分配列)$
$(sの区間の総和)+(tの左端を含む最大部分配列)$
の2つが条件を満たすので、ｍaxを取ります
右端も同様です

中央をまたぐやつとまたがないやつを考える分割統治法の王道により
$(sの最大部分配列)$
$(tの最大部分配列)$
$(sの右端を含む最大部分配列)+(tの左端を含む最大部分配列)$
のmaxです

$(sの総和)+(tの総和)$
それはそう

よって上手くセグ木に乗せられます(モノイドの要件を満たすのは意味論より明らか)

ps.この方法によって s*t*u=max(0,max(0,s+t),u)みたいな演算をモノイドとして処理出来たりもします(kadaneのアルゴリズムより)