使用矩阵乘法维护的线段树

车人去 WC 了，找了一个巴蜀毕业的哈工大大三学生来给他代课。

那就简单记录一下每天都讲了什么吧

CF GYM103470 Paimon Segment Tree

给定一个长度为 $n$ 的序列 $a$，以及 $m$ 次区间加操作和 $q$ 次询问（在处理完所有操作后再询问）。
询问操作：假设 $a_{i,j}$ 表示进行完第 $j$ 次操作后 $a_i$ 的值。给定 $l_k,r_k,x_k,y_k$ 查询

$$\sum^{r_k}_{i=lk}\sum^{y_k}_{j=x_k} a^2_{i,j}$$

显然可以想到的一步是，将询问离线下来差分第二个 $\sum$，就可以转化成求解历史区间平方和。

接着考虑如何维护，首先处理平方：

$$\sum (a+k)^2=\sum (a^2+2ak+k^2)$$

则只需维护区间的 0 次，1 次，2 次和与历史区间平方和。

构造一个矩阵 $data$：

$$\begin{bmatrix} len & sum & qsum & hsum \end{bmatrix}$$

对于区间加操作，相当于对区间的 $data$ 乘上:

$$\begin{bmatrix} 1 & k & k^2 & 0\\ 0 & 1 & 2k & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}$$

同时一次修改后，我们还要对整体用以下矩阵操作一次来累加 $hsum$

$$\begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 \end{bmatrix}$$

时间复杂度 $O((m+q)\log n\times4^3)$，需要卡常。

一个很智慧的应用是，我们可以自己模拟矩乘的过程来减少常数，当然你会发现这就变成了普通的维护 $tag$ 的线段树。