题目要求维护一个数据结构，支持区间依次加斐波那契数列，区间求和。
一开始我想的是利用斐波那契数列前缀和公式，然后下传，类似于维护一个等差数列，但是很快我就发现这个思路有问题。
但是这个思路其实有用，我们考察一下斐波那契数列的通项公式：
(f_n = frac{1}{sqrt{5}} [(frac{1 + sqrt{5}}{2})^n - (frac{1 - sqrt{5}}{2})^n])
其实斐波那契数列可以看成两个等比数列之差。本题要求取模，所以我们不妨求一下(sqrt{5})在模(10^9+9)意义下的模数，通过抄题解计算可以得到其模数为383008016，然后就可以愉快的维护两个等比数列了。
维护方法比较简单，显然公比一定，只需要下传首项即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<iostream>
#include<queue>
#include<cctype>
using namespace std;
#define A(x) cout << #x << " " << x << endl;
#define AA(x,y) cout << #x << " " << x << #y << " " << y << endl;
#define B cout << "Break" << endl;
#define ll long long
#define inf 1000000000
ll read()
{
ll c = getchar();
int x = 0,f = 1;
while(!isdigit(c))
{
if(c == '-') f = -1;
c = getchar();
}
while(isdigit(c))
{
x = x * 10 + c - '0';
c = getchar();
}
return f * x;
}
#define N 300010
#define mod 1000000009
ll base1,base2,inv,n,m;
int seq[N];
ll quick_pow(ll a,ll b)
{
ll ret = 1;
while(b)
{
if(b & 1) ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret % mod;
}
struct Segment_Tree
{
#define mid (l + r >> 1)
#define ls x << 1,l,mid
#define rs x << 1 | 1,mid + 1,r
ll p[N],tree[N << 2],lazy[N << 2],q,Inv;
void init()
{
p[0] = 1;
for(ll i = 1;i <= n;++i) p[i] = p[i - 1] * q % mod;
Inv = quick_pow(q - 1,mod - 2);
build(1,1,n);
return;
}
void push_up(ll x)
{
tree[x] = (tree[x << 1] + tree[x << 1 | 1]) % mod;
return;
}
void build(ll x,ll l,ll r)
{
if(l == r) return;
build(ls);
build(rs);
push_up(x);
return;
}
void add(ll x,ll l,ll r,ll a)
{
lazy[x] += a;
tree[x] += (a * p[r - l + 1] % mod - a + mod) % mod * Inv % mod;
return;
}
void push_down(ll x,ll l,ll r)
{
if(!lazy[x]) return;
add(ls,lazy[x]);
add(rs,lazy[x] * p[r - l + 1] % mod);
lazy[x] = 0;
}
void modify(ll x,ll l,ll r,ll L,ll R,ll a)
{
if(l == L && r == R)
{
add(x,l,r,a);
return;
}
push_down(x,l,r);
if(r <= mid) modify(ls,L,R,a);
else if(l > mid) modify(rs,L,R,a);
else
{
modify(ls,L,mid,a);
modify(rs,mid + 1,R,a * p[mid - L + 1] % mod);
}
push_up(x);
return;
}
ll query(ll x,ll l,ll r,ll L,ll R)
{
if(l == L && r == R) return tree[x];
push_down(x,l,r);
if(r <= mid) return query(ls,L,R);
else if(l > mid) return query(rs,L,R);
else return (query(ls,L,mid) + query(rs,mid + 1,R)) % mod;
}
}t1,t2;
int main()
{
t1.q = (383008016 + 1) * quick_pow(2ll,mod - 2) % mod;
t2.q = (1 - 383008016 + mod) * quick_pow(2ll,mod - 2) % mod;
inv = quick_pow(383008016,mod - 2);
n = read(),m = read();
for(ll i = 1;i <= n;++i) seq[i] = (seq[i - 1] + read()) % mod;
t1.init(),t2.init();
while(m--)
{
ll op = read(),l = read(),r = read();
if(op == 1)
{
t1.modify(1,1,n,l,r,t1.q);
t2.modify(1,1,n,l,r,t2.q);
}
else
{
ll a = t1.query(1,1,n,l,r);
ll b = t2.query(1,1,n,l,r);
ll ans = (a - b + mod) % mod * inv % mod;
printf("%lld
",((seq[r] - seq[l - 1] + mod) % mod + ans) % mod);
}
}
}