题意：给你一个数列a，a[i]表示斐波那契数列的下标为a[i]，求区间对应斐波那契数列数字的和，还要求能够维护对区间内所有下标加d的操作
分析：线段树
线段树的每个节点表示（f[i],f[i-1]）这个数组
因为矩阵的可加性，所以可以进行lazy操作
我最开始的想法是每个节点lazy表示该区间下标加了多少，add表示该区间已经加的下标对应的矩阵乘积，这样更新lazy是O(1)的，算add是O(logn)的
但是这样每次pushdown的时候,add下传总要多个log，会TLE
更好的办法是lazy表示加的下标对应的矩阵乘积，这样虽然每次更新lazy是O(logn)的，但是pushdown的时候就是直接把(f[i],f[i-1])和lazy[2][2]乘起来了，是O(1)的
代码：
#include<bits/stdc++.h>
const int maxn=1e5;
const long long mod=1e9+;
int ch[maxn*+][];
long long sum[maxn*+][],add[maxn*+][][],a[maxn+];
int len=,n,m;
void mer(long long a[][],long long b[][])
{
long long s[][];
memset(s,,sizeof(s));
for(int i=;i<;++i)
for(int j=;j<;++j)
for(int k=;k<;++k)
s[i][j]=(s[i][j]+a[i][k]*b[k][j]%mod)%mod;
for(int i=;i<;++i)
for(int j=;j<;++j)
a[i][j]=s[i][j];
}
void fib(long long num[][],long long x)
{
long long a[][]={{,},{,}};
num[][]=,num[][]=,num[][]=,num[][]=;
while(x)
{
if(x&) mer(num,a);
mer(a,a);
x>>=;
}
}
void cal(long long sum[],long long s[][])
{
long long x=(sum[]*s[][]%mod+sum[]*s[][]%mod)%mod;
long long y=(sum[]*s[][]%mod+sum[]*s[][]%mod)%mod;
sum[]=x,sum[]=y;
}
void pushdown(int k)
{
if(add[k][][]==&&add[k][][]==&&add[k][][]==&&add[k][][]==) return;
//printf("A");
//cal(sum[k],add[k]);
int l=ch[k][],r=ch[k][];
if(l) mer(add[l],add[k]),cal(sum[l],add[k]);
if(r) mer(add[r],add[k]),cal(sum[r],add[k]);
add[k][][]=,add[k][][]=,add[k][][]=,add[k][][]=;
}
void update(int k)
{
int l=ch[k][],r=ch[k][];
//cal(sum[k],add[k]);
//pushdown(k);
for(int i=;i<;++i) sum[k][i]=(sum[l][i]+sum[r][i])%mod;
// if(k==2) printf("A : %d %d %lld %lld\n",l,r,sum[l][0],sum[r][0]);
}
int build(int l,int r)
{
if(l>r) return ;
int mid=(l+r)>>;
int k=++len;
add[k][][]=,add[k][][]=,add[k][][]=,add[k][][]=;
if(l==r)
{
sum[k][]=,sum[k][]=;
long long num[][];
fib(num,a[l]-);
cal(sum[k],num);
//printf("%d %d %d %d %d\n",l,r,k,ch[k][0],ch[k][1]);
return k;
}
ch[k][]=build(l,mid);
ch[k][]=build(mid+,r);
update(k);
return k;
// printf("%d %d %d %d %d\n",l,r,k,ch[k][0],ch[k][1]);
}
void make(int k,int l,int r,int x,int y,long long num[][])
{
if(l>r) return;
if(l>y||r<x) return;
if(x<=l&&y>=r)
{
mer(add[k],num);
cal(sum[k],num);
return;
}
int mid=(l+r)>>;
pushdown(k);
if(l<=mid) make(ch[k][],l,mid,x,y,num);
if(r>mid) make(ch[k][],mid+,r,x,y,num);
update(k);
}
long long query(int k,int l,int r,int x,int y)
{
if(l>r) return ;
if(l>y||r<x) return ;
if(x<=l&&y>=r)
{
return sum[k][];
}
int mid=(l+r)>>;
pushdown(k);
return (query(ch[k][],l,mid,x,y)+query(ch[k][],mid+,r,x,y))%mod;
}
int main()
{ scanf("%d %d",&n,&m);
for(int i=;i<=n;++i) scanf("%lld",&a[i]);
build(,n);
//for(int i=1;i<=len;++i) printf("%d %lld %lld\n",i,sum[i][0],sum[i][1]);
//or(int i=1;i<=len;++i) printf("%d %lld %lld %lld %lld\n",i,add[i][0][0],add[i][0][1],add[i][1][0],add[i][1][1]);
for(int i=;i<=m;++i)
{
int t,l,r;
long long x;
scanf("%d %d %d",&t,&l,&r);
if(t==)
{
scanf("%lld",&x);
long long num[][];
fib(num,x);
make(,,n,l,r,num);
}
else printf("%lld\n",query(,,n,l,r));
}
return ;
}