声明    :

文章转载于http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464583.html

文章讲得很好,所以几乎是全部引用(仅部分修改),但是没有懒标记的讲解,所以我补充一下。

线段树作为一种十分常用的数据结构,在NOIP、NOI中广泛的出现,所以在这里对线段树进行简单的讲解。

线段树支持对一个数列的求和、单点修改、求最值(最大、最小)、区间修改(需要lazy标记,切不可循环单个修改,那么线段树就失去了意义)。这几种操作,时间复杂度是(logn)级别的,是一种十分优秀的数据结构。因此其获得了广泛的应用。

定义:顾名思义,它是一种树形结构,但每段不是平常所学的一个点一个点的树,而是一条一条的线段,每条线段包含着一些值,其中最主要的是起始和结束点记作 l,r 即左端点和右端点。

那么该如何划分线段树呢?我们采用二分的思想,即每次将一段取半,再进行接下来的操作,这样综合了操作的方便程度和时间复杂度。因为线段树通过二分得来,所以线段树是一颗二叉树。这也方便了对儿子查找。下面是线段树的图,有利于理解(以[5,10]为例,右子节点最好改为形如[6,10]这样的区间,较好理解):

建树:仅仅知道模型还是不够的,建树的过程是线段树的关键(build(1,1,n))从一号开始,左端是1,右端是n

位运算 i<<1 等效于 i*2  (i<<1)|1 等效于  i*2+1  加速。。。     

inline void update(int i)更新i节点维护的值(求和,最大……) 
{ 
    node[i].sum=node[i<<1].sum+node[(i<<1)|1].sum; 
    node[i].maxx=max(node[i<<1].maxx,node[(i<<1)|1].maxx); 
}

inline void build(int i,int l,int r)//inline 还是加速 
{
       node[i].l=l;node[i].r=r;//左右端点为当前递归到的 l 和 r    
       if(l==r){//若l==r 则当前的树节点是真正意义上的点 
         node[i].maxx=a[l];//最大值就是本身的值 
         node[i].sum=a[l];//区间的和就是本身的值 
        return;
       }
       int mid=(l+r)/2;//因为是二叉树所以以中点为分割点 
       build(i<<1,l,mid);//根据二叉树的知识,左儿子是i/2右儿子是i/2+1 
       build((i<<1)|1,mid+1,r);
       update(i);
}

数列求和:这是线段树的一个典型算法,其他的很多应用都是从中转化的。

为了求和我们定义一个函数sum(int i,int l,int r) i 是开始的树节点,我们默认为1。l 是区间的开始点,它的标号是在数列中的标号,r 是结束点其余同 l。帖下代码:

inline int sum(int i,int l,int r)//inline 又是加速   
{                                                 
  if(node[i].l==l&&node[i].r==r)
    return node[i].sum;//若树节点的左右区间与查找区间相同,返回其维护的sum  
  int mid=(node[i].l+node[i].r)/2;//确定该树节点的中点以确定继续查找左儿子还是右儿子     
  if(r<=mid) return sum(i<<1,l,r);//若查找区间最右端小于中点,则该区间完全包含于左儿子中 
    else if(l>mid) return sum((i<<1)|1,l,r);//最左端大于中点,查找右儿子 
      else return sum(i<<1,l,mid)+sum((i<<1)|1,mid+1,r)
      //若跨越中点,查找左儿子 l 到 mid ,和右儿子的 mid+1 到 r 并返回值 
}

区间求最值和区间求和大致相同,自己看一下

inline int Max(int i,int l,int r)
{
    if(node[i].l==l&&node[i].r==r)
     return node[i].maxx;
    int mid=(node[i].l+node[i].r)/2;
    if(r<=mid) return Max(i<<1,l,r);
      else if(l>mid) return Max((i<<1)|1,l,r);
        else return max(Max(i<<1,l,mid),Max((i<<1)|1,mid+1,r));
}

单点更新:和区间不同,但基本思想还是一样的。

inline void add(int i,int k,int v)//当前计算到的点为i,把数列中的第k个元素加v
{
    if(node[i].l==k&&node[i].r==k){//因为更改的单点,所以左右端点均和k相等
        node[i].sum+=v;
        node[i].maxx+=v;
        return;
    }
    int mid=(node[i].l+node[i].r)/2;
    if(k<=mid) add(i<<1,k,v);//若k小于mid则k在树节点i的左子树中
     else add((i<<1)|1,k,v);//反之
    update(i);//更新
}

最后贴下全部的代码基本可以做模板了,代码下面是本人补充的懒标记

#include<iostream>
#include<cstdio>
using namespace std;
struct tree{
    int l,r,sum,maxx;
};
tree node[100];
int n,m,a[100];
inline void update(int i)
{
    node[i].sum=node[i<<1].sum+node[(i<<1)|1].sum;
    node[i].maxx=max(node[i<<1].maxx,node[(i<<1)|1].maxx);
}

inline void build(int i,int l,int r)
{
    node[i].l=l;node[i].r=r;
    if(l==r){
      node[i].maxx=a[l];
      node[i].sum=a[l];
      return;
    } 
    int mid=(l+r)/2;
    build(i<<1,l,mid);
    build((i<<1)|1,mid+1,r);
    update(i);
}

inline void add(int i,int k,int v)
{
    if(node[i].l==k&&node[i].r==k){
        node[i].sum+=v;
        node[i].maxx+=v;
        return;
    }
    int mid=(node[i].l+node[i].r)/2;
    if(k<=mid) add(i<<1,k,v);
     else add((i<<1)|1,k,v);
    update(i);
}

inline int sum(int i,int l,int r)
{
    if(node[i].l==l&&node[i].r==r)
     return node[i].sum;
    int mid=(node[i].l+node[i].r)/2;
    if(r<=mid) return sum(i<<1,l,r);
     else if(l>mid) return sum((i<<1)|1,l,r);
       else return sum(i<<1,l,mid)+sum((i<<1)|1,mid+1,r);
}

inline int Max(int i,int l,int r)
{
    if(node[i].l==l&&node[i].r==r)
     return node[i].maxx;
    int mid=(node[i].l+node[i].r)/2;
    if(r<=mid) return Max(i<<1,l,r);
      else if(l>mid) return Max((i<<1)|1,l,r);
        else return max(Max(i<<1,l,mid),Max((i<<1)|1,mid+1,r));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int c,a,b;
        scanf("%d%d%d",&c,&a,&b);
        if(c==1) printf("%d\n",sum(1,a,b));
          else if(c==2) add(1,a,b);
            else if(c==3) printf("%d\n",Max(1,a,b));
    }    
}
inline void pushdown(ll x)
{//每次扫到一个区间,恰好如果他有标记的时候,标记下放到两个儿子区间,立马对儿子区间的值修改
    node[x<<1].lazy+=node[x].lazy;
    node[(x<<1)|1].lazy+=node[x].lazy;//下放标记
    node[x<<1].sum+=node[x].lazy*(node[x<<1].r-node[x].l+1);
    node[(x<<1)|1].sum+=node[x].lazy*(node[(x<<1)|1].r-node[(x<<1)|1].l+1);//这里是区间修改,共r-l+1个数,每个都加k,即标记的值
    node[x].lazy=0;//这个区间的标记已经下放,取消就可以了(之前已经给这个区间打过标记,也完成了更新操作,即标记完立马更新,所以不需要再次更新)
}
inline void add(ll x,ll l,ll r,ll k)
{
    if(node[x].l==l&&node[x].r==r)
     {//是要整个修改的区间,打标记,立马更新和(或最大、最小值)
     	node[x].lazy+=k;
     	node[x].sum+=k*(r-l+1);
     	return;
     }
    if(node[x].lazy) pushdown(x);//每次扫到标记区间,就下放标记,取消本区间标记
    ll mid=(node[x].l+node[x].r)>>1;
    if(r<=mid) add(x<<1,l,r,k);
     else if(l>mid) add((x<<1)|1,l,r,v);
      else add(x<<1,l,mid,v),add((x<<1)|1,mid+1,r,v);
    update(x);
}
inline ll query(ll x,ll l,ll r)
{
    if(node[x].l==l&&node[x].r==r)
     return node[x].sum;
    if(node[x].lazy) pushdown(x);//也是扫到标记区间下放,取消
    ll mid=(node[x].l+node[x].r)>>1;
    if(r<=mid) return query(x<<1,l,r);
     else if(l>mid) return query((x<<1)|1,l,r);
      else return query(x<<1,l,mid)+query((x<<1)|1,mid+1,r);
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int  i=1;i<=n;i++)
     scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
     {
     	scanf("%d%lld%lld",&q,&x,&y);
     	if(q==1)
     	 {
     	 	scanf("%lld",&v);
     	 	add(1,x,y,v);
          }
        else
         printf("%lld\n",query(1,x,y));
     }
    return 0;
}

欢迎来到睿屿青衫丶

avatar
 
微笑晕爱心心碎调皮难过尴尬惊讶惊吓酷泪奔吐彩虹害羞敲打喝彩抠鼻吐星星眼擦汗大笑蛋糕呲牙瞌睡咒骂吃瓜贪财骷髅鬼脸委屈奋斗笑哭摸头小纠结点赞笑崩发呆绿帽狂汗亲嘴么么机智抑郁色鄙视坏笑白眼左哼哼右哼哼捂嘴鼓掌可怜香肠嘴闭嘴墨镜认错思考拒绝鲜花愤怒嘟嘴不忍直视嘘emm流泪yeah睡觉扔鞋石化生病抽烟吐血偷笑衰兔牙害怕震惊捂嘴笑打盹疑问亲亲指开心喜欢阴险郁闷坏笑2搞怪汪好奇汪机智汪冷漠汪搞怪哈摆拍柴柴犬生气柴流泪柴张嘴柴挥爪柴佩服勾引拳头胜利赞踩滑稽
  订阅  
提醒