线段树模板简略解释

2018-06-29 06:14:41来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

 引例◎

在详细解释之前,我们先来看一下洛谷上的两个线段树模板题目(洛谷P3372、P3373)。

模板(一)

模板(二)

       从这几到题目可以看出,线段树的基本操作大致有三种:①给区间中的每一个元素加一个值  ②给区间中的每一个元素乘一个值  ③求出一个区间的每个元素和,下面我们先对线段树做一个基本的了解。

 ◎线段树的定义和结构◎

线段树的定义

       线段树是一种二叉搜索树,时间复杂度为O(nlogn)。

线段树的结构

       线段树,顾名思义,是树形结构,如下图所示:

       线段树应用了二分的思想,“树根”带表总的区间,然后不断对区间二分,直到代表单个值。在上述两个例题中,线段树的节点值都代表了所覆盖区间的元素和,在一些其他情况下,这个节点值也可以代表其他的东西,例如:区间的最大值或者最小值等等。

◎线段树的建树◎

       线段树的建树过程就是一个不断二分区间的过程(解释的通俗,但是可能不准确……)。从最大的区间开始,一步一步的二分,直到左右区间重合,也就是到了叶子结点,就开始给线段树赋值,下面附建树代码(本文的代码都是上文例题中的节选,在不同的题目中,可能有所不同)

void build(int l,int r,int u){ //[l,r]区间,u节点 
    tree[u].l=l,tree[u].r=r;
    if(tree[u].l==tree[u].r){ //[l,r]区间只有一个数(到达低端) 
        scanf("%lld",&tree[u].w);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,u+u); //建立左子树 
    build(mid+1,r,u+u+1); //建立右子树 
    tree[u].w=tree[u+u].w+tree[u+u+1].w; //根节点=左子树+右子树
}

◎线段树的区间修改◎

        区间修改可以说是线段树最难理解的一部分,因为在这里有线段树特有的标记,名叫——懒惰标记(lazytag)。这个标记的大致作用就是在修改的时候,只修改当前节点,而不是全部,这也是线段树时间复杂度低的原因,而这就用到了lazytag,用来记录修改操作。然后,下一次修改时,如果当前的标记影响到了修改,就将标记下推。

◎线段树的区间查询◎

       在熟练区间修改之后,查询就相对来说简单了,依旧是应用了二分的思想。

◎例题代码◎

例题(一)

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
int n,m,x,y,k,q;
long long ans;
struct Tree{
    int l;
    int r; //[l,r]区间 
    long long int w; //当前区间的值 
    int lazytag;
}tree[MAXN<<2]; //MAXN*2^2
inline void build(int l,int r,int u){ //[l,r]区间,u节点 
    tree[u].l=l,tree[u].r=r;
    if(tree[u].l==tree[u].r){ //[l,r]区间只有一个数(到达低端) 
        scanf("%lld",&tree[u].w);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,u+u); //建立左子树 
    build(mid+1,r,u+u+1); //建立右子树 
    tree[u].w=tree[u+u].w+tree[u+u+1].w; //根节点=左子树+右子树
}
inline void down(int u){
    tree[u+u].lazytag+=tree[u].lazytag;
    tree[u+u+1].lazytag+=tree[u].lazytag; //lazytag下推 
    tree[u+u].w+=(tree[u+u].r-tree[u+u].l+1)*tree[u].lazytag;
    tree[u+u+1].w+=(tree[u+u+1].r-tree[u+u+1].l+1)*tree[u].lazytag; //重置区间值
    tree[u].lazytag=0; //删除lazytag
}
inline void change(int u){
    if(tree[u].l>=x && tree[u].r<=y){ //--->[x,y]区间包含[l,r]区间
        tree[u].w+=(tree[u].r-tree[u].l+1)*k; //[l,r]的和加个数*k
        tree[u].lazytag+=k; //lazytag----该节点以下的叶节点+k
        return;
    }
    if(tree[u].lazytag) down(u); //有lazytag就下推
    int mid=(tree[u].l+tree[u].r)>>1;
    if(x<=mid) change(u+u); //修改左区间
    if(mid<y) change(u+u+1); //修改右区间
    tree[u].w=tree[u+u].w+tree[u+u+1].w; //重置节点值
}
inline void ask(int u){
    if(tree[u].l>=x && tree[u].r<=y){ //--->[x,y]区间包含[l,r]区间
        ans+=tree[u].w;
        return;
    }
    if(tree[u].lazytag) down(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(x<=mid) ask(u+u);
    if(y>mid) ask(u+u+1);
}
int main(){
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=m;i++){
        scanf("%d",&q);
        if(q==1){
            scanf("%d%d%d",&x,&y,&k);
            change(1);
        }
        else{
            ans=0;
            scanf("%d%d",&x,&y);
            ask(1);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

 

例题(二)

#include<bits/stdc++.h>
#define MAXN 100100
using namespace std;
typedef long long LL;
struct Tree{
    LL l;
    LL r;
    LL w;
    LL jl;
    LL cl;
    Tree(){
        l=r=jl=0;
        w=0;
        cl=1;
    }
}tree[MAXN<<2];
LL n,m;
LL ans,p;
LL q,x,y,k;
LL read(){
    LL x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}
void build(int l,int r,int u){
    tree[u].l=l;
    tree[u].r=r;
    if(l==r){
        tree[u].w=read()%p;
        return;
    }
    int m=(l+r)>>1;
    build(l,m,u+u);
    build(m+1,r,u+u+1);
    tree[u].w=(tree[u+u].w+tree[u+u+1].w)%p;
}
void down(int u){
    tree[u+u].w=(tree[u+u].w*tree[u].cl+tree[u].jl*(tree[u+u].r-tree[u+u].l+1))%p;
    tree[u+u+1].w=(tree[u+u+1].w*tree[u].cl+tree[u].jl*(tree[u+u+1].r-tree[u+u+1].l+1))%p;
    tree[u+u].cl=(tree[u+u].cl*tree[u].cl)%p;
    tree[u+u+1].cl=(tree[u+u+1].cl*tree[u].cl)%p;
    tree[u+u].jl=(tree[u+u].jl*tree[u].cl+tree[u].jl)%p;
    tree[u+u+1].jl=(tree[u+u+1].jl*tree[u].cl+tree[u].jl)%p;
    tree[u].cl=1;
    tree[u].jl=0;
    return;
}
void add(int u){
    if(tree[u].l>y || tree[u].r<x) return;
    if(tree[u].l>=x && tree[u].r<=y){
        tree[u].jl=(tree[u].jl+k)%p;
        tree[u].w=(tree[u].w+k*(tree[u].r-tree[u].l+1))%p;
        return;
    }
    down(u);
    int m=(tree[u].r+tree[u].l)>>1;
    if(m>=x) add(u+u);
    if(m<y) add(u+u+1);
    tree[u].w=(tree[u+u].w+tree[u+u+1].w)%p;
}
void mul(int u){
    if(tree[u].l>y || tree[u].r<x) return;
    if(tree[u].l>=x && tree[u].r<=y){
        tree[u].w=(tree[u].w*k)%p;
        tree[u].cl=(tree[u].cl*k)%p;
        tree[u].jl=(tree[u].jl*k)%p;
        return;
    }
    down(u);
    int m=(tree[u].r+tree[u].l)>>1;
    if(m>=x) mul(u+u);
    if(m<y) mul(u+u+1);
    tree[u].w=(tree[u+u].w+tree[u+u+1].w)%p;
}
LL search(int u){
    if(tree[u].l>y || tree[u].r<x) return 0;
    if(tree[u].l>=x && tree[u].r<=y) return tree[u].w%p;
    down(u);
    int m=(tree[u].r+tree[u].l)>>1;
    return (search(u+u)+search(u+u+1))%p;
}
int main(){
    int i,j;
    n=read(),m=read(),p=read();
    build(1,n,1);
    for(i=1;i<=m;i++){
        q=read();
        if(q==1){
            x=read(),y=read(),k=read();
            mul(1);
        }
        else if(q==2){
            x=read(),y=read(),k=read();
            add(1);
        }
        else{
            x=read(),y=read();
            cout<<search(1)<<endl;
        }
    }
    return 0;
}

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:29.QT-自定义窗口拖动、自定义QToolButton/QPushButton开关按钮

下一篇:大专生自学c++到找到工作的前前后后