求助各位大佬 考试时写的，思路大致就是记录斐波那契数列的起始点然后通过区间相减（预处理）得到结果

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+9;
const int maxn = 3e5+10;
struct tree
{
    int l,r;
    long long tag,num;
}t[4*maxn];
long long line[maxn],fibo[maxn],fibop[maxn];
inline int len(int n)
{
    return t[n].r - t[n].l + 1;
}
void pushup(int n)
{
    t[n].num = t[n*2].num + t[n*2+1].num;
    t[n].num %= mod;
    return ;
}
void pushdown(int n)
{
    if(t[n].tag && t[n].l != t[n].r)
    {
        t[n*2].num += fibop[t[2*n].r - t[n].tag + 1] - fibop[t[2*n].l - t[n].tag];
        t[n*2+1].num += fibop[t[2*n+1].r - t[n].tag + 1] - fibop[t[2*n+1].l - t[n].tag];
        t[n*2].num %= mod;
        t[n*2+1].num%= mod;
        if(t[n*2].tag) pushdown(n*2);
        if(t[n*2+1].tag) pushdown(n*2+1);
        t[n*2].tag = t[n].tag;
        t[n*2+1].tag = t[n].tag;
        t[n].tag = 0;
    }
    return ;
}
void build(int n,int l,int r)
{
    t[n].l = l;
    t[n].r = r;
    if(l == r)
    {
        t[n].num = line[l];
        return ;
    }
    int mid = (l + r) /2;
    build(n*2,l,mid);
    build(n*2+1,mid+1,r);
    pushup(n);
    return ;
}
void modify(int n,int l,int r,int ol)//ol为其原始起点
{
    pushdown(n);
    if(t[n].l == l && t[n].r == r)
    {
        t[n].tag = ol;
        t[n].num += fibop[r - ol + 1] - fibop[l - ol];
        return ;
    }
    int mid = (t[n].l + t[n].r)/2;
    if(r <= mid)
    {
        modify(n*2,l,r,ol);
        pushup(n);
        return ;
    }
    if(mid < l)
    {
        modify(n*2+1,l,r,ol);
        pushup(n);
        return ;
    }
    modify(n*2,l,mid,ol);
    modify(n*2+1,mid+1,r,ol);
    pushup(n);
    return ;
}
long long query(int n,int l,int r)
{
    if(t[n].l == l && t[n].r == r)
    {
        return t[n].num;
    }
    pushdown(n);
    int mid = (t[n].l + t[n].r)/2;
    if(r <= mid)
    {
        return query(n*2,l,r);
    }
    if(mid < l)
    {
        return query(n*2+1,l,r);
    }
    return (query(n*2,l,mid) + query(n*2+1,mid+1,r))%mod;
}
int main()
{
    int n,m;
    cin>>n>>m;
    fibo[1] = 1; fibo[2] = 1;
    fibop[0] = 0; fibop[1] = 1; fibop[2] = 2;
    for(int i=3;i<=n;i++)
    {
        fibo[i] = fibo[i-1] + fibo[i-2];
        fibo[i] %= mod;
        fibop[i] = fibop[i-1] + fibo[i];
        fibop[i] %= mod;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>line[i];
        line[i] %= mod;
    }
    build(1,1,n);
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        if(a == 1)
        {
            modify(1,b,c,b);
        }
        else
        {
            int ttmp = query(1,b,c);
            if(ttmp >= 0) cout<<ttmp%mod<<endl;
            else cout<<mod - ttmp%mod<<endl;
        }
    }
    return 0;
}