首先斐波那契数列有一个性质：
当(f[1] = x,f[2] = y)时，那么(f[n] = x*f[n-1]+y*f[n-2])
还有一个性质：
任意两段不同的斐波那契数列逐项相加，所得数列仍然是个斐波那契数列。
所以对于这个题，维护一棵线段树，需要维护区间内斐波那契数列的第一项，第二项，区间和。
下传标记的时候，我们可以在做区间加前两项，在右区间可以求出总和再加上总和就行了。
时间复杂度为(O(nlogn))
然而还有别的做法：
直接写出斐波那契数列的通项：
[f[n] = frac{1}{sqrt{5}}[(frac{1+sqrt{5}}{2})^n-(frac{1-sqrt{5}}{2})^n]
]
然后转化为线段树区间加等比数列，运用等比数列求和公式就可以。
同时值得注意的是，(sqrt{5})在(mod10^9+9)意义下有二次剩余为383008016，so不用扩域。
代码为第一种做法。
#define B cout << "BreakPoint" << endl;
#define O(x) cout << #x << " " << x << endl;
#define O_(x) cout << #x << " " << x << " ";
#define Msz(x) cout << "Sizeof " << #x << " " << sizeof(x)/1024/1024 << " MB" << endl;
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#define LL long long
const int mod = 1e9 + 9;
const int N = 3e5 + 5;
using namespace std;
inline int read() {
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
LL a[N],f[N],sum[N];
LL solve1(LL x,LL y,LL l){
if(l == 1) return x;
if(l == 2) return y;
return (x * f[l - 2] + y * f[l - 1]) % mod;
}
LL solve2(LL x,LL y,LL l){
if(l == 1) return x;
if(l == 2) return (x + y) % mod;
return (solve1(x,y,l + 2) - y + mod) % mod;
}
namespace Segment{
#define ls k<<1
#define rs k<<1|1
struct node {
LL c1,c2,sum;
} t[N*20];
void pushup(int k){
t[k].sum = (t[ls].sum + t[rs].sum)%mod;
}
void pushdown(int k,int l,int r){
if(!t[k].c1) return;
int mid = l+r>>1;
t[ls].c1 = (t[ls].c1 + t[k].c1) % mod;
t[ls].c2 = (t[ls].c2 + t[k].c2) % mod;
t[ls].sum = (t[ls].sum + solve2(t[k].c1,t[k].c2,mid - l + 1)) % mod;
LL x = solve1(t[k].c1,t[k].c2,mid - l + 2),y = solve1(t[k].c1,t[k].c2,mid - l + 3);
t[rs].c1 = (t[rs].c1 + x) % mod;
t[rs].c2 = (t[rs].c2 + y) % mod;
t[rs].sum = (t[rs].sum + solve2(x,y,r - mid)) % mod;
t[k].c1 = 0,t[k].c2 = 0;
}
void update(int k,int l,int r,int L,int R){
if(L <= l && r <= R){
t[k].c1 = (t[k].c1 + f[l - L + 1]) % mod;
t[k].c2 = (t[k].c2 + f[l - L + 2]) % mod;
t[k].sum = (t[k].sum + solve2(f[l - L + 1],f[l - L + 2],r - l + 1)) % mod;
return ;
}
pushdown(k,l,r);
int mid = l+r>>1;
if(L <= mid) update(ls,l,mid,L,R);
if(R > mid) update(rs,mid + 1,r,L,R);
pushup(k);
}
LL query(int k,int l,int r,int L,int R){
LL res = 0;
if(L <= l && r <= R){
res = t[k].sum;
return (res+mod)%mod;
}
pushdown(k,l,r);
int mid = l+r>>1;
if(L <= mid) res += query(ls,l,mid,L,R);
if(R > mid) res += query(rs,mid + 1,r,L,R);
return (res+mod) % mod;
}
}
int n,m;
void init(){
n = read(),m = read();
for(int i = 1;i <= n;i++){
LL x = read();
a[i] = (a[i - 1] + x) % mod;
}
f[1] = 1,f[2] = 1;
for(int i = 3;i <= n + 2;i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
return ;
}
using namespace Segment;
void solve(){
for(int i = 1; i <= m; i++) {
int opt = read(),x = read(),y = read();
if (opt == 1) update(1, 1, n, x, y);
else printf("%lld
", (mod + query(1,1,n,x,y) + a[y] - a[x - 1]) % mod);
}
return ;
}
int main(){
init();
solve();
return 0;
}