萌新求助

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define int long long
#define l(x) tr[x].l
#define r(x) tr[x].r
#define sum(x) tr[x].sum
#define ff(x) tr[x].ff
#define gg(x) tr[x].gg
#define len(x) tr[x].len
const int Mod = 1e9+9;
const int N = 300005;
int n,q,a[N],f[N];
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int Add(int x,int y) {return (x+y+Mod) % Mod;}
int mul(int x,int y) {return x * y % Mod;}

struct Seg{
	int l,r;
	int sum,ff,gg,len;
	
}tr[N<<2];
 
void spread(int x) {
	if((!ff(x)) && (!gg(x))) return; 
	ff(x<<1) = Add(ff(x<<1),ff(x)) % Mod;
	gg(x<<1) = Add(gg(x<<1),gg(x)) % Mod;
	sum(x<<1) = Add(sum(x<<1),Add(mul(f[len(x<<1)],ff(x)),mul(f[len(x<<1)+1]-1,gg(x))));
	ff(x<<1|1) = Add(ff(x<<1|1),Add(mul(f[len(x<<1)-1],gg(x)),mul(f[len(x<<1)-2],ff(x))));
	gg(x<<1|1) = Add(gg(x<<1|1),Add(mul(f[len(x<<1)],gg(x)),mul(f[len(x<<1)-1],ff(x))));
	sum(x<<1|1) = Add(sum(x<<1|1),Add(Add(Add(mul(gg(x),f[len(x)+1]-1),mul(ff(x),f[len(x)])),mul(-gg(x),f[len(x<<1)+1]-1)),mul(-ff(x),f[len(x<<1)]))) 
	ff(x) = gg(x) = 0;
	return;
} 

void pushup(int x) {
	sum(x) = (sum(x<<1) + sum(x<<1|1)) % Mod;
	return;
}

void build(int x,int l,int r) {
	l(x) = l,r(x) = r;len(x) = r-l+1;
	if(l == r) {
		sum(x) = ff(x) = gg(x) = 0;
		return; 
	}
	int mid = (l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x);
}

inline int query(int x,int l,int r) {
	if(l <= l(x) && r(x) <= r) return sum(x);
	int mid = (l(x) + r(x))>>1;
	spread(x);
	int val = 0;
	if(l <= mid) val = (val + query(x<<1,l,r)) % Mod;
	if(mid < r) val = (val + query(x<<1|1,l,r)) % Mod;
//	pushup(x);
	return val; 
}

void change(int x,int l,int r) {
	if(l <= l(x) && r <= r(x)) {
		ff(x) = (ff(x) + f[l(x)-l+1]) % Mod;
		gg(x) = (gg(x) + f[l(x)-l+2]) % Mod;
		sum(x) = ((sum(x) + f[len(x)] * f[l(x)-l+1] % Mod) % Mod + (f[len(x)+1]-1) * f[l(x)-l+2] % Mod) % Mod;
		return;
	}
	spread(x);
	int mid = (l(x) + r(x))>>1;
	if(l <= mid) change(x<<1,l,r);
	if(mid < r) change(x<<1|1,l,r);
	pushup(x);
} 


signed main () {
	n = read();q = read();
	for(int i = 1;i <= n;i++) a[i] = read();
	f[1] = f[2] = 1;
	for(int i = 3;i <= n+2;i++) f[i] = (f[i-1] + f[i-2]) % Mod;
	build(1,1,n);
	while(q--) {
		int opt;
		opt = read();
		if(opt == 1) {
			int l,r;
			l = read();r = read();
			change(1,l,r);
		}
		if(opt == 2) {
			int x,y;
			x = read();y = read();
			printf("%lld\n",query(1,x,y));
		}
	}
	return 0;
}

#define ff(x) tr[x].ff