coderfoces446c (斐波那契数列)

题目描述：

区间增值，但是每一项增加的值为Fi - l + 1，F[i]为斐波那契数列，求区间和？

考虑线段树，刚开始想用斐波那契数列的前n项和，可是推不出来，考虑到每个区间的增值序列都是一段斐波那契数列，他们的和是否有什么特性呢？

发现如果前两项为a和b的话，那么，a,b,a+b,a+2b,2a+3b,3a+5b;

a和b前的系数为斐波那契数列（后一项为前两项之和,

设F[k]表示以a，b开头的第k项的值，s[k]代表以a和b开头的前k项和

F[k]=a*f[k-2]+b*f[k-1];

F[1]=1*a+0*b;

F[2]=0*a+1*b;

F[3]=f[1]*a+f[2]*b;

F[4]=f[2]*a+f[3]*b;

F[k]=f[k-2]*a+f[k-1]*b;

pp[k]=1+0+f[1]+f[2]+f[3]+...f[k-2];

qq[k]=0+f[1]+f[2]+f[3]+...+f[k-1];

求和:

S[k]=a*pp[k]+b*qq[k];

这样只需要确定每个区间的a和b，长度可以计算出来，那么第k项可以求出来,前k项和也可以求出来；

维护每个区间的a和b的值，a和b作为标记。

写这道题是发现对标记的处理有了更深的理解：

标记会有那些操作呢？

1 位置，最下层的标记以下的节点没有被更新，最上层的标记以上全都被更新过，

也就是对于每一个标记来说，它没有更新它所在节点的子节点，更新了它所有的父节点。

2 标记在同一个区间可以累加（累加型标记）

3 标记传递时，子节点的值是由父节点的标记累计改变的，子节点的标记只是用来往下传的，所以子节点的标记值没有用。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstring>

#include <algorithm>

#define LL long long

#define MOD 1000000009

using namespace std;

//线段树

//区间每点增值，求区间和

const int maxN = ;

struct node

{

    int  lt, rt;

    int  addA,addB;

    LL   val;

}tree[*maxN];

LL  a[maxN];

int n,m;

LL f[maxN];

LL pp[maxN];

LL qq[maxN];

void init()

{

    memset(f,,sizeof(f));

    f[]=; f[]=;

    pp[]=; pp[]=;

    qq[]=; qq[]=;

    for(int i=;i<maxN;i++)

    {

        f[i]=(f[i-]+f[i-])%MOD;

        pp[i]=(pp[i-]+f[i-])%MOD;

        qq[i]=(qq[i-]+f[i-])%MOD;

    }

}

//向下更新

void pushDown(int id)

{

    if (tree[id].addA !=  || tree[id].addB!=)

    {

        LL a,b;

        int LeftLen= tree[id << ].rt - tree[id << ].lt +;

        a=tree[id].addA;  b=tree[id].addB;

        tree[id<<].addA +=  a;

        tree[id<<].addB +=  b;

        tree[id<<].addA %=MOD;

        tree[id<<].addB %=MOD;

        tree[id<<].val  += ( ( (pp[LeftLen]* a)%MOD + (qq[LeftLen] *b)%MOD )%MOD ) ;

        tree[id<<].val  %= MOD;

        int RightLen= tree[id <<  |].rt - tree[id << |].lt +;

        a=( ( (tree[id].addA * f[LeftLen+ -] )%MOD + (tree[id].addB * f[LeftLen + -])%MOD ) %MOD );

        b=( ( (tree[id].addA * f[LeftLen+- +])%MOD + (tree[id].addB * f[LeftLen + - +])%MOD )%MOD);

        //a和b分别为第k项和第k+1项

        tree[id<< |].addA +=a;

        tree[id<< |].addB +=b;

        tree[id << |].addA%=MOD;

        tree[id << |].addB%=MOD;

        tree[id<< |].val  +=( ( (pp[RightLen] *a) %MOD + (qq[RightLen] *b)%MOD ) %MOD );

        tree[id << |].val%=MOD;

        tree[id].addA = ;

        tree[id].addB = ;

    }

}

//向上更新

void pushUp(int id)

{

    tree[id].val = ( (tree[id<<].val + tree[id<<|].val) %MOD);

}

//建立线段树

void build(int lt, int rt, int id)

{

    tree[id].lt = lt;

    tree[id].rt = rt;

    tree[id].val =  ;//每段的初值，根据题目要求

    tree[id].addA = ;

    tree[id].addB = ;

    if (lt == rt)

    {

        tree[id].val = a[lt];

        return;

    }

    int mid = (lt+rt)>>;

    build(lt, mid, id<<);

    build(mid+, rt, id<<|);

    pushUp(id);

}

//增加区间内每个点固定的值

void add2(int lt, int rt, int id, int Left)

{

    if (lt <= tree[id].lt && rt >= tree[id].rt)

    {

        int plsa=   tree[id].lt - Left +;

        int plsb=   tree[id].lt - Left +;

        tree[id].addA +=  f[plsa];

        tree[id].addB +=  f[plsb];

        tree[id].addA%=MOD;

        tree[id].addB%=MOD;

        LL a,b;

        a=f[plsa]; b=f[plsb];

        int Len= tree[id].rt - tree[id].lt + ;

        tree[id].val  +=( (a*pp[Len])%MOD + (b*qq[Len])%MOD )%MOD ;

        tree[id].val %=MOD;

        return;

    }

    pushDown(id);

    //区间更新中最重要的lazy操作,把下次可能要查询的节点的标记更新到，然后只要不影响查询就好。

    int mid = (tree[id].lt+tree[id].rt)>>;

    if (lt <= mid)

        add2(lt, rt, id<<, Left);

    if (rt > mid)

        add2(lt, rt, id<<|, Left);

    pushUp(id);

}

//查询某段区间内的和

LL query(int lt, int rt, int id)

{

    if (lt <= tree[id].lt && rt >= tree[id].rt)

        return tree[id].val;

    pushDown(id);

    //如果不pushdown的话，它的计算方式是记下沿途的标记，到达目的节点之后计算目的节点自上而下的标记之和；

    //然后再加上本节点之前由自下而上的标记递推的来的和也就是tree.val（tree.val的含义就是只执行节点id及其子孙节点中的add操作，节点id对应区间中所有数之和）

    //如果每次pushdown就可以把下次可能要查询的节点的标记更新到就好(tree.val的含义就是执行所有对节点id有影响的id操作，节点id对应区间中所有数之和)

    int mid = (tree[id].lt+tree[id].rt)>>;

    LL ans = ;

    if (lt <= mid)

        ans += query(lt, rt, id<<);

    if (rt > mid)

        ans += query(lt, rt, id<<|);

    ans%=MOD;

    return ans;

}

int main()

{

   //freopen("test.txt","r",stdin);

    init();

    while(~scanf("%d%d",&n,&m))

    {

       for(int i=;i<=n;i++)

          scanf("%d",&a[i]);

          build(,n,);

       for(int i=;i<=m;i++)

       {

           int c,l,r;

           scanf("%d%d%d",&c,&l,&r);

           if(c==)

           {

               add2(l,r,,l);

           }

           if(c==)

           {

               printf("%I64d\n",query(l,r,));

           }

       }

    }

    return ;

}

巴特西

coderfoces446c (斐波那契数列)

最新文章

热门文章