浅谈树状数组,浅谈树状

2019-09-25 作者:计算机教程   |   浏览(61)

1,单点修改,求区间和

浅谈树状数组,浅谈树状

最近学了树状数组,给我的感觉就是 这个数据结构好神奇啊^_^

首先她的常数比线段树小,其次她的实现复杂度也远低于线段树 (并没有黑线段树的意思=-=)

所以熟练掌握她是非常有必要的。。

关于树状数组的基础知识与原理网上一搜一大堆,我就不赘述了,就谈一些树状数组的应用好了

 

1,单点修改,求区间和

#define lowbit(x) (x&-x)  // 设 x 的末尾零的个数为 y , 则 lowbit(x) == 2^y 
void Update(int i,int v)  // 初始化与单点修改 
{
    while(i <= n)
    {
        c[i]  = v ;
        i  = lowbit(i) ;
    }
}

inline int Sum(int i)   // 区间求和 
{
    int res = 0 ;
    while(i > 0)
    {
        res  = c[i] ;
        i -= lowbit(i) ;
    }
    return res ;
}

2,区间修改,单点查询

这里要用到差分的思想

创建一个差分数组c[],令c[i] = a[i] - a[i-1] (a[i] 表示原本的第i个数) 

则a[i] = ( a[i] - a[i-1] ) ( a[i-1] - a[i-2] ) ...... ( a[2] - a[1] ) a[1] 

         = c[i] c[i-1] ...... c[2] c[1] 

所以单点查询变成了区间求和

那么区间修改怎么办呢 ?

我们看这样一个例子:

a 1 3 4 5 7 10

c 1 2 1 1 2 3

若我们令区间[2,4]加2,则

a 1 5 6 7 9 10

c 1 4 1 1 2 1 

我们可以发现只有c[2]和c[5]的数值改变了,其实原理也很好想,区间内的前后元素差是不变的,只有(区间第一个元素与前一个元素的差) 和 (区间后第一个元素与区间末尾元素的差) 改变了。所以区间修改问题变成了单点修改问题。

 

        for(int i=1;i<=n;i  )
    {
        a[i] = read() ;
        Update(i,a[i]-a[i-1]);
    } 
/*    int x=0,y=0;       // 注释掉的内容是空间上的优化(初学者建议先跳过)
    for(int i=1;i<=n;i  )
    {
        if(i%2)
        {
            x = read() ;
            Update(i,x-y);
        }
        else
        {
            y = read() ;
            Update(i,y-x) ;
        }
    }  */
    int ii ;
    int k,x,y;
    for(int i=1;i<=m;i  )
    {
        ii = read() ;
        if(ii == 1)
        {
            x = read() ; y = read() ; k = read() ;
            Update(x,k);
            Update(y 1,-k);
        }
        if(ii == 2)
        {
            x = read() ;
            printf("%dn",Sum(x));
        }
    }

(洛谷有对应的模板题 P3374 与 P3368)

 

上述就是树状数组最基础的两个应用,日后更深入的学习后再来更新。

 

——end ; 

 

http://www.bkjia.com/cjjc/1229378.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1229378.htmlTechArticle浅谈树状数组,浅谈树状 最近学了树状数组,给我的感觉就是 这个数据结构好神奇啊^_^ 首先她的常数比线段树小,其次她的实现复杂度也...

关于树状数组的基础知识与原理网上一搜一大堆,我就不赘述了,就谈一些树状数组的应用好了

——end ; 

所以熟练掌握他是非常有必要的。。

最近学了树状数组,给我的感觉就是 这个数据结构好神奇啊^_^

c 1 4 1 1 2 1 

那么区间修改怎么办呢 ?

2,区间修改,单点查询

(洛谷有对应的模板题 P3374 与 P3368)

c 1 2 1 1 2 3

a 1 5 6 7 9 10

这里要用到差分的思想

 

上述就是树状数组最基础的两个应用,日后更深入的学习后再来更新。

        for(int i=1;i<=n;i  )
    {
        a[i] = read() ;
        Update(i,a[i]-a[i-1]);
    } 
/*    int x=0,y=0;       // 注释掉的内容是空间上的优化(初学者建议先跳过)
    for(int i=1;i<=n;i  )
    {
        if(i%2)
        {
            x = read() ;
            Update(i,x-y);
        }
        else
        {
            y = read() ;
            Update(i,y-x) ;
        }
    }  */
    int ii ;
    int k,x,y;
    for(int i=1;i<=m;i  )
    {
        ii = read() ;
        if(ii == 1)
        {
            x = read() ; y = read() ; k = read() ;
            Update(x,k);
            Update(y 1,-k);
        }
        if(ii == 2)
        {
            x = read() ;
            printf("%dn",Sum(x));
        }
    }

本文由www.2003.com发布于计算机教程,转载请注明出处:浅谈树状数组,浅谈树状

关键词: