0


线段树详解(含代码实现经过测试)

1.线段树介绍

什么是线段树?线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。 [1]

对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树,最后的子节点数目为N,即整个线段区间的长度。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。-----来自百度。

2.线段树原理及其实现

线段树主要是把一段大区间 平均地划分 成两段小区间进行维护,再用小区间的值来更新大区间。这样既能保证正确性,又能使时间保持在 log ⁡ 级别(因为这棵线段树是平衡的)。也就是说一个[L,R]区间会被划分为两个区间分别是[L,(L+R)/2]和[(L+R)/2+1,R]这两个小区间。然后再递归下去分直达L=R。
下图就是一棵 [ 1 , 10 ] 的线段树的分解过程(相同颜色的节点在同一层)如图所示:

我们可以发现,这棵线段树的最大深度不超过[ log2 ( n − 1 ) ]+2.

1.实现的基本框架

我们如何实现这种结构呢?难道真的是用二叉树吗?当然不是我们可以用我们之前学过的堆来实现这种结构。本文中使用满二叉树来实现线段树,可能有老铁会问了如果给定数组的长度不是2的某次方时又该怎么办了?在这里如果他不是满二叉树我们给他补成满二叉树。

2.空间的计算

实现线代树我采用了大根堆来实现,这是因为大根堆是一个完全二叉树因此我们可以使用数组来表示,只不过当数组的长度不是2^i时我们需要补齐。如图所示

在这里插入图片描述

现在我们来估计一下大概需要多少空间。假设区间有n个元素,对于满二叉树来说:

1.第一层到第k层一共有2^k-1个节点(约有2^k)个节点

2.最后一层共有2^k-1个节点

我们可以得出:满二叉树中最后一层节点的个数大约是前面节点的个数之和

1.如果n=2^i则需要2n个节点

2.如果n=2^i+1时此时情况最坏需要4*n个节点(估计值)

3.表示方式:

在这里我们我们数组的下标是从1开始,这是为了让左右孩子的下标能够使用位运算来进而提高效率。如果一个父亲节点对应的索引为i那么则有下面公式:

1.左孩子=2*i;

2.右孩子=2*i+1

用位运算来表示为:

1.左孩子=i<<1;

2.右孩子=i<<1|1;

4.线段树的构建对应代码:

#pragma once 
#include<iostream>
#include<vector>
using std::vector;
using std::cout;
using std::endl;
class SegmentTree {
public:
    SegmentTree(const vector<int>& origin) {
        MAXN = origin.size() + 1;
        arr.resize(MAXN);
        for (int i = 1; i < MAXN; i++) {//arr[0]不用从arr[1]开始
            arr[i] = origin[i - 1];
        }
        sum.resize(MAXN << 2);//相当与MAXN*4;用来支持脑补概念中,某一个范围的累加和信息
        lazy.resize(MAXN << 2);//用来支持脑补概念中,某一个没有在往下的累加和标记
        change.resize(MAXN << 2);
        update.resize(MAXN << 2);

    }
    void build(int l, int r, int rt) {
        if (l == r) {//只有一个数
            sum[rt] = arr[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, rt << 1);
        build(mid + 1, r, (rt << 1) | 1);//相当于2*rt+1;                                                                                                                                                                                                 
        pushUp(rt);//计算玩向上返回累加和
    };
    void pushUp(int rt) {
        sum[rt] = sum[rt << 1] + sum[(rt << 1) | 1];//rt<<1|1相当于2*rt+1;
    }
private:
    int MAXN;
    vector<int>arr;//arr维护的是原序列信息从0开始,但是在这里arr从1开始
    vector<int>sum;//模拟线段树维护区间和
    vector<int>lazy;//为累加懒惰信息标记
    vector<int>change;//对应位置的更新值
    vector<bool>update;//为更新懒惰标记
};

2.1区间修改

修改大概可以分为两步:

1.找到这段区间。

2.修改这一区间所有的点

大致流程如下:

1.如果当前区间完全被覆盖在目标区间里将这个区间sum数组的的位置加上(r-l+1)*C

2.如果没有完全覆盖则先下传懒标记

3.如果这个区间的左孩子和目标区间有交集,那么就递归给左孩子分配任务

4.如果这个区间的右孩子和目标区间有交集,则递归分配任务给右孩子。

懒更新:

在线段树中为了提高效率引入了懒跟新:

1.标记的含义:区间已经被更新过,但是子区间没有被更新过,被更新的信息是什么(区间求和只用记录有没有被访问过,而区间的四则运算等多种操作的问题则要记录是那一种操作)。
这里再引入两个很重要的东西:相对标记和绝对标记

相对标记:指的是可以共存的标记,且打标记的顺序与答案无关,即标记可以叠加。 比如说给一段区间中的所有数字都 + a ,我们就可以把标记叠加一下,比如上一次打了一个 加2 的标记,这一次要给这一段区间 +5 ,那么就把 + 2 的标记变成 + 5

绝对标记:

是指不可以共存的标记,每一次都要先把标记下传,再给当前节点打上新的标记。这些标记不能改变次序,否则会出错。 比如说给一段区间的数字重新赋值,或是给一段区间进行多种操作。

例如:

有了 懒惰标记 这种神奇的东西,我们区间修改时就可以偷一下懒,先修改当前节点,然后直接把信息挂在节点上就可以了!
如下面这棵线段树,当我们要修改区间 [ 1 , 4 ] [1,4][1,4] ,将元素赋值为 1 时,我们可以先找到所有的整个区间都要被修改的节点,显然是储存区间 [1,3] 和 [4,4] 的这两个节点。我们就可以先把 [1,3] 的 sum 改为(3−1+1)∗1=3 ,把 [ 4 , 4 ] 的 sum 改为 (1-1+1)*1=1 ,然后给它们打上值为 1 的懒惰标记,然后就可以了。
这样一来,我们每一次修改区间时只要找到目标区间就可以了,不用再向下递归到叶节点,从而提高了效率。

下传标记
碰到 相对标记 这种容易欺负的小朋友,我们只用打一下懒惰标记就可以了。
但是,遇到 绝对标记 ,或是下文提到的 区间查询 ,简单地打上懒惰标记就明显GG了。毕竟, 懒惰标记 只是简单地在节点挂上一个信息而已,遇到复杂的情况可是不行的啊!
于是,懒惰标记的 下传操作 就诞生了。
顾名思义, 下传标记 就是把一个节点的懒惰标记传给它的左右儿子,再把该节点的懒惰标记删去。
我们先来回顾一下标记的含义:

标记的含义:本区间已经被更新过了,但是子区间却没有被更新过,被更新的信息是什么。

显然,父区间是包含子区间的,也就是对于父区间的标记和子区间是有联系的。在大多数情况下,父区间和子区间的标记是 相同的 。因此,我们可以由父区间的标记推算出子区间应当是什么标记。
注意:以下所说的问题都是指区间赋值,除非有什么特别的申明。
如果要给一个节点中的所有元素重新赋值为 x ,那么它的儿子也必定要被赋值成 x 。所以,我们直接在子节点处修改 sumsum 值,再把子节点的标记改变一下就可以了(由于区间赋值要用 绝对标记 ,因此当子节点已经有标记时,要先下传子节点的标记,再下传该节点的标记。但是区间赋值会覆盖掉子节点的值,因此在这个问题中,直接修改标记就可以了)

下面是在对应区间加C的代码:

void pushUp(int rt) {//更新父亲的累加和
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
    void pushDown(int rt, int ln, int rn) {
        if (update[rt]) {//update方法需要使用
            update[rt << 1] = true;//往下发
            update[rt << 1|1] = true;
            change[rt << 1] = change[rt];
            change[rt << 1 | 1] = change[rt];
            lazy[rt << 1] = 0;//清空左右孩子的懒数组
            lazy[rt << 1 | 1] = 0;
            sum[rt << 1] = change[rt] * ln;//左孩子总和
            sum[rt << 1 | 1] = change[rt] * rn;//右孩子总和
            update[rt] = false;//当前位置已经下发改成false;
        }
        if (lazy[rt]) {
            lazy[rt << 1] += lazy[rt];
            lazy[(rt << 1) | 1] += lazy[rt];
            sum[rt << 1] += lazy[rt] * ln;
            sum[rt << 1 | 1] += lazy[rt] * rn;
            lazy[rt] = 0;
        }
    }
    void add(int L, int R, int C, int l, int r, int rt) {//L和R表示实际要修改的范围 l到r表示实际的范围 rt 表示这个范围
        //的信息我去数组中那个位置去找
        if (L <= l && r <= R) {//懒住
            //修改相关信息
            sum[rt] += C * (r - l + 1);
            lazy[rt] += C;
            return;
        }
        //当前任务躲不掉,无法懒更新,要往下发
        int mid = (l + r) >> 1;
        pushDown(rt, mid - l + 1, r - mid);//先将懒信息下发给左右孩子
        if (L <= mid) {//左孩子需要下发任务
            add(L, R, C, l, mid, rt << 1);
        }
        if (R > mid) {//右孩子需要下发任务
            add(L, R, C, mid + 1, r, rt << 1 | 1);
        }
        pushUp(rt);//更新父亲的累加和
    }

对于add中的参数解释:

1.L,R代表要修改的区间范围

2.l,r 代表实际的范围

3.C要加的值

4.rt表示l到r位置对于的信息在数组的那个位置去拿

对于pushdown方法的解释:

1.包括了update方法的和add的懒操作

2.2区间查询

区间查询的和add基本类似:

1.如果当前区间完全被覆盖在目标区间里将对于sum位置的数据返回

2.如果没有完全覆盖则先下传懒标记

3.如果这个区间的左孩子和目标区间有交集,那么就递归给左孩子分配任务

4.如果这个区间的右孩子和目标区间有交集,则递归分配任务给右孩子。

对应代码:

long long query(int L, int R, int l, int r, int rt) {
        if (L <= l && r <= R) {//刚好覆盖这个区间直接在这里面拿值
            return sum[rt];
        }
        int mid = (l + r) >> 1;
        pushDown(rt, mid - l + 1, r - mid);//先将懒信息分配给左右孩子
        long long ans = 0;
        if (L <= mid) {
            ans+=query(L, R, l, mid, rt << 1);
        }
        if (R > mid) {
            ans += query(L, R, mid + 1, r, rt << 1 | 1);
        }
        return ans;
    }

2.3区间更新

区间更新和区间的修改也是基本类似但也所不同

1.如果某一个区间被设置成对应的数那么该区间的lazy数组中的数据全部置为0

2.如果当前区间懒不住要先下发懒信息给左右孩子在分配任务

具体请看代码:

void Update(int L, int R, int C, int l, int r, int rt) {
        if (L <= l && r <= R) {
            update[rt] = true;//标记已经更新过
            change[rt] = C;
            sum[rt] = C * (r - l + 1);
            lazy[rt] = 0;//清空
            return;
         }
        //当前任务躲不掉,无法懒更新,要往下发
        int mid = (l + r) >> 1;
        pushDown(rt, mid - l + 1, r - mid);
        if (L <= mid) {
            Update(L, R, C, l, mid, rt << 1);
        }
        if (R > mid) {
            Update(L, R, C, mid + 1, r, rt << 1 | 1);
        }
        pushUp(rt);//更新父亲节点的累加和
    }

对应总代码:

#pragma once 
#include<iostream>
#include<vector>
using std::vector;
using std::cout;
using std::endl;
class SegmentTree {
public:
    SegmentTree(const vector<int>& origin) {
        MAXN = origin.size() + 1;
        arr.resize(MAXN);
        for (int i = 1; i < MAXN; i++) {//arr[0]不用从arr[1]开始
            arr[i] = origin[i - 1];
        }
        sum.resize(MAXN << 2);//相当与MAXN*4;用来支持脑补概念中,某一个范围的累加和信息
        lazy.resize(MAXN << 2);//用来支持脑补概念中,某一个没有在往下的累加和标记
        change.resize(MAXN << 2);
        update.resize(MAXN << 2);

    }
    void build(int l, int r, int rt) {
        if (l == r) {
            sum[rt] = arr[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, rt << 1);
        build(mid + 1, r, rt << 1 | 1);//相当于2*rt+1;                                                                                                                                                                                                 
        pushUp(rt);
    };
    void pushUp(int rt) {//更新父亲的累加和
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
    void pushDown(int rt, int ln, int rn) {
        if (update[rt]) {//update方法需要使用
            update[rt << 1] = true;//往下发
            update[rt << 1|1] = true;
            change[rt << 1] = change[rt];
            change[rt << 1 | 1] = change[rt];
            lazy[rt << 1] = 0;//清空左右孩子的懒数组
            lazy[rt << 1 | 1] = 0;
            sum[rt << 1] = change[rt] * ln;//左孩子总和
            sum[rt << 1 | 1] = change[rt] * rn;//右孩子总和
            update[rt] = false;//当前位置已经下发改成false;
        }
        if (lazy[rt]) {//下发懒信息
            lazy[rt << 1] += lazy[rt];
            lazy[(rt << 1) | 1] += lazy[rt];
            sum[rt << 1] += lazy[rt] * ln;
            sum[rt << 1 | 1] += lazy[rt] * rn;
            lazy[rt] = 0;
        }
    }
    void add(int L, int R, int C, int l, int r, int rt) {//L和R表示实际要修改的范围 l到r表示实际的范围 rt 表示这个范围
        //的信息我去数组中那个位置去找
        if (L <= l && r <= R) {//懒住
            //修改相关信息
            sum[rt] += C * (r - l + 1);
            lazy[rt] += C;
            return;
        }
        //当前任务躲不掉,无法懒更新,要往下发
        int mid = (l + r) >> 1;
        pushDown(rt, mid - l + 1, r - mid);//先将懒信息下发给左右孩子
        if (L <= mid) {//左孩子需要下发任务
            add(L, R, C, l, mid, rt << 1);
        }
        if (R > mid) {//右孩子需要下发任务
            add(L, R, C, mid + 1, r, rt << 1 | 1);
        }
        pushUp(rt);//更新父亲的累加和
    }
    void Update(int L, int R, int C, int l, int r, int rt) {
        if (L <= l && r <= R) {
            update[rt] = true;//标记已经更新过
            change[rt] = C;
            sum[rt] = C * (r - l + 1);
            lazy[rt] = 0;//清空
            return;
         }
        //当前任务躲不掉,无法懒更新,要往下发
        int mid = (l + r) >> 1;
        pushDown(rt, mid - l + 1, r - mid);
        if (L <= mid) {
            Update(L, R, C, l, mid, rt << 1);
        }
        if (R > mid) {
            Update(L, R, C, mid + 1, r, rt << 1 | 1);
        }
        pushUp(rt);//更新父亲节点的累加和
    }

    
    long long query(int L, int R, int l, int r, int rt) {
        if (L <= l && r <= R) {//刚好覆盖这个区间直接在这里面拿值
            return sum[rt];
        }
        int mid = (l + r) >> 1;
        pushDown(rt, mid - l + 1, r - mid);//先将懒信息分配给左右孩子
        long long ans = 0;
        if (L <= mid) {
            ans+=query(L, R, l, mid, rt << 1);
        }
        if (R > mid) {
            ans += query(L, R, mid + 1, r, rt << 1 | 1);
        }
        return ans;
    }
private:
    int MAXN;
    vector<int>arr;//arr维护的是原序列信息从0开始,但是在这里arr从1开始
    vector<int>sum;//模拟线段树维护区间和
    vector<int>lazy;//为累加懒惰信息标记
    vector<int>change;//对应位置的更新值
    vector<bool>update;//为更新懒惰标记
};

上述代码博主经过测试基本正确如有错误请在评论区留言!

标签: 算法 数据结构

本文转载自: https://blog.csdn.net/qq_56999918/article/details/122887547
版权归原作者 一个山里的少年 所有, 如有侵权,请联系我们删除。

“线段树详解(含代码实现经过测试)”的评论:

还没有评论