线段树（学习笔记）

· · 算法·理论

线段树

例题

一.功能：

线段树可以用来处理区间问题如 “区间和” 虽然区间和可以用前缀和解决，用O(1) 的复杂度进行查询，但修改需要O(n)的复杂度。同理差分可以以O(1)的复杂度进行修改，但需要O(n)的复杂度进行查询。
所以线段树可以同时用O(logn)的复杂度进行查询和修改。同时线段树可以维护多种不同的区间关系,如区间乘，区间最大数等

二.原理：

利用了分治的思想，将一个数列进行二分建树用根来维护此小区间的区间关系，如区间最大值一个数列的最大值也就等于它左半部分的最大值和右半部分的最大值的最大值。

三.实现（以例题为例）;

1.建立线段树：

运用递归的思想，若当前根节点为p则其左儿子lc为p<<1,右儿子为p<<1|1。这样就可以用数组表示线段树，在建起左子树和右子树，最后在根据左右子树的关系给当前根节点进行赋值sum。时间复杂度为nlogn

void build(int p,int l,int r){
    if(l==r){
        tr[p].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}

2.单点修改;

我们只需要知道要修改的点的坐标，然后递归遍历，看它是在左儿子的区间内还是右儿子的区间，直到找到这个数，在回溯修改所有的根节点的值。时间复杂度为logn

void update(int p,int l,int r,int add,int p){
    if(l==r){
        tr[p].sum+=add;
        return;
    }
    int mid=(l+r)>>1;
    if(l<=p && p<=mid)update(lc,l,mid,add,p);
    if(mid+1<=p && p<=r)update(rc,mid+1,r,add,p);
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}

3.区间修改：

但如果要修改整个区间的值时该怎么办，若是一个一个单点修改那时间复杂度为nlogn，比暴力还要慢。这时候我们可以想到加一个懒标志，若当前递归到的区间在我要修改的区间之内，就不往下遍历了，等后面需要往下走的时候顺便修改了，这样就可以把时间复杂度压缩到logn

void Add(int p,int l,int r,int add){
    tr[p].add+=add;
    tr[p].sum+=add*(r-l+1);
} 
void push_down(int p,int l,int r){
    int mid=(l+r)>>1;
    if(tr[p].add==0)return;
    Add(lc,l,mid,tr[p].add);
    Add(rc,mid+1,r,tr[p].add);
    tr[p].add=0;
}
void update(int p,int l,int r,int add,int ll,int rr){
    if(ll<=l && r<=rr){
        Add(p,l,r,add);
        return;
    }
    int mid=(l+r)>>1;
    push_down(p,l,r);
    if(ll<=mid)update(lc,l,mid,add,ll,rr);
    if(rr>mid)update(rc,mid+1,r,add,ll,rr);
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}

4.查询：

查询一段区间时，我们不需要一个一个遍历，我只需要找到所有包含于查询区间的值，最后累加即可，也是用递归查找，同时在查询中可以顺便转移懒标志pushdown一下即可

int query(int p,int l,int r,int ll,int rr){
    if(ll<=l && r<=rr){
        return tr[p].sum;
    }
  push_down(p,l,r);
    int mid=(l+r)>>1;
    int res=0;
    if(ll<=mid)res+=query(lc,l,mid,ll,rr);
    if(rr>mid)res+=query(rc,mid+1,r,ll,rr);
    return res;
}

四.完整代码：

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define int long long
using namespace std;
const int N=100010;
struct edge{
    int sum,add;
}tr[N*4];
int a[N];
void Add(int p,int l,int r,int add){
    tr[p].add+=add;
    tr[p].sum+=add*(r-l+1);
} 
void push_down(int p,int l,int r){
    int mid=(l+r)>>1;
    if(tr[p].add==0)return;
    Add(lc,l,mid,tr[p].add);
    Add(rc,mid+1,r,tr[p].add);
    tr[p].add=0;
}
void build(int p,int l,int r){
    if(l==r){
        tr[p].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}
void update(int p,int l,int r,int add,int ll,int rr){
    if(ll<=l && r<=rr){
        Add(p,l,r,add);
        return;
    }
    int mid=(l+r)>>1;
    push_down(p,l,r);
    if(ll<=mid)update(lc,l,mid,add,ll,rr);
    if(rr>mid)update(rc,mid+1,r,add,ll,rr);
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}
int query(int p,int l,int r,int ll,int rr){
    if(ll<=l && r<=rr){
        return tr[p].sum;
    }
    push_down(p,l,r);
    int mid=(l+r)>>1;
    int res=0;
    if(ll<=mid)res+=query(lc,l,mid,ll,rr);
    if(rr>mid)res+=query(rc,mid+1,r,ll,rr);
    return res;
}
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            int k;
            cin>>k;
            update(1,1,n,k,x,y);
        }
        if(op==2){
            cout<<query(1,1,n,x,y)<<endl;
        }
    }
}

五.练习：

1.P1198 [JSOI2008] 最大数 题解
2.P4588 [TJOI2018] 数学计算 题解
3.P2471 [SCOI2007] 降雨量 题解
4.P4145 上帝造题的七分钟 2 / 花神游历各国 题解
5.P2391 白雪皑皑 题解
6.P4513 小白逛公园 题解