数据结构:线段树基础详解

时间:2022-10-25 15:07:46

1.简介

线段树,顾名思义,就是由线段构成的树,是一个较为优秀的数据结构,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点,通常用于解决区间类的问题,在各大OI赛事中频繁出现。下面我将为你展示线段树的一些基本操作及原理

2.存储

线段树一般用结构体存储,代码如下:

struct node{
    int l,r,num,add;
}tree[10010];
//add 用于懒标记

 3.建树

代码如下:

void buildtree(int x,int y,int p){
    t[p].l = x,t[p].r = y;
    if (x == y){
        t[p].sum = a[x];
        return;
    }
    int mid = x+y>>1;
    buildtree(x,mid,p<<1);
    buildtree(mid+1,y,(p<<1)+1);
    t[p].sum = t[p<<1].sum+t[(p<<1)+1].sum;
}

4.懒标记

从前有一个人,太懒了,修改线段树区间值时不想把线段树全都遍历一遍,于是就有了懒标记

懒标记的精髓就是打标记和下传操作,由于我们要做的操作是区间加一个数,所以我们不妨在区间进行修改时为该区间打上一个标记,就不必再修改他的儿子所维护区间,等到要使用该节点的儿子节点维护的值时,再将懒标记下放即可,可以节省很多时间,对于每次区间修改和查询,将懒标记下传,可以节省很多时间。当然,这一操作不是必要的,在不住求代码运行速度的时候可以不用

代码如下:

void tag(int p){
    if (t[p].add){ //如果懒标记不为空,则进行下传操作 
        t[p<<1].sum += t[p].add*(t[p<<1].r-t[p<<1].l+1); //这里,因为luogu的模板题中修改是对于区间内每一个值的所以是乘
        t[(p<<1)+1].sum += t[p].add*(t[(p<<1)+1].r-t[(p<<1)+1].l+1);
        t[p<<1].add += t[p].add;
        t[(p<<1)+1].add += t[p].add;
        t[p].add = 0;
    }
}

5.区间修改

从根节点自上而下查找,当发现有区间覆盖要修改的节点时,我们就把这一区间修改并打上懒标记。否则下传懒标记,继续查找。

代码如下:

void change(int p,int x,int y,int z){
    if (x<=t[p].l&&y>=t[p].r){
        t[p].sum+=(ll)z*(t[p].r-t[p].l+1);
        t[p].add+=z;
        return;
    }
    tag(p);
    int mid = t[p].l+t[p].r>>1;
    if (x<=mid){
        change(p<<1,x,y,z);
    } //左儿子包含于修改区间内 
    if (y>mid){ //用if 不用else if 
        change((p<<1)+1,x,y,z);
    } //右儿子包含于修改区间内
    t[p].sum = t[p<<1].sum+t[(p<<1)+1].sum; 
}

6.区间查询

考虑询问一个区间的和,依旧是从根节点向下查找,当发现该节点被覆盖时,就返回维护的值,否则下传懒标记,查询左右儿子,累加答案

代码如下:

long long ask(int p,int x,int y){
    if (x<=t[p].l&&y>=t[p].r){
        return t[p].sum;
    }
    tag(p);
    int mid = t[p].l+t[p].r>>1;
    long long ans = 0;
    if (x<=mid) ans+=ask(p<<1,x,y);
    if (y>mid) ans+=ask((p<<1)+1,x,y);
    return ans;
}

7.完整代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[101010];
struct node{
    ll l,r,sum,add;
}t[401010];
void buildtree(int x,int y,int p){
    t[p].l = x,t[p].r = y;
    if (x == y){
        t[p].sum = a[x];
        return;
    }
    int mid = x+y>>1;
    buildtree(x,mid,p<<1);
    buildtree(mid+1,y,(p<<1)+1);
    t[p].sum = t[p<<1].sum+t[(p<<1)+1].sum;
}
void tag(int p){
    if (t[p].add){ //如果懒标记不为空,则进行下传操作 
        t[p<<1].sum += t[p].add*(t[p<<1].r-t[p<<1].l+1);
        t[(p<<1)+1].sum += t[p].add*(t[(p<<1)+1].r-t[(p<<1)+1].l+1);
        t[p<<1].add += t[p].add;
        t[(p<<1)+1].add += t[p].add;
        t[p].add = 0;
    }
}
void change(int p,int x,int y,int z){
    if (x<=t[p].l&&y>=t[p].r){
        t[p].sum+=(ll)z*(t[p].r-t[p].l+1);
        t[p].add+=z;
        return;
    }
    tag(p);
    int mid = t[p].l+t[p].r>>1;
    if (x<=mid){
        change(p<<1,x,y,z);
    } //左儿子包含于修改区间内 
    if (y>mid){ //用if 不用else if 
        change((p<<1)+1,x,y,z);
    } //右儿子包含于修改区间内
    t[p].sum = t[p<<1].sum+t[(p<<1)+1].sum; 
}
ll ask(int p,int x,int y){
    if (x<=t[p].l&&y>=t[p].r){
        return t[p].sum;
    }
    tag(p);
    int mid = t[p].l+t[p].r>>1;
    ll ans = 0;
    if (x<=mid) ans+=ask(p<<1,x,y);
    if (y>mid) ans+=ask((p<<1)+1,x,y);
    return ans;
}
int main(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    buildtree(1,n,1);
    int k,c,s,p;
    for (int i=1;i<=m;i++){
        cin>>k;
        if (k == 1){
            cin>>c>>s>>p;
            change(1,c,s,p);
        }
        else if (k == 2){
            cin>>c>>s;
            cout<<ask(1,c,s)<<endl;
        }
    }
    return 0;
} 

 

Over~