线段树【模板】及解释

众所周知，线段树是一种十分狗好用的算法。
线段树是通过一颗每个节点都有两个儿子或一个儿子没有的二叉树中任何一个节点的左儿子的编号一定是这个节点的编号乘上2，右儿子则是再加1。
因此，将树的每一个节点定义为一段区间，里面维护自己想要的在区间中的值，如图所示
线段树【模板】及解释
写线段树的第一步当然就是建造一颗这样的树，建树程序如下，时间复杂度（n log n）

void build(int ll,int rr,int number){
    if(ll>rr)return;
    tree[number].l=ll;tree[number].r=rr;
    if(ll==rr)return;
    int mid=(ll+rr)/2;
    build(ll,mid,number*2);
    build(mid+1,rr,number*2+1);
}

建树程序一般要根据题目来修改，但大致都是这样的

对于线段树的修改和查询，我们就以最简单的模板，也就是区间和修改为例（luogu p3372）

将一段区间的所有数加上x的代码如下

void in(int number,int ll,int rr,long long s){
    if(!tree[number].l)return;
    if(ll<=tree[number].l&&tree[number].r<=rr){
        tree[number].value+=(tree[number].r-tree[number].l+1)*s;
        tree[number].lazy+=s;
        return;
    }
    else
    {
        if(tree[number].lazy)down(number);
        if(ll<=(tree[number].l+tree[number].r)/2){
            in(number*2,ll,rr,s);
        }
        if(rr>(tree[number].l+tree[number].r)/2){
            in(number*2+1,ll,rr,s);
        }
        tree[number].value=tree[number*2].value+tree[number*2+1].value;
    }
}

这里我们用到了lazy_tag，俗称懒标记。
这玩意可以给线段树优化很多的时间，在不加lazy时，线段树每次查询修改时间复杂度为O（2n），而优化后就是O（log n）。
懒标记的思想就是能不往你儿子上传的值就先不传，除非你儿子需要这个值了，否则就一直累加。（lazy里只记区间内每个节点应该加上多少的值）
这里用到了down，这是一个实现lazy的过程，代码如下

void down(int number){
    int l=tree[number].l,r=tree[number].r;
    int mid=(l+r)/2;
    tree[number*2].value+=tree[number].lazy*(mid-l+1);
    tree[number*2].lazy+=tree[number].lazy;
    tree[number*2+1].value+=tree[number].lazy*(r-mid);
    tree[number*2+1].lazy+=tree[number].lazy;
    tree[number].lazy=0;
}

最后就是查询操作了，这个操作可以用函数也可以用过程，笔者的代码用的就是过程，具体如下

void query(int number,int ll,int rr){
    if(!tree[number].l)return;
    if(ll<=tree[number].l&&tree[number].r<=rr){
        ans+=tree[number].value;
        return;
    }
    else{ 
        if(tree[number].lazy){
    		down(number);
        }
        if(ll<=(tree[number].l+tree[number].r)/2){
            query(number*2,ll,rr);
        }
        if(rr>(tree[number].l+tree[number].r)/2){
            query(number*2+1,ll,rr);
        }
    }
}

把这些代码组合一下，再加上简短的主程序，就是一个基础的线段树模板

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long sum[100010];
long long ans;
struct node{
    int l,r;
    long long value,lazy;
}tree[400050]; //需要开四倍n，不然会炸 
void down(int number){//lazy下传 
    int l=tree[number].l,r=tree[number].r;
    int mid=(l+r)/2;
    tree[number*2].value+=tree[number].lazy*(mid-l+1);
    tree[number*2].lazy+=tree[number].lazy;
    tree[number*2+1].value+=tree[number].lazy*(r-mid);
    tree[number*2+1].lazy+=tree[number].lazy;
    tree[number].lazy=0;
}
void build(int ll,int rr,int number){//建树 
    if(ll>rr)return;
    tree[number].l=ll;tree[number].r=rr;
    if(ll==rr)return;
    int mid=(ll+rr)/2;
    build(ll,mid,number*2);
    build(mid+1,rr,number*2+1);
}
void in(int number,int ll,int rr,long long s){//修改区间和操作 
    if(!tree[number].l)return;
    if(ll<=tree[number].l&&tree[number].r<=rr){
        tree[number].value+=(tree[number].r-tree[number].l+1)*s;
        tree[number].lazy+=s;
        return;
    }
    else
    {
        if(tree[number].lazy)down(number);
        if(ll<=(tree[number].l+tree[number].r)/2){//判定边界 
            in(number*2,ll,rr,s);
        }
        if(rr>(tree[number].l+tree[number].r)/2){
            in(number*2+1,ll,rr,s);
        }
        tree[number].value=tree[number*2].value+tree[number*2+1].value;//根据儿子时刻更新 
    }
}
void query(int number,int ll,int rr){//查询 
    if(!tree[number].l)return;
    if(ll<=tree[number].l&&tree[number].r<=rr){
        ans+=tree[number].value;
        return;
    }
    else{ 
        if(tree[number].lazy){
    		down(number);
        }
        if(ll<=(tree[number].l+tree[number].r)/2){
            query(number*2,ll,rr);
        }
        if(rr>(tree[number].l+tree[number].r)/2){
            query(number*2+1,ll,rr);
        }
    }
}
int main(){
   scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=n;i++){
    	int v;
    	scanf("%d",&v);
    	sum[i]=sum[i-1]+v;
    }
    for(int i=1;i<=m;i++){
        int temp,x,y;
        scanf("%d%d%d",&temp,&x,&y);
        if(temp==1){
        	long long z;
        	scanf("%lld",&z);
        	in(1,x,y,z);
        }
        else{
            ans=0;
            query(1,x,y);
            ans+=sum[y]-sum[x-1];
            printf("%lld\n",ans);
        }
    }
    return 0;
}

特别注意线段树的树的结构体要开四倍长度，否则基本上会RE

线段树【模板】及解释

相关推荐