题意

给一段序列，长度小于3e5，给出多次(3e5)区间操作，每次在 [ l , r ] 依次从fib(1)加上斐波那契数列。
斐波那契数列即f[n] = f[n – 1] + f[n – 2]; 前5项为1，1，2，3，5；
比如[1，1，4，5，6]现在要求在[2，4]上增加，[1，1+1，4+1，5+2，6+3]

另外一个操作就是求区间和。
传送门

斐波那契数列的性质

1.fib[n] = fib[n+2]-fib[2]

这个性质由斐波那契数列的差分推出。
1,1,2,3,5,8,13,21…
..,0,1,1,2,3,5..,8..,13…
可以看出，斐波那契数列求差分以后还是一个斐波那契数列，而且每一位向后移动了两个位置。根据差分的性质：差分序列的N位前缀和即原序列的第N个数字。可以通过逆差分得到序列和。
所以如果想求斐波那契数列的和，也可求它的差分的和，反正都是一样的，但由于差分出来的斐波那契数列是往后移动了两位的。所以需要原序列也往后移动两位，即fib(n)=fib(n+2)-fib(2)

2.斐波那契数列的叠加还是斐波那契数列

这个性质很好理解。因为每个斐波纳妾数列都满足同样的齐次线性递推关系。多个斐波那契数列的每一项还是满足。

也可以通过多次差分的规律，看出逆差分即本性质。

3.类斐波那契数列的公式

形如
F(1)=a,F(2)=b,F(n)=F(n-1)+F(n-2)
的数列即类斐波那契数列。
这类数列可以转化为斐波那契数列相关的数列。即
F(n)=a\times fib(n-1)+b\times fib(n-2)
可以通过矩阵证明
\left[\begin{matrix} 1 & 1\end{matrix} \right] \times \left[\begin{matrix} 0 & 1\\ 1 & 1 \end{matrix} \right]^{n} = \left[\begin{matrix} fib_{n-1} & fib_{n}\end{matrix} \right]
初始值的不同相当于左边的矩阵每列有个系数

线段树维护序列

魔改lazy

由于斐波那契数列的性质3和2，可以对lazy标记的传递方式进行魔改。每个区间记录序列前两个，这样既可以推算出区间和，也可以推算出某项的值。

向下传递的时候不是简单的直接传值。需要把对应的F1和F2算出来。因为对于每个小区间而言，它的F1和F2不再是大区间的F1和F2，需要用性质3计算。

比如
【1，8】
【1，4】 【5，8】
【1，2】【3，4】【5，6】【7，8】
【1】【2】【3】【4】【5】【6】【7】【8】
现在更新【2，6】
那么完毕后lazy应该是这样的
【0，0】
【0，0】 【0，0】
【0，0】【f2，f3】【f4，f5】【0，0】
【0】【f1】【0】【0】【0】【0】【0】【0】
也就是说lazy要根据区间的不同进行更改。同时push也要进行类似的换算。
求和也用公式计算。所有操作只需要预处理斐波那契数列就好。

小坑

性质1计算的时候有减法操作，注意取模后的减法可能会变成负数。需要（res+p）%p

答案进行取模..不然不知道哪儿又多出来个大于1e9+7的数

push的时候用父亲的lazy去更新儿子的dat，不是儿子的lazy去更新儿子的dat

#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
const int Mz = 1e9 + 9;
typedef long long ll;
const long long  maxn = 3e5 + 233;
ll n,m,fib[maxn],a[maxn];
struct SegNode{
    ll l,r,dat,mark1,mark2;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define dat(x) t[x].dat
    #define mk1(x) t[x].mark1
    #define mk2(x) t[x].mark2
}t[maxn * 4];
ll F(ll a, ll b, int x)
{
    //F(n) = a*Fib(n-2)+b*Fib(n-1)
    return ((a % Mz)*(fib[x - 2] % Mz) + (b % Mz) * (fib[x - 1] % Mz)) % Mz;
}
ll calcsum(ll a, ll b, int x)
{
    //s = F(n+2)-F(2)
    return (((F(a, b, x + 2) % Mz) - (b % Mz)) % Mz + Mz) % Mz;
}
void build(int p, int l, int r)
{
    l(p) = l; r(p) = r;
    if(l == r)
    {
        dat(p) = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls(p), l, mid); build(rs(p), mid + 1, r);
    dat(p) = dat(ls(p)) + dat(rs(p));
}
void spr(int p)
{
    while(mk1(p) || mk2(p))
    {
        int mid = (l(p) + r(p)) >> 1;

        mk1(ls(p)) = ((mk1(ls(p)) % Mz) + (mk1(p) % Mz)) % Mz;
        mk2(ls(p)) = ((mk2(ls(p)) % Mz) + (mk2(p) % Mz)) % Mz;
        if(mid - l(p) + 1 == 1) mk2(ls(p)) = 0;
        dat(ls(p)) = ((dat(ls(p)) % Mz) + calcsum(mk1(p), mk2(p), mid - l(p) + 1)) % Mz;

        mk1(rs(p)) = ((mk1(rs(p)) % Mz) + (F(mk1(p),mk2(p),mid + 1 - l(p) + 1) % Mz)) % Mz;
        mk2(rs(p)) = ((mk2(rs(p)) % Mz) + (F(mk1(p),mk2(p),mid + 2 - l(p) + 1) % Mz)) % Mz;
        ll t1 = F(mk1(p),mk2(p),mid + 1 - l(p) + 1) % Mz, t2 = F(mk1(p),mk2(p),mid + 2 - l(p) + 1) % Mz;
        if(r(p) - mid == 1) t2 = 0;
        dat(rs(p)) = ((dat(rs(p)) % Mz) + calcsum(t1, t2, r(p) - mid)) % Mz; 

        mk1(p) = 0; mk2(p) = 0;
    }
}
void updata(int p, int l, int r)
{
    //cout<< p <<":"<<l(p)<<' '<<r(p)<<endl ;
    if(l <= l(p) && r >= r(p))
    {
        mk1(p) = ((mk1(p) % Mz) + (fib[l(p) - l + 1] % Mz)) % Mz;
        mk2(p) = ((mk2(p) % Mz) + (fib[l(p) - l + 2] % Mz)) % Mz;
        ll t1 = fib[l(p) - l + 1] % Mz, t2 = fib[l(p) - l + 2] % Mz;
        if(r(p) - l(p) + 1 == 1) t2 = 0;
        dat(p) = ((dat(p) % Mz) + (calcsum(t1,t2,r(p) - l(p) + 1) % Mz)) % Mz; 
      //  cout<<dat(p)<<"!"<<endl;
        return ;
    }
    spr(p);
    int mid = (l(p) + r(p)) >> 1;
    if(l <= mid) updata(ls(p), l, r);
    if(r > mid) updata(rs(p), l, r);
    dat(p) = (dat(ls(p)) + dat(rs(p))) % Mz;
}
ll ask(int p, int l, int r)
{
    if(l <= l(p) && r >= r(p)) return dat(p) % Mz;
    spr(p);
    int mid = (l(p) + r(p)) >> 1;
    ll v = 0;
    if(l <= mid) v = ((v % Mz) + (ask(ls(p),l,r) % Mz)) % Mz;
    if(r > mid) v = ((v % Mz) + (ask(rs(p),l,r) % Mz)) % Mz;
    return v % Mz; 
}
int main()
{
    scanf("%d%d",&n,&m);
    fib[1] = 1LL; fib[2] = 1LL;
    for(int i = 3; i <= n + 10; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % Mz;
    for(int i = 1; i <= n; i++) cin >> a[i];    
    build(1,1,n);
    for(int i = 1; i <= m; i++)
    {
        int c,a,b;
        scanf("%d%d%d",&c,&a,&b);
        if(c == 1) updata(1,a,b);
        else cout << ask(1,a,b) << endl;
    }
}

总的来说是个很好的题。维护斐波那契数列数列的方法还可以扩展到维护等差数列，等比数列，任意规律数列。