浅谈线段树

iyka · 2024-11-04 14:00:21 · 算法·理论

前言

线段树是我十分喜欢的算法，同时他也是树链剖分的重要前置芝士，但作为一个蒟蒻，我并不会线段树的一些高级用法（哭），所以这篇文章只是我在日常使用普通线段树时的一些感悟，不会涉及到如吉司机线段树、李超线段树、线段树分裂等高级线段树用法（~~我太菜了~~）。

关于线段树

很多初学线段树的人都很懵，在这里我讲解一下。

问题引入

对于任意一个数组，我们要求它的区间和是十分简单的，直接去跑一遍这个区间就行了。

那我们升级一下难度，有 m 次查询呢？如果还是上面的做法的话，那时间复杂度就变成了 O(nm)，非常爆炸，但我们只要随意的使用一下前缀和大法，时间复杂度就变回了 O(n+m)。

那再升一下难度？在 m 次查询中加上对数组中一个值的修改，那就算时前缀和也变回了 O(nm)，可是先别慌，我们用一下树状数组就能在 O(\log{n}) 完成单点修改个区间查询，时间复杂度就变成了 O(m\log{n})，还是轻松解决。

可是 OI 的要求总是无穷无尽的，还要再升一次难度。将单点修改变为区间加上一个值，还要再多维护一个区间最值，先不说树状数组和前缀和不能维护区间最值，就是树状数组也的单点修改变为区间修改，那时间复杂度也变成了 O(nm\log{n})，甚至不如前缀和的 O(nm)。

其实上面这个问题就是我们的例题 P3372。

那现在该咋办呢？只能用线段树了呗。

线段树原理

先看一张图：

这是啥啊？有人就问。

那我现在告诉你这就是建成的线段树，最下面一排对应就是原数组，每两个相邻的元素就合并（可以是加和或最值），组成上一层的父节点。

此时建成的线段树有如下性质：

每个节点（除叶子节点外）的儿子都为两个。
树的深度为 \log{n}。

那这有啥用呢？

那对于一次查询如（n=8）：原数组编号为 3 到 7 之间的数的和，那我们就从一号根节点开始搜索，看到 3 到 7 在 1 到 8 这个区间内，于是继续向下二分，来到二号节点，发现 3 到 7 有部分在它的左区间处，跳到五号节点，发现刚好对应 3 到 4 这个区间，加上它的权值，回到三号节点继续向下搜。。。以此类推我们就能得到 3 到 7 之间的数的和。

区间修改也是一样的，只不过对于改变的权值我们直接加到最下面一层的话时间复杂度就会变回 O(n\log{n})，那该咋办呢？

懒标记（lazy_tag）

我喜欢线段树的很大一部分原因就是因为懒标记，它很完美的诠释了什么叫有用再取的思维。

说句题外话，其实对于很多算法，它总有一些重复去计算的部分，不少的优化思路都是去减少重复计算的部分，比如离线处理等思路。但其实还有一种很优雅的思路就是有用再取。就好像做手工，拿的钉子肯定是有用再拿，一把把钉子全部拿出最后再放回去那肯定是没那么优的。

说远了，我们回到懒标记。对于一次区间修改，要在对应的区间加上 k，我们和上面区间查询一样先搜索出所对应的能刚好包含的全部区间块，给它们打上懒标记，就是用一个数组去记录现在这个区间加上的 k。

那总有要将这个区间再次分开向下搜索的情况的，那该怎么办呢？

其实也很简单，搜索到这个区间时，将这一个块的懒标记向下先推一层，清空懒标记，对于这个区间快要总共加上的值就是 (r-l+1)\times k，这就是有用再取，这样时间就还是 O(\log{n})，思考一下，为什么呢？

线段树的优化本质

线段树其实就是对两个地方经行了优化，一个是区间查询，另一个就是区间修改（我好像在说废话）。

区间查询：对于区间查询，最本质的就是二分递归，多亏了线段树作为一个二分树，利用二分的性质就可以把 n 次的查询变为了 \log{n}。
区间修改：首先还是二分递归查找，然后就是懒标记把会重复的步骤从可能的 n\log{n} 变回了 \log{n}。

所以其实写好了二分递归部分和懒标记的下放，线段树就完成了。

代码实现

其实理解好线段树，代码实现也挺简单的。

建树+懒标记

建树

对于建树函数，我们只有三个参数：线段树数组编号（idx）、目前对应的区间左边界（l）和右边界（r）。

我们先来手推一下，先传入参数 (1,1,n)，然后我们分开成 (2,1,(int)n/2) 和 (3,(int)n/2+1,n) 继续向下递归……直到递归到了 l=r 时我们有 a_l\to tree_{idx}，这时就向上回溯，对于回溯中的每一个节点有 tree_{\text{左儿子}}+tree_{\text{右儿子}}\to tree_{idx}，这样我们就把 tree 数组处理出来了。

在手推的过程中我们不难发现对于一个编号为 idx 的节点，它的左儿子编号就为 idx\times 2，右儿子编号就为 idx\times 2+1。先定义有 \lfloor\frac{l+r}{2}\rfloor\to mid，这样左儿子的递归参数就可以写为 (idx<<1,l,mid)，右儿子的递归参数就可以写为 (idx<<1|1,mid+1,r)，其中 <<、| 为位运算符号，是为了给程序提速的，通常下，我们给 mid 赋值的语句也使用位运算，写为 mid=l+r>>1。

代码：

void build(int idx,int l,int r)
{
    if(l==r)
    {
        tree[idx]=num[l];
        return;
    }
    int mid=l+r>>1;
    build(idx<<1,l,mid);
    build(idx<<1|1,mid+1,r);
    tree[idx]=tree[idx<<1]+tree[idx<<1|1];
}

懒标记

对于懒标记（tag）就非常简单了，我们分成两个函数来实现，一个为 push_down，一个为 add。

上面也说过了，tag_{idx} 对应到 tree_{idx} 上就是 (r-l+1)\times k，所以对于 add 函数我们就有 tag_{idx}+k\to tag_{idx} 和 tree_{idx}+(r-l+1)\times k\to tree_{idx}，而 push_down 函数也就是将 tag_{idx} 向下推一层并将 tag_{idx} 赋值为 0 而已。

代码：

void add(int idx,int l,int r,int k)
{
    tree[idx]+=(r-l+1)*k;
    tag[idx]+=k;
}
void push_down(int idx,int l,int r)
{
    if(tag[idx]==0)
        return;
    int mid=l+r>>1;
    add(idx<<1,l,mid,tag[idx]);
    add(idx<<1|1,mid+1,r,tag[idx]);
    tag[idx]=0;
}

区间查询和修改

区间查询

其实大概的方法在上面也都说过了，就是从 tree_1 向下二分，寻找深度最少的多个能将查询区间完全包含的区间块并在回溯时将他们的值累加（或取最值）就行了，向下二分的方法大体是和建树是一样的，只是要注意有些区间块是不能将左右儿子都走的，可以稍微剪一下支。

long long query(int idx,int l,int r,int x,int y)
{
    if(x<=l && y>=r)
        return tree[idx];
    int mid=(l+r)>>1;
    ll res=0;
    push_down(idx,l,r,mid);//记得要下放懒标记哦
    if(x<=mid)
        res+=query(idx<<1,l,mid,x,y);
    if(y>mid)
        res+=query(idx<<1|1,mid+1,r,x,y);
    return res;
}

区间修改

说实话线段树代码实现中还是有很多重复的地方的（因为都要向下找到需要的区间块嘛），所以区间修改和区间查询是非常像的，只不过在搜索到对应的区间块时不是返回其值，而是给这个区间块打上懒标记。

void update(int idx,int l,int r,int x,int y,int k)
{
    if(x<=l && y>=r)
    {
        add(idx,l,r,k);
        return;
    }
    int mid=(l+r)>>1;
    push_down(idx,l,r,mid);//千万不要忘了
    if(x<=mid)
        update(idx<<1,l,mid,x,y,k);
    if(y>mid)
        update(idx<<1|1,mid+1,r,x,y,k);
    tree[idx]=tree[idx<<1]+tree[idx<<1|1]; 
}

封装版

我个人是比较喜欢线段树封装起来用的，十分美观。

class Sigment_Tree
{
    private:
        long long tree[N<<2],tag[N<<2];
        void add(int idx,int l,int r,int k)
        {
            tree[idx]+=(r-l+1)*k;
            tag[idx]+=k;
        }
        void push_down(int idx,int l,int r,int mid)
        {
            if(tag[idx]==0)
                return ;
            add(idx<<1,l,mid,tag[idx]);
            add(idx<<1|1,mid+1,r,tag[idx]);
            tag[idx]=0;
        }
    public:
        void build(int idx,int l,int r)
        {
            if(l==r)
            {
                tree[idx]=a[l];
                return;
            }
            int mid=(l+r)>>1;
            build(idx<<1,l,mid);
            build(idx<<1|1,mid+1,r);
            tree[idx]=tree[idx<<1]+tree[idx<<1|1];
        }
        void update(int idx,int l,int r,int x,int y,int k)
        {
            if(x<=l && y>=r)
            {
                add(idx,l,r,k);
                return;
            }
            int mid=(l+r)>>1;
            push_down(idx,l,r,mid);
            if(x<=mid)
                update(idx<<1,l,mid,x,y,k);
            if(y>mid)
                update(idx<<1|1,mid+1,r,x,y,k);
            tree[idx]=tree[idx<<1]+tree[idx<<1|1]; 
        }
        long long query(int idx,int l,int r,int x,int y)
        {
            if(x<=l && y>=r)
                return tree[idx];
            int mid=(l+r)>>1;
            long long res=0;
            push_down(idx,l,r,mid);
            if(x<=mid)
                res+=query(idx<<1,l,mid,x,y);
            if(y>mid)
                res+=query(idx<<1|1,mid+1,r,x,y);
            return res;
        }
}smt;

一些可能的问题

仔细看一下我封装的代码，你们会发现我 tree 和 tag 都开了四倍空间，线段树代码不过有很大一部分原因就是因为空间开小了。

在写代码时记得写一个函数就检查一下递归中参数、边界条件等是否有写错，不然写完再去检查会非常耗时并令人发狂。

线段树的运用

大家都知道，数据结构的很大一个用途就是给算法中部分区间操作问题作优化的，线段树也不例外，我们这里来用一道题讲一下其中最为常见的线段树优化动态规划。

题目 P4644

我们考虑这道题的动态规划做法，可以将其转化为一个二维区间覆盖问题，先将每个小区间以右端点从小到大排序。设 dp_i 为覆盖 [L,i] 这个区间所用的最小花费，这里我们就可以得到一个比较常用的动态规划式子。

dp_{r_i}\gets \min_{k\in [l_i,r_i]}{dp_k}+val_i

设 Len\gets E-M+1，那这样子的时间复杂度为 O(NLen)，是肯定不行的，这个时候我们注意到对于式子中求区间最小值的部分我们是可以用线段树去维护的，这样我们的时间复杂度就为 O(N\log{Len})，可以通过此题。

代码部分

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,inf=0x3f3f3f3f;
int dp[N],n,m,e,len;
struct node
{
    int l,r,s;
    bool operator <(const node y)const
    {
        return r<y.r;
    }
}cow[N];
class sigment_tree
{
    private:
        int tree[N<<2];
    public:
        void build(int idx,int l,int r)
        {
            tree[idx]=inf;
            if(l==r)
                return;
            int mid=l+r>>1;
            build(idx<<1,l,mid);
            build(idx<<1|1,mid+1,r);
        }
        void update(int idx,int l,int r,int x,int k)
        {
            if(x==l && x==r)
            {
                tree[idx]=k;
                return;
            }
            int mid=l+r>>1;
            if(x<=mid)
                update(idx<<1,l,mid,x,k);
            if(x>mid)
                update(idx<<1|1,mid+1,r,x,k);
            tree[idx]=min(tree[idx<<1],tree[idx<<1|1]);
        }
        int query(int idx,int l,int r,int x,int y)
        {
            if(x<=l && y>=r)
                return tree[idx];
            int mid=l+r>>1,res=INT_MAX;
            if(x<=mid)
                res=min(res,query(idx<<1,l,mid,x,y));
            if(y>mid)
                res=min(res,query(idx<<1|1,mid+1,r,x,y));
            return res;
        }
}smt;
signed main()
{
    cin>>n>>m>>e; m++, e++;
    for(int i=1,a,b,c;i<=n;++i)
    {
        cin>>a>>b>>cow[i].s;
        cow[i].l=max(a+1,m);
        cow[i].r=min(b+1,e);
    }
    for(int i=1;i<=e;++i)
        dp[i]=inf;
    dp[m]=0;
    smt.build(1,m-1,e);
    sort(cow+1,cow+n+1);
    smt.update(1,m-1,e,m,0);
    for(int i=1;i<=n;++i)
    {
        dp[cow[i].r]=min(dp[cow[i].r],smt.query(1,m-1,e,cow[i].l-1,cow[i].r)+cow[i].s);
        smt.update(1,m-1,e,cow[i].r,dp[cow[i].r]);
    }
    if(dp[e]==inf)
        return cout<<-1, 0;
    cout<<dp[e];
    return 0;
}

写在最后的话

线段树真的是一个十分美妙的数据结构，希望大家可以灵活运用线段树，多写多练，发挥它的才能！

一些练习题目

\large \texttt{ by\ iyka}