题意：给你长度为n的数列，有两个操作
①将区间[L,R]加上从1,1为前两项的斐波那契数列。
②询问区间[L,R]的和。
题解：首先肯定是用线段树维护区间和，但是直接加上斐波那契数列又很难维护，所以我们可以利用斐波那契数列的性质：
①我们可以通过标记记录该区间所加的斐波那契的前两项，因为斐波那契相叠加还是斐波那契数列。
②通过前两项，我们可以O（1）的计算出区间和，如下：
但是如何知道第n+2项呢？当我们知道前两项a1和a2的时候，我们可以通过：a*fib[n-2]+b*fib[n-1]（fib[i]是以1,1为前两项的斐波那契数列）得到第n+2项，我们预处理所有需要的斐波那契数，也就可以O（1）计算出区间加上的斐波那契数列的和。
AC代码：
#include<stdio.h> #define N 300005 #define mod 1000000009 typedef long long ll; ll fib[N],a[N]; ll tree[N*4],fir[N*4],sec[N*4]; void build(ll L,ll R,ll root) { if(L==R) { tree[root]=a[L]; return ; } ll mid=L+R>>1; build(L,mid,root<<1); build(mid+1,R,root<<1|1); tree[root]=(tree[root<<1]+tree[root<<1|1])%mod; } ll get(ll a1,ll a2,ll n) { if(n==1)return a1%mod; if(n==2)return a2%mod; return ((a1*fib[n-2])%mod+(a2*fib[n-1])%mod)%mod; } ll getsum(ll a,ll b,ll n) { if(n==1)return a%mod; if(n==2)return (a+b)%mod; return (get(a,b,n+2)-get(a,b,2)+mod)%mod; } void pushdown(ll root,ll L,ll R) { ll mid=L+R>>1; tree[root<<1]=(tree[root<<1]+getsum(fir[root],sec[root],mid-L+1))%mod; tree[root<<1|1]=(tree[root<<1|1]+getsum(get(fir[root],sec[root],mid-L+2),get(fir[root],sec[root],mid-L+3),R-mid))%mod; fir[root<<1]=(fir[root<<1]+fir[root])%mod; sec[root<<1]=(sec[root<<1]+sec[root])%mod; fir[root<<1|1]=(fir[root<<1|1]+get(fir[root],sec[root],mid-L+2))%mod; sec[root<<1|1]=(sec[root<<1|1]+get(fir[root],sec[root],mid-L+3))%mod; fir[root]=sec[root]=0; } void update(ll l,ll r,ll L,ll R,ll root,ll a,ll b) { if(l<=L&&R<=r) { tree[root]=(tree[root]+getsum(a,b,R-L+1))%mod; fir[root]=(fir[root]+a)%mod; sec[root]=(sec[root]+b)%mod; return ; } ll mid=L+R>>1; if(fir[root]||sec[root])pushdown(root,L,R); if(r<=mid)update(l,r,L,mid,root<<1,a,b); else if(l>mid)update(l,r,mid+1,R,root<<1|1,a,b); else { update(l,mid,L,mid,root<<1,a,b); update(mid+1,r,mid+1,R,root<<1|1,get(a,b,mid-l+2),get(a,b,mid-l+3)); } tree[root]=(tree[root<<1]+tree[root<<1|1])%mod; } ll query(ll l,ll r,ll L,ll R,ll root) { if(l<=L&&R<=r)return tree[root]; ll mid=L+R>>1; if(fir[root]||sec[root])pushdown(root,L,R); if(r<=mid)return query(l,r,L,mid,root<<1); else if(l>mid)return query(l,r,mid+1,R,root<<1|1); else return (query(l,mid,L,mid,root<<1)+query(mid+1,r,mid+1,R,root<<1|1))%mod; } int main() { fib[1]=fib[2]=1; for(ll i=3;i<N;i++) fib[i]=(fib[i-1]+fib[i-2])%mod; ll n,m; scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,n,1); while(m--) { ll op,l,r; scanf("%lld%lld%lld",&op,&l,&r); if(op==1)update(l,r,1,n,1,1,1); else printf("%lld\n",query(l,r,1,n,1)); } }