RT，窝用的是线段树套矩乘的方法，对于每个区间[L,R]，用tag记录它的第一项累加的矩阵，设为A，用B表示加速斐波那契数列时用的矩阵，I表示单位矩阵，然后区间和就是$A+B\times A+ B^{2}\times A+…+B^{R-L}\times A =A\times \frac{B^{R-L+1}-I}{A-I}$，把这个式子套到线段树上跑一遍。

理论上讲push_down和push_up都是常数阶的，总时间复杂度为$O(nlogn)$，但不知道为啥跑的特别慢，n=3e5,m=1e4的数据就已经快1s了，极限数据直接T飞。我对着代码调了快一天了也没调出来，请求好心的巨佬救济一下！谢谢！！

#include<iostream>
#include<cstdio>
#include<cstring>
					#include<windows.h>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;
inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;} 
//tag=i表示[L,R]这段区间的a[L]加上了fib[i]，记矩阵A为[fib[i]//fib[i+1] 
//那么整段区间的变化就是A*(B^(R-L+1)-I)*(B-I)^(-1)
//在下传tag时套一个矩阵快速幂再微调一下就OK
const int maxn=3e5+5,yrz=1e9+9;
struct M{
	int n,m;
	int a[5][5];
	M(){memset(a,0,sizeof a);} 
	void fz(){memset(a,0,sizeof a);} 
	void outit(){
		printf("%d,%d\n",n,m);
		fo(i,1,n){
			fo(j,1,m) printf("%d ",a[i][j]);
			puts("");
		}	
	}
	bool check(){//检查矩阵是否为空 
		return (a[1][2]||a[1][1]||a[2][1]||a[2][2]); 
	} 
}A,I,B,ny,C,D,E,tag[maxn<<2],power[maxn],ans;
//B表示斐波那契数列用矩阵快速幂加速时的矩阵，power[i]表示B^i，I是单位矩阵，ny是矩阵(B-I)的逆，CDE都是中间变量 

M operator*(const M &x,const M &y){//重载矩阵乘法 
	ans.n=x.n;
	ans.m=y.m;
	ans.fz();
	fo(i,1,ans.n)
		fo(j,1,ans.m)
			fo(k,1,x.m) ans.a[i][j]=(ans.a[i][j]+1ll*x.a[i][k]*y.a[k][j]%yrz)%yrz;
	return ans;
}

M operator+(const M &x,const M &y){//重载矩阵加法 
	ans.n=x.n;
	ans.m=x.m;
	ans.fz();
	fo(i,1,x.n)
		fo(j,1,y.m) ans.a[i][j]=(x.a[i][j]+y.a[i][j])%yrz;
	return ans;
}

M operator-(const M &x,const M &y){//重载矩阵减法 
	ans.n=x.n;
	ans.m=x.m;
	ans.fz();
	fo(i,1,x.n)
		fo(j,1,y.m) ans.a[i][j]=(x.a[i][j]+yrz-y.a[i][j])%yrz;
	return ans;
}
struct Node{
	int L,R,len;
	int val;
}tree[maxn<<2];//线段树 
int a[maxn];
int n,m,fib[maxn<<2];

void push_up(int now){
	tree[now].val=(tree[ls(now)].val+tree[rs(now)].val)%yrz;
}

void push_down(int now){//push_down函数，我觉得这里是最有可能出bug的地方 
	int lt=ls(now),rt=rs(now);	
	//printf("push_down(%d)\n",now);
	//printf("lt=%d rt=%d\n",lt,rt);
	//printf("lt.val=%lld,rt.val=%lld\n",tree[lt].val,tree[rt].val);
	tag[lt]=tag[lt]+tag[now];
	D=power[tree[lt].len]-I;
	D=D*ny;
	D=D*tag[now];
	tree[lt].val+=D.a[1][1];
	tree[lt].val%=yrz;
	D=power[tree[rt].L-tree[lt].L]*tag[now];
	tag[rt]=tag[rt]+D;
	D=ny*D;
	E=power[tree[rt].len]-I;
	D=E*D;
	tree[rt].val+=D.a[1][1];
	tree[rt].val%=yrz;
	//puts("D:");
	//D.outit();
	//printf("lt.val=%lld,rt.val=%lld\n",tree[lt].val,tree[rt].val);
	//tag[now].fz();
	tag[now].a[1][1]=tag[now].a[2][1]=0;
}

void build(int L,int R,int now){//build函数 
	tree[now].L=L,tree[now].R=R;
	tree[now].len=R-L+1;
	tag[now].n=2,tag[now].m=1;
	if(L==R){
		tree[now].val=a[L];
		return; 
	}
	int mid=(L+R)>>1;
	build(L,mid,ls(now));
	build(mid+1,R,rs(now));
	push_up(now);
}

void update(int L,int R,int x,int now){
	//把区间[L,R]的第一项加上fib[x]
	if(tree[now].L>=L&&tree[now].R<=R){
		D.n=2,D.m=1;
		D.a[1][1]=fib[x];
		D.a[2][1]=fib[x+1];
		tag[now]=tag[now]+D;
		E=power[tree[now].len]-I;
		D=ny*D;
		D=E*D;
		tree[now].val+=D.a[1][1];
		tree[now].val%=yrz;
		return;
	}
	int mid=(tree[now].L+tree[now].R)>>1;
	if(tag[now].check())push_down(now);
	if(L<=mid) update(L,R,x,ls(now));
	if(R>mid) update(L,R,(L<=mid?mid+2-L:x),rs(now));
	push_up(now);
}

int ask(int L,int R,int now){
	if(L<=tree[now].L&&R>=tree[now].R){
		return tree[now].val;
	}
	int mid=(tree[now].L+tree[now].R)>>1;
	int ret=0;
	if(tag[now].check())push_down(now);
	if(L<=mid) ret+=ask(L,R,ls(now));
	if(R>mid) ret+=ask(L,R,rs(now));
	return ret%yrz;
}
 
int main(){
	DWORD start_time=GetTickCount();
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	n=read(),m=read();
	fo(i,1,n) a[i]=read();
	fib[1]=fib[2]=1;
	fo(i,3,n+1) fib[i]=(fib[i-1]+fib[i-2])%yrz;
	B.n=B.m=2;
	B.a[2][1]=B.a[2][2]=B.a[1][2]=1;
	I.n=I.m=2;
	I.a[1][1]=I.a[2][2]=1;
	power[0]=I;
	fo(i,1,n+1) power[i]=power[i-1]*B; 
	ny=B;
	build(1,n,1);
	fo(i,1,m){
		int opt=read(),x=read(),y=read();
		if(opt==1) update(x,y,1,1);
		else printf("%d\n",ask(x,y,1));
	}
	DWORD end_time=GetTickCount();
	int t=end_time-start_time;
	printf("运行时间为%d ms\n",t);
	return 0;
}
/*
4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3
-------------------------------------------------
17
12
*/

衷心感谢您的到来！