历史和线段树
例题：Loj P193 线段树历史和
您需要写一种数据结构，来维护一个有序数列，其中需要提供以下操作：
- 区间加一个数。
- 查询区间的历史和。
历史和定义为数列 $h_i$ 的区间和：初始 $h_i=a_i$，在每次操作（修改或查询）完成后，对所有 $h_i \leftarrow h_i+a_i$。
考虑使用线段树维护区间信息。
矩阵乘法
每一个线段树节点维护信息矩阵：
\[\begin{bmatrix}
\textit{history}\\
\textit{sum}\\
\textit{len}
\end{bmatrix}\]
其中，$\textit{history},\textit{sum},\textit{len}$ 分别表示区间历史和、区间和、区间长度。
合并节点可以直接相加。
-
区间加 $k$ 后更新区间和，有：
\[\begin{bmatrix}
1&0&0\\
0&1&k \\
0&0&1\\
\end{bmatrix}
\begin{bmatrix}
\textit{history}\\
\textit{sum}\\
\textit{len}
\end{bmatrix}
=
\begin{bmatrix}
\textit{history}\\
\textit{sum}+d\cdot\textit{len}\\
\textit{len}
\end{bmatrix}\]
-
更新区间历史和，有：
\[\begin{bmatrix}
1&1&0\\
0&1&0\\
0&0&1\\
\end{bmatrix}
\begin{bmatrix}
\textit{history}\\
\textit{sum}\\
\textit{len}
\end{bmatrix}
=
\begin{bmatrix}
\textit{history}+\textit{sum}\\
\textit{sum}\\
\textit{len}
\end{bmatrix}\]
线段树维护两种操作即可。
更新时只更新操作区间的区间和。操作结束后，更新全局的区间历史和。
参考代码
```cpp
//#include<bits/stdc++.h>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define int long long
constexpr const int N=1e5;
int n,a[N+1];
struct Matrix{
int n,m;
int a[3][3];
Matrix(int nn=-1,int mm=-1){
if(mm==-1){
mm=nn;
}
if(nn!=-1){
n=nn,m=mm;
}else{
n=0,m=0;
}
memset(a,0,sizeof(a));
}
Matrix(initializer_list<initializer_list> x){
n=x.size();m=0;
for(auto &i:x){
m=max(m,(int)i.size());
}
int pi=0;
for(auto &i:x){
int pj=0;
for(auto &j:i){
a[pi][pj]=j;
pj++;
}
pi++;
}
}
int* operator [](const int &x){
return a[x];
}
void unit(){
memset(a,0,sizeof(a));
for(int i=0;i<n;i++){
a[i][i]=1;
}
}
void print(){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<a[i][j]<<' ';
}
cout<<endl;
}
}
};
Matrix operator *(Matrix A,Matrix B){
Matrix C(A.n,B.m);
for(int i=0;i<A.n;i++){
for(int j=0;j<B.m;j++){
for(int k=0;k<A.m;k++){
C[i][j]+=A[i][k]*B[k][j];
}
}
}
return C;
}
Matrix& operator *=(Matrix &A,Matrix B){
return A=A*B;
}
Matrix operator +(Matrix A,Matrix B){
Matrix C(A.n,A.m);
for(int i=0;i<A.n;i++){
for(int j=0;j<A.m;j++){
C[i][j]=A[i][j]+B[i][j];
}
}
return C;
}
Matrix& operator +=(Matrix &A,Matrix B){
for(int i=0;i<A.n;i++){
for(int j=0;j<A.m;j++){
A[i][j]+=B[i][j];
}
}
return A;
}
struct segTree{
struct node{
int l,r;
Matrix value,tag;
int size(){
return r-l+1;
}
}t[N<<2|1];
void up(int p){
t[p].value=t[p<<1].value+t[p<<1|1].value;
}
void build(int p,int l,int r){
t[p]={l,r};
t[p].tag=Matrix(3);
t[p].tag.unit();
if(l==r){
t[p].value={ {a[l]},{a[l]},{1} };
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
up(p);
}
void down(int p){
t[p<<1].value=t[p].tag*t[p<<1].value;
t[p<<1].tag=t[p].tag*t[p<<1].tag;
t[p<<1|1].value=t[p].tag*t[p<<1|1].value;
t[p<<1|1].tag=t[p].tag*t[p<<1|1].tag;
t[p].tag.unit();
}
void update(int p,int l,int r,Matrix pl){
if(l<=t[p].l&&t[p].r<=r){
t[p].value=pl*t[p].value;
t[p].tag=pl*t[p].tag;
return;
}
down(p);
if(l<=t[p<<1].r){
update(p<<1,l,r,pl);
}
if(t[p<<1|1].l<=r){
update(p<<1|1,l,r,pl);
}
up(p);
}
int query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].value[0][0];
}
down(p);
int ans=0;
if(l<=t[p<<1].r){
ans=query(p<<1,l,r);
}
if(t[p<<1|1].l<=r){
ans+=query(p<<1|1,l,r);
}
return ans;
}
}t;
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
t.build(1,1,n);
while(m--){
int op,l,r,x;
cin>>op;
switch(op){
case 1:
cin>>l>>r>>x;
t.update(1,l,r,{ {1,0,0},{0,1,x},{0,0,1}});
break;
case 2:
cin>>l>>r;
cout<<t.query(1,l,r)<<'\n';
break;
}
t.update(1,1,n,{ {1,1,0},{0,1,0},{0,0,1}});
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
## 懒标记
自行拆解矩阵乘法即可。
但是矩阵乘法可以天然避免操作顺序等其他问题。
## 问题转化
设 $t$ 为当前版本，维护 $c_i=h_i-t\cdot a_i$。
记 $t'=t-1$ 为操作前的版本，则将区间 $[l,r]$ 增加 $k$，对于 $i\in[l,r]$，有：
$$
c_i\leftarrow c_i-t'\cdot k
$$
因此维护 $c_i$ 的区间加法即可。
