用矩阵维护的，没想到跑了 3s+。
求大佬帮助。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
typedef long long ll;
const ll mod=1e9;
const int maxn=2e5+5;
int n,m;
ll a[maxn];
struct Matrix{
    ll mp[2][2];
    void init(){
        memset(mp,0,sizeof mp);
    }
    void unit(){
        mp[0][1]=mp[1][0]=0;
        mp[0][0]=mp[1][1]=1;
    }
    void unit(ll x){
        mp[0][0]=mp[1][1]=x;
        mp[0][1]=mp[1][0]=0;
    }
    Matrix operator*(const Matrix& b)const{
        Matrix res;
        res.mp[0][0]=(mp[0][0]*b.mp[0][0]+mp[0][1]*b.mp[1][0])%mod;
        res.mp[0][1]=(mp[0][0]*b.mp[0][1]+mp[0][1]*b.mp[1][1])%mod;
        res.mp[1][0]=(mp[1][0]*b.mp[0][0]+mp[1][1]*b.mp[1][0])%mod;
        res.mp[1][1]=(mp[1][0]*b.mp[0][1]+mp[1][1]*b.mp[1][1])%mod;
        return res;
    }
    Matrix operator*(const ll& b)const{
        Matrix res;
        res.mp[0][0]=mp[0][0]*b%mod;
        res.mp[0][1]=mp[0][1]*b%mod;
        res.mp[1][0]=mp[1][0]*b%mod;
        res.mp[1][1]=mp[1][1]*b%mod;
        return res;
    }
    Matrix operator+(const Matrix& b)const{
        Matrix res;
        res.mp[0][0] = mp[0][0]+b.mp[0][0];
        if(res.mp[0][0]>=mod)res.mp[0][0]-=mod;
        res.mp[0][1] = mp[0][1]+b.mp[0][1];
        if(res.mp[0][1]>=mod)res.mp[0][1]-=mod;
        res.mp[1][0] = mp[1][0]+b.mp[1][0];
        if(res.mp[1][0]>=mod)res.mp[1][0]-=mod;
        res.mp[1][1] = mp[1][1]+b.mp[1][1];
        if(res.mp[1][1]>=mod)res.mp[1][1]-=mod;
        return res;
    }
}emp;
Matrix fib_base[maxn];
struct SGT{
    Matrix val[maxn<<2];
    ll lazy[maxn<<2];
    int lef[maxn<<2],rig[maxn<<2];
    int len(int pos){
        return rig[pos]-lef[pos]+1;
    }
    void pushup(int pos){
        val[pos]=val[pos<<1]+val[pos<<1|1]*fib_base[len(pos<<1)];
   //     printf("[%d,%d]: lef %lld rig %lld\n",lef[pos],rig[pos],val[pos<<1].mp[0][0],(fib_base[len(pos<<1)]*val[pos<<1|1]).mp[0][0]);
      //  printf("[%d,%d] rig: \n%lld %lld\n%lld %lld\n",lef[pos],rig[pos],fib_base[len(pos<<1)].mp[0][0],fib_base[len(pos<<1)].mp[0][1],fib_base[len(pos<<1)].mp[1][0],fib_base[len(pos<<1)].mp[1][1]);
    }
    void bd(int pos,int l,int r){
        lef[pos]=l,rig[pos]=r;
        if(l==r){
            val[pos].unit(a[l]);
      //      printf("single %d\n",l);
        //    (fib_base[1]*val[pos]).print();
            return;
        }
        int mid=(l+r>>1);
        bd(pos<<1,l,mid);
        bd(pos<<1|1,mid+1,r);
        pushup(pos);
    }
    void add(int pos,ll _add){
        val[pos]=val[pos]+fib_base[len(pos)-1]*_add;
        lazy[pos]+=_add;
        lazy[pos]%=mod;
    }
    void pushdown(int pos){
        if(lazy[pos]){
            add(pos<<1,lazy[pos]);
            add(pos<<1|1,lazy[pos]);
            lazy[pos]=0;
        }
    }
    void cov(int pos,int x,ll _v){
        if(lef[pos]==rig[pos]){
            val[pos].unit(_v);
            return;
        }
        pushdown(pos);
        int mid=(lef[pos]+rig[pos]>>1);
        if(mid>=x)cov(pos<<1,x,_v);
        else cov(pos<<1|1,x,_v);
        pushup(pos);
    }
    void chg(int pos,int l,int r,ll _add){
        if(lef[pos]==rig[pos]){
            add(pos,_add);
            return;
        }
        pushdown(pos);
        int mid=(lef[pos]+rig[pos]>>1);
        if(mid>=l)chg(pos<<1,l,r,_add);
        if(mid<r)chg(pos<<1|1,l,r,_add);
        pushup(pos);
    }
    pair<Matrix,int> query(int pos,int l,int r){
        if(rig[pos]<l||lef[pos]>r)return mkpr(emp,0);
        if(lef[pos]>=l&&rig[pos]<=r){
    //       printf("val[%d,%d] = %lld\n",lef[pos],rig[pos],val[pos].mp[0][0]);
            return mkpr(val[pos],len(pos));
        }
        pushdown(pos);
        int mid=(lef[pos]+rig[pos]>>1);
        bool f1=(mid>=l),f2=(mid<r);
        if(f1){
            auto res=query(pos<<1,l,r);
            if(f2){
                auto res2=query(pos<<1|1,l,r);
                res.fi=res.fi+res2.fi*fib_base[res.se];
                res.se+=res2.se;
            }
            return res;
        }else if(f2){
            return query(pos<<1|1,l,r);
        }
    }
}sgt;
void solve(int id_of_test){
    scanf("%d%d",&n,&m);
    FOR(i,1,n){
        scanf("%lld",&a[i]);
    }
    fib_base[0].unit();
    fib_base[1].mp[0][0]=1;
    fib_base[1].mp[0][1]=1;
    fib_base[1].mp[1][0]=1;
    FOR(i,2,n){
        fib_base[i]=fib_base[i-1]*fib_base[1];
    }
    sgt.bd(1,1,n);
  //  printf("%lld\n",sgt.query(1,1,2).mp[0][0]);
    FOR(i,1,m){
        int op;
        scanf("%d",&op);
        if(op==1){
            int x,v;
            scanf("%d%d",&x,&v);
            sgt.cov(1,x,v);
        }else if(op==2){
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",sgt.query(1,l,r).fi.mp[0][0]);
        }else{
            int l,r,d;
            scanf("%d%d%d",&l,&r,&d);
            sgt.chg(1,l,r,d);
        }
    }
}
int main()
{
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}