AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

线段树入门笔记

作者: 作者的头像   T-SHLoRk ,  2019-08-28 17:54:30 ,  阅读 1221


24


19

写在最前,感谢秦淮岸大佬以及其他同学的博客供我参考。

线段树(Segment Tree)

Introduction

线段树这种数据结构可以很好的处理区间查询和区间修改的问题,虽然树状数组也可以通过差分的思想来实现区间修改,但是树状数组通常只能用于区间求和,而线段树能够处理区间最大值/最小值等一系列问题。

录制_2019_08_04_21_53_05_755.gif

线段树虽然看起来是一个树状结构,但是我们通常使用数组来保存线段树。假设我们原是数组的大小为$n$。

那么线段树的需要开辟的空间一般是$4*n$。

直观上来说,类似于一颗满二叉树好像只需要$2*n$的空间就可以了。

现在我们考虑一个恰好有$N = 2^k + 1$个节点的数组,

那么这棵线段树有$k + 2$层(虽然最后一层只有最左边有两个节点),

但是对于深度为$k + 2$的树,

其满二叉树的节点个数为$2^{k +2} - 1$。

我们可以得到$lim \frac{2^{k+2}-1}{2^k+1}=4$。

所以在极端情况下,我们需要开$4*n$的空间。

在一棵线段树中,每个节点代表的是一个区间,叶子节点代表的是长度为1的区间
。假设一个节点代表的区间是$[L,R]$,

我们有$mid = (L+R)/2$,

那么其左孩子代表的区间就是$[L,mid]$,

右孩子代表的区间是$[mid + 1,R]$。

为了方便起见,线段树数组的长度为$4*n$

其下标我们通常从1开始,那么对应到二叉树,我们可以知道假设一个节点的数组下标为$idx$,

那么其左孩子的数组下标为$idx << 1(idx * 2)$,

其右孩子的数组下标为$idx<<1|1(idx*2+1)$。

建树

在上述动图中,我们可以发现在初始化数组的时候,我们是将节点的左右节点都初始化好了,才初始化根节点,事实上我们也的确如此。这里我们实现一个支持区间求和操作的线段树。

//将处理好的左右儿子节点的值更新给父节点
void push_up(int rt)
{
        tree[rt] = tree[rt << 1] + tree[rt << 1|1];
}
int A[],tree[];
//当前根节点rt对应的原数组区间为[start,end]
void build(int rt,int start,int end)
{
    //  当前节点应该是一个叶子节点了
    if(start == end)
            tree[rt] = A[start];
    else
    {       //  将当前节点代表的区间拆分成两半,分给左子树(rt << 1)和右子树(rt << 1|1)
        int mid = (start + end) >> 1;
        build(rt << 1,start,mid);
        build(rt << 1|1,mid + 1,end);
        push_up(rt);
    }
}
build(1,1,N);

单点修改

//将A[pos]的值修改为val
//当前区间的根节点下标rt,当前区间代表原数组的左右范围l,r,
void update(int rt,int l,int r,int pos,int val)
{
        if(l == r)
      {
            A[pos] = val
            tree[rt] = val;
            return;
      }
        int mid = (l + r) >> 1;
        if(x <= mid)
            update(rt<<1,l,mid,pos,val);
        else
            update(rt<<1 + 1,mid + 1,r,pos,val);
        push_up(rt);
}
update(1,1,N,2,5)//将A[pos] = 5;

区间求和

//当前根节点rt所对应的区间为[l,r],我们希望查询的区间和是[start,end]
int rangeSum(int rt,int l,int r,int start,int end)
{
    //  如果当前节点范围不在目标查找区间内
    //  如果当前节点对应区间恰好完整的在我们的目标区间中,直接返回该节点的值
    //  否则的话,分别在左右子树中查询,并完成累加和
    if(start > r || end < l) 
        return 0;
    else if(start <= l && end >= r)
        return tree[rt];
    else
    {
        int mid = (l + r) >> 1;
        int sum_left = rangeSum(rt << 1,l,mid,start,end);
        int sum_right = rangeSum(rt << 1|1,mid + 1,r,start,end);
        return sum_left + sum_right;
    }
}
rangeSum(1,1,N,2,5)

区间修改

线段树最精华的地方在于线段树的区间修改,如果我们需要修改一段区间$[L,R]$里面的值都加上$delta$,如果我们将其看作若干次单点更新,那么线段树的复杂度就会退化成$O(nlogn)$,这是我们不可接受的。于是线段树创造性的使用了懒惰标记(延迟标记)来实现区间修改,简单的说,就是我们再对一个区间进行修改的时候,我们把这个大区间分成若干个小区间,每次只修改代表这些小区间的节点上的标记,因为一个区间最多分成$O(logn)$个小区间,所以我们可以在$O(logn)$的时间内完成修改。

çº¿æ®µæ ‘.jpg

以上图为例,假如我们想将区间$[3,7]$的值都加上$delta$,我们可以发现$[3,7]$可以拆分成$[3,4],[5,6],[7,7]$分别对应上图中的5,6,14号节点,因此我们只需要将这几个节点进行修改。

typedef long long ll;
ll A[N],tree[N],tag[4*N];
//  push_down函数的意义在于将父节点的tag信息传递给两个孩子节点。
//  tree存储的是当前节点区间和,所以将tag传递给孩子节点时,孩子节点的值要加上区间长度乘以tag值
//  tag信息传递给孩子之后,父节点的tag信息就清空啦
void push_down(int rt,int l,int r)
{
        if(tag[rt] != 0)
      {
                int mid = (l + r) >> 1;
                ll lazy = tag[rt];
                int left = rt << 1,right = rt << 1|1;
                tag[left] += lazy,tag[right] += lazy;
                tree[left] += lazy * (mid - l + 1);
                tree[right] += lazy * (r - mid);
                tag[rt] = 0;
      }
}
//  将区间[start,end]的值都加上delta
//  如果当前区间[l,r]是[start,end]的真子集,那么直接修改当前节点对应的区间不用递归向下修改了
//  记住,我们修改的值包括区间和(tree数组)和延迟标记(tag数组)
//  否则我们需要递归查找当前节点rt的左右孩子,在进行递归查找之前我们需要先将当前节点已经存在的延迟标记传下去(push_down函数)。
//  然后再根据左子树是否有目标区间的元素和右子树是否有目标区间的元素进行递归修改。
//  最后不要忘记更新当前节点的值
void updateRange(int rt,int l,int r,int start,int end,ll delta)
{
    if(start <= l && end >= r)
    {
            tree[rt] += (r - l + 1)*delta;
            tag[rt] += delta;
            return;
    }
    push_down(rt,l,r);
    int mid = (l + r) >> 1;
    if(start <= mid) updateRange(rt << 1,l,mid,start,end,delta);
    if(end >= mid + 1)updateRange(rt << 1|1,mid + 1,r,start,end,delta);
    push_up(rt);
}

带区间修改的区间查询

因为我们给每个节点带上了延迟标记,所以之前的区间查询函数我们也需要进行相应的修改。

// 查询区间[start,end]的和
//  如果当前区间节点rt对应的区间[l,r]是[start,end]的真子集,那么直接返回当前节点的值就可以啦。
//  否则我们要将当前节点的延迟标记先传递给左右孩子,然后对左右子树进行查询。
ll rangeQuery(int rt,int l,int r,int start,int end)
{
        if(start <= l && end >= r)
            return tree[rt];
        push_down(rt,l,r);
        int mid = (l + r) >> 1;
        ll res = 0;
        if(start <= mid) res += rangeQuery(rt << 1,l,mid,start,end);
        if(end >= mid + 1) res += rangeQuery(rt << 1|1,mid + 1,r,start,end);
        return res;
}

模板题解:

Acwing243

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const static int N = 100010;
typedef long long ll;
ll A[N],tree[4 * N],tag[4 * N];
void push_up(int rt)
{
    tree[rt] = tree[rt << 1] + tree[rt << 1|1];
}
void push_down(int rt,int l,int r)
{
    if(tag[rt] != 0)
    {
        int mid = (l + r) >> 1;
        ll lazy = tag[rt];
        tree[rt << 1] += (mid - l + 1) * lazy;
        tree[rt << 1|1] += (r - mid) * lazy;
        tag[rt << 1] += lazy;
        tag[rt << 1|1] += lazy;
        tag[rt] = 0;
    }
}
void build(int rt,int l,int r)
{
    if(l == r)
    {
        tree[rt] = A[r];
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1,l,mid);
    build(rt << 1|1,mid + 1,r);
    push_up(rt);
}
void updateRange(int rt,int l,int r,int start,int end,ll delta)
{
    if(start <= l && end >= r)
    {
        tree[rt] += (r - l + 1) * delta;
        tag[rt] += delta;
        return;
    }
    push_down(rt,l,r);
    int mid = (l + r) >> 1;
    if(start <= mid) updateRange(rt << 1,l,mid,start,end,delta);
    if(end >= mid + 1)updateRange(rt <<1|1,mid + 1,r,start,end,delta);
    push_up(rt);
}
ll rangeQuery(int rt,int l,int r,int start,int end)
{
    if(start <= l && end >= r)
        return tree[rt];
    push_down(rt,l,r);
    int mid = (l + r) >> 1;
    ll res = 0;
    if(start <= mid) 
        res += rangeQuery(rt << 1,l,mid,start,end);
    if(end >= mid + 1) 
        res += rangeQuery(rt << 1|1,mid + 1,r,start,end);
    return res;
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n ; i ++) 
        scanf("%lld",&A[i]);
    build(1,1,n);
    for(int i = 1; i <= m ; i ++)
    {
        char ch;
        cin >> ch;
        if(ch == 'Q')
        {
            int start,end;
            ll delta;
            scanf("%d %d",&start,&end);
            printf("%lld\n",rangeQuery(1,1,n,start,end));
        }else
        {
            int start,end;
            ll delta;
            scanf("%d %d %lld",&start,&end,&delta);
            updateRange(1,1,n,start,end,delta);
        }
    }
    return 0;
}

17 评论


用户头像
itdef   2019-12-01 13:44     回复

单点修改代码 好像掉了分号


用户头像
suiyo   2019-11-15 11:02     回复

%%%简单明了

用户头像
T-SHLoRk   2019-11-15 12:49     回复

因为太复杂的应用自己也不太会 只能把基础的写的详细一点啦


用户头像
mxyzptlk13   2019-08-30 00:56     回复

点赞啊。 顺便求问大佬动图是用什么怎么做的

用户头像
T-SHLoRk   2019-08-30 10:16     回复

这个图也是盗来的 (逃 不过做动图还是比较麻烦的感觉


用户头像
墨染空   2019-08-28 10:39     回复

棒棒哒

用户头像
T-SHLoRk   2019-08-28 10:50     回复

Acwing 是个好地方

用户头像
墨染空   2019-08-28 11:05    回复了 T-SHLoRk 的评论     回复

昂昂


用户头像
秦淮岸灯火阑珊   2019-08-28 10:13     回复

$\text{大佬棒棒哒!疯狂打call!}$

用户头像
T-SHLoRk   2019-08-28 10:51     回复

谢谢支持,不过为啥你的评论可以这么大

用户头像
秦淮岸灯火阑珊   2019-08-28 10:54    回复了 T-SHLoRk 的评论     回复

更好的书写体验,可以使用# Markdown+$\text{Latex}$

用户头像
T-SHLoRk   2019-08-28 10:56    回复了 秦淮岸灯火阑珊 的评论     回复

对了,有一个小问题就是Acwing的编辑器好像不允许一行有多个$$代表的行内公式?还是我操作有误。

用户头像
秦淮岸灯火阑珊   2019-08-28 11:18    回复了 T-SHLoRk 的评论     回复

这个我也不知道,我来帮你 @yxc

用户头像
yxc   2019-08-28 13:22    回复了 T-SHLoRk 的评论     回复

可以的,一对单个的美元符号是行内公式,可以写多个,比如 公式1 $n^2$、公式2 $2^n$、公式3 $\frac{n}{2}$。但公式内某些特殊字符需要转义,比如 '_', '*', '\'等。

用户头像
T-SHLoRk   2019-08-28 14:08    回复了 yxc 的评论     回复

是我蠢了 忘记*转义了

用户头像
yxc   2019-08-28 14:36    回复了 T-SHLoRk 的评论     回复

好的hh 加油~

用户头像
dys   9个月前    回复了 秦淮岸灯火阑珊 的评论     回复

怎么进行@操作?

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息