题意

参考这篇博客。

看到区间问题首先考虑线段树，之后考虑如何合并区间：

比如我们现在求出了区间\([l,mid]\)和区间\([mid+1,r]\)的答案，现在我们要求出\([l,r]\)的答案，我们需要使\([mid+1,r]\)的答案中每个斐波那契系数的下标加上\(mid-l+1\)，这个看似无法处理，我们不妨先考虑只让下标加\(1\)的情况。

对于区间\([l,r]\)：
设\(s_i=\sum\limits_{j=0}^{r-l}f_{j+i}a_j\)，那么在区间\([l,r]\)上记录的答案就是\(s_0\)。
\(s_{i-1}+s_{i-2}\)
\(=\sum\limits_{j=0}^{r-l}f_{j+i-1}a_j+\sum\limits_{j=0}^{n}f_{j+i-2}a_j\)
\(=\sum\limits_{j=0}^{r-l}(f_{j+i-1}+f_{j+i-2})a_j\)
\(=\sum\limits_{j=0}^{r-l}f_{j+i}a_j\)
\(=s_i\)
即\(s_i=s_{i-1}+s_{i-2}\)。

于是我们现在能从\(s_{i-1}\)和\(s_{i-2}\)转移到\(s_i\)，但是我们显然不能在线段树上递推或者记录所有的\(s_i\)，因此考虑如何用\(s_0\)和\(s_1\)推出所有\(s_i\)。

不妨设\(s_0=A,s_1=B\)，那么有：
\(s_2=s_0+s_1=1A+1B=f_0A+f_1B\)
\(s_3=s_1+s_2=1B+1A+1B=f_1A+f_2B\)
\(s_4=s_2+s_3=(f_0+f_1)A+(f_1+f_2)B=f_2A+f_3B\)
\(...\ ...\)
\(f_i=f_{i-2}A+f_{i-1}B\)

即\(f_i=f_{i-2}s_0+f_{i-1}s_1\)

那么我们对每个节点维护\(s_0,s_1\)即可，现在我们可以合并区间了。

区间加的话，我们肯定是打标记，假设对\([l,r]\)区间加\(k\)。

\(s'_0=\sum\limits_{j=0}^{r-l}f_j*(a_j+k)\)
\(=\sum\limits_{j=0}^{r-l}f_ja_j+\sum\limits_{j=0}^{r-l}f_jk\)

同理，\(s'_1=\sum\limits_{j=0}^{r-l}f_{j+1}a_j+\sum\limits_{j=0}^{r-l}f_{j+1}k\)

我们只要求一个斐波那契数列的前缀和，之后对区间的\(s_0,s_1\)加上上面的那个只跟\(k\)有关的东西就好了。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define s0(p) (seg[p].s0)
#define s1(p) (seg[p].s1)
#define tag(p) (seg[p].tag)
const int maxn=2e5+10;
const int mod=1000000000;
int n,m;
ll a[maxn],fib[maxn],sum[maxn];
struct Seg{ll s0,s1,tag;}seg[maxn<<2];
inline void up(int p,int l,int r)
{
    int mid=(l+r)>>1;
    s0(p)=(s0(ls(p))+(s0(rs(p))*fib[mid-l-1]%mod+s1(rs(p))*fib[mid-l]%mod)%mod)%mod;
    s1(p)=(s1(ls(p))+(s0(rs(p))*fib[mid-l]%mod+s1(rs(p))*fib[mid-l+1]%mod)%mod)%mod;
}
inline void down(int p,int l,int r)
{
    if(!tag(p))return;
    int mid=(l+r)>>1,k=tag((p));
    tag(ls(p))=(tag(ls(p))+k)%mod;tag(rs(p))=(tag(rs(p))+k)%mod;
    s0(ls(p))=(s0(ls(p))+sum[mid-l]*k%mod)%mod;
    s1(ls(p))=(s1(ls(p))+(sum[mid-l+1]-sum[0]+mod)%mod*k%mod)%mod;
    s0(rs(p))=(s0(rs(p))+sum[r-mid-1]*k%mod)%mod;
    s1(rs(p))=(s1(rs(p))+(sum[r-mid]-sum[0]+mod)%mod*k%mod)%mod;
    tag(p)=0;
}
void build(int p,int l,int r)
{
    if(l==r){s0(p)=s1(p)=a[l]%mod;return;}
    int mid=(l+r)>>1;
    build(ls(p),l,mid);build(rs(p),mid+1,r);
    up(p,l,r);
}
void change(int p,int l,int r,int pos,ll k)
{
    if(l==r){s0(p)=s1(p)=k%mod;tag(p)=0;return;}
    down(p,l,r);
    int mid=(l+r)>>1;
    if(pos<=mid)change(ls(p),l,mid,pos,k);
    else change(rs(p),mid+1,r,pos,k);
    up(p,l,r);
}
void add(int p,int l,int r,int ql,int qr,ll k)
{
    if(l>=ql&&r<=qr)
    {
        tag(p)=(tag(p)+k)%mod;
        s0(p)=(s0(p)+sum[r-l]*k%mod)%mod;
        s1(p)=(s1(p)+(sum[r-l+1]-sum[0]+mod)%mod*k%mod)%mod;
        return;
    }
    down(p,l,r);
    int mid=(l+r)>>1;
    if(ql<=mid)add(ls(p),l,mid,ql,qr,k);
    if(qr>mid)add(rs(p),mid+1,r,ql,qr,k);
    up(p,l,r);
}
ll query(int p,int l,int r,int ql,int qr)
{
    if(l>=ql&&r<=qr)
    {
        if(l==ql)return s0(p);
        else if(l==ql+1)return s1(p);
        else return (s0(p)*fib[l-ql-2]%mod+s1(p)*fib[l-ql-1]%mod)%mod;
    }
    down(p,l,r);
    int mid=(l+r)>>1;ll res=0;
    if(ql<=mid)res=(res+query(ls(p),l,mid,ql,qr))%mod;
    if(qr>mid)res=(res+query(rs(p),mid+1,r,ql,qr))%mod;
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    fib[0]=fib[1]=1;
    for(int i=2;i<=n;i++)fib[i]=(fib[i-2]+fib[i-1])%mod;
    sum[0]=1;
    for(int i=1;i<=n;i++)sum[i]=(sum[i-1]+fib[i])%mod;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int op,l,r;ll k;scanf("%d%d%d",&op,&l,&r);
        if(op==1)change(1,1,n,l,r);
        if(op==2)printf("%lld\n",query(1,1,n,l,r));
        if(op==3)scanf("%lld",&k),add(1,1,n,l,r,k);
    }
    return 0;
}