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

标签：begin end 线段 矩阵 bmatrix 区间 sum 乘法

车人去 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\) 的线段树。

标签：begin,end,线段,矩阵,bmatrix,区间,sum,乘法
From： https://www.cnblogs.com/lfyszy/p/18680755