线段树-基础

· · 算法·理论

线段树是什么？

线段树可以理解为一个二叉树，它将一个序列变成了一棵树状的结构，通过二叉树的一些性质，我们可以优化维护序列区间的时间复杂度，将 O(n) 复杂度的操作变为 O(log n)。

模板：

线段树的模板（建立树，单点查、修，区间查、修）
码量较多，因为有较多的操作。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000010;

ll a[maxn],w[maxn*4],lzy[maxn*4];//lzy为延迟标记数组(lazy_tag)

bool InRange(int L,int R,int l,int r){
    //工具：[L,R]是否被[l,r]包含 
    return (l<=L)&&(R<=r); 
} 
bool OutofRange(int L,int R,int l,int r){
    //工具：[L,R]是否和[l,r]完全无交集 
    return (L>r)||(R<l); 
} 
void maketag(int u,int len,ll x){
    //工具：延迟标记 
    lzy[u]+=x;//打标记 
    w[u]+=len*x;//修改当前节点区间和，len个x相加
}
void pushdown(int u,int L,int R){
    //工具：标记下方（把自己的延迟标记下放到子节点） 
    int M=(L+R)/2;
    maketag(u*2,M-L+1,lzy[u]);//给左子树加上lzy[u]
    maketag(u*2+1,R-M,lzy[u]);//给右子树加上lzy[u]
    lzy[u]=0;//去掉自己的标记 
} 
void pushup(const int u){
    //工具：更新 
    w[u]=w[u*2]+w[u*2+1];//当前节点=左子节点+右子节点。
    //这里就是在不断求和 
} 

void build(const int u,int L,int R){//操作：建立树 
    if(L==R){//到达叶节点 
        w[u]=a[L];//w[u]=数组a[L]的值 
        return;
    } 
    int M=(L+R)/2;
    build(u*2,L,M);build(u*2+1,M+1,R);//往左、右区间走 
    pushup(u);//更新当前区间的和。
    //类似回溯 
} 

ll query1(int u,int L,int R,int p){//操作：单点查询（但用线段树做多此一举） 
    if(L==R){
        return w[u];//找到叶结点就返回 
    }else{
        int M=(L+R)/2;//二分查找这一个坐标
        if(M>=p)return query1(u*2,L,M,p);
        else return query1(u*2+1,M+1,R,p); 
    } 
    //复杂度O(log n),如果就用数组O(1) 
} 

ll update1(int u,int L,int R,int p,ll x){//操作：单点修改(修改成x) 
    if(L==R)w[u]=x;
    else{//二分，没有什么好说的 
        int M=(L+R)/2;
        if(M>=p)update1(u*2,L,M,p,x); 
        else update1(u*2+1,M+1,R,p,x);
    }
    //和单点查一样，复杂度O(log n),如果就用数组O(1) 
}

//（接下来才是线段树该做的）
ll query(int u,int L,int R,int l,int r){//操作：区间查
    if(InRange(L,R,l,r))return w[u];//若全部包含则直接返回区间和
    else if(!OutofRange(L,R,l,r)){
        //相交一部分，则递归处理 
        int M=(L+R)/2;
        return query(u*2,L,M,l,r)+query(u*2+1,M+1,R,l,r);
        //左子节点+右子节点。 
    } 
    else return 0;//没有交集就是0 
} 

void update(int u,int L,int R,int l,int r,ll x){//操作：区间修(改为x) 
    if(InRange(L,R,l,r)){//完全包含 
        maketag(u,R-L+1,x);//直接达标记 
    }else if(!OutofRange(L,R,l,r)){
        int M=(L+R)/2;
        pushdown(u,L,R);//标记下传
        update(u*2,L,M,l,r,x);//左 
        update(u*2+1,M+1,R,l,r,x);//右
        pushup(u);//修改过后要更新（跟单点修一样） 
    }
}

int main(){
  //根据题做操作
    return 0;
}

建立树(也可以用 update)：

ll a[maxn],w[maxn*4];

void pushup(const int u){
    w[u]=w[u*2]+w[u*2+1];
} 

void build(const int u,int L,int R){
    if(L==R){
        w[u]=a[L];
        return;
    } 
    int M=(L+R)/2;
    build(u*2,L,M);build(u*2+1,M+1,R);
    pushup(u);
}

区间查：

ll a[maxn],w[maxn*4];

void pushup(const int u){
    w[u]=w[u*2]+w[u*2+1];
} 
bool InRange(int L,int R,int l,int r){
    return (l<=L)&&(R<=r); 
} 
bool OutofRange(int L,int R,int l,int r){
    return (L>r)||(R<l); 
}

ll query(int u,int L,int R,int l,int r){
    if(InRange(L,R,l,r))return w[u];
    else if(!OutofRange(L,R,l,r)){
        int M=(L+R)/2;
        return query(u*2,L,M,l,r)+query(u*2+1,M+1,R,l,r);
    } 
    else return 0;
}

区间修：

ll a[maxn],w[maxn*4],lzy[maxn*4];

void pushup(const int u){
    w[u]=w[u*2]+w[u*2+1];
} 
void maketag(int u,int len,ll x){
    lzy[u]+=x;
    w[u]+=len*x;
}
void pushdown(int u,int L,int R){
    int M=(L+R)/2;
    maketag(u*2,M-L+1,lzy[u]);
    maketag(u*2+1,R-M,lzy[u]);
    lzy[u]=0;
}

void update(int u,int L,int R,int l,int r,ll x){
    if(InRange(L,R,l,r)){
        maketag(u,R-L+1,x);
    }else if(!OutofRange(L,R,l,r)){
        int M=(L+R)/2;
        pushdown(u,L,R);
        update(u*2,L,M,l,r,x);
        update(u*2+1,M+1,R,l,r,x);
        pushup(u);
    }
}

例题

P3372【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上 k。
  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 n, m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 [x, y] 内每个数加上 k。
  2. 2 x y：输出区间 [x, y] 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1

样例输入 #1
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
样例输出 #1
11
8
20

提示

对于 30\% 的数据：n \le 8，m \le 10。
对于 70\% 的数据：n \le {10}^3，m \le {10}^4。
对于 100\% 的数据：1 \le n, m \le {10}^5。

保证任意时刻数列中所有元素的绝对值之和 \le {10}^{18}。

如果你想省一些码量，可以不写 build 操作，使用 update 每次修改一个点(长度为一的区间)，复杂度为 O(n log n)

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000010;

ll a[maxn],w[maxn*4],lzy[maxn*4];//lzy为延迟标记数组(lazy_tag)

bool InRange(int L,int R,int l,int r){
    //[L,R]是否被[l,r]包含 
    return (l<=L)&&(R<=r); 
} 
bool OutofRange(int L,int R,int l,int r){
    //[L,R]是否和[l,r]完全无交集 
    return (L>r)||(R<l); 
} 
void maketag(int u,int len,ll x){
    //延迟标记 
    lzy[u]+=x;//打标记 
    w[u]+=len*x;//修改当前节点区间和，len个x相加
}
void pushdown(int u,int L,int R){
    //标记下方（把自己的延迟标记下放到子节点） 
    int M=(L+R)/2;
    maketag(u*2,M-L+1,lzy[u]);//给左子树加上lzy[u]
    maketag(u*2+1,R-M,lzy[u]);//给右子树加上lzy[u]
    lzy[u]=0;//去掉自己的标记 
} 
void pushup(const int u){
    //更新区间和
    w[u]=w[u*2]+w[u*2+1];//当前节点=左子节点+右子节点。
    //这里就是在不断求和 
} 

ll query(int u,int L,int R,int l,int r){//操作：区间查
    if(InRange(L,R,l,r))return w[u];//若全部包含则直接返回区间和
    else if(!OutofRange(L,R,l,r)){
        //相交一部分，则递归处理 
        int M=(L+R)/2;
        return query(u*2,L,M,l,r)+query(u*2+1,M+1,R,l,r);
        //左子节点+右子节点。 
    } 
    else return 0;//没有交集就是0 
} 

void update(int u,int L,int R,int l,int r,ll x){//操作：区间修(改为x) 
    if(InRange(L,R,l,r)){//完全包含 
        maketag(u,R-L+1,x);//直接达标记 
    }else if(!OutofRange(L,R,l,r)){
        int M=(L+R)/2;
        pushdown(u,L,R);//标记下传
        update(u*2,L,M,l,r,x);//左 
        update(u*2+1,M+1,R,l,r,x);//右
        pushup(u);//修改过后要更新（跟单点修一样） 
    }
}
int main() {
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;++i) {
        ll val;cin>>val;
        update(1,1,n,i,i,val);//另一种建树的方法。
    }
    for(int i=1;i<=m;++i) {
        int opt;cin>>opt;
        if(opt==1) {
            int x,y;ll k;
            cin>>x>>y>>k;
            update(1,1,n,x,y,k);//区间修 
        }else{
            int x, y;
            cin>>x>>y;
            printf("%lld\n", query(1,1,n,x,y));//区间查 
        }
    }
    return 0;
}