首页 > > 程序设计 > C/C++ >

线段树模板简略解释

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

◎引例◎

在详细解释之前，我们先来看一下洛谷上的两个线段树模板题目（洛谷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;
}