关于线段树

作者： 作者的头像   ZYzzz ,  2019-08-17 07:27:52 ,  所有人可见 ,  阅读 5143

60


63

其实吧，就是一个看完视频后的整理吧，线段树入门的知识，强烈推灯大！！！！
正月点灯笼这个up主真的好赞好赞！！！！
求赞！如果觉得我写的还不错的话，就点个赞吧！！！（可怜兮兮

笔记链接

视频链接

好了，y大佬说不能只有链接没有内容，那我就加点内容。其实只有链接是因为太懒

  • 假设我们现在拿到了一个非常大的数组，对于这个数组里面的数字要反复不断地做两个操作。

1.png

1、（$query$）随机在这个数组中选一个区间，求出这个区间所有数的和。

2.png

2、（$update$）不断地随机修改这个数组中的某一个值。

3.png

时间复杂度：

4.png

枚举：

  • 枚举$L$~$R$的每个数并累加。 $query:O(n)$

  • 找到要修改的数直接修改。 $update:O(1)$

如果$query$与$update$要做很多很多次，$query$的$O（n）$会被卡住，所以时间复杂度会非常慢。那么有没有办法把$query$的时间复杂度降成$O（1）$呢？其中一种方法如下：

先建立一个与$a$数组一样大的数组。

6.png

s[1]=a[1];s[2]=a[1]+a[2];s[3]=a[1]+a[2]+a[3];…;s[n]=a[1]+a[2]+a[3]+…+a[n]（在s数组中存入a的前缀和）

7.png

此时$a[L]+a[L+1]+…+a[R]=s[R]-s[L-1]$，$query$的时间复杂度降为$O(1)$。
但若要修改$a[k]$的值，随之也需修改$s[k],s[k+1],…,s[n]$的值，时间复杂度升为$O(n)$。

前缀和：

  • $query:O(1)$

  • $update:O(n)$

  • 我们发现，当我们想尽方法把其中一个操作的时间复杂度改成$O(1)$后，另一个操作的时间复杂度就会变为$O(n)$。当$query$与$update$的操作特别多时，不论用哪种方法，总体的时间复杂度都不会特别快。

  • 所以，我们将要讨论一种叫线段树的数据结构，它可以把这两个操作的时间复杂度平均一下，使得$query$和$update$的时间复杂度都落在$O(n log n)$上，从而增加整个算法的效率。

线段树

  • 假设我们拿到了如下长度为6的数组：

8.png

在构建线段树之前，我们先阐述线段树的性质：

1、线段树的每个节点都代表一个区间。

2、线段树具有唯一的根节点，代表的区间是整个统计范围，如$[1,N]$。

3、线段树的每个叶节点都代表一个长度为1的元区间$[x,x]$。

4、对于每个内部节点$[l,r]$，它的左子结点是$[l,mid]$，右子节点是$[mid+1,r]$，其中$mid=(l+r)/2$（向下取整）。

依照这个数组，我们构建如下线段树（结点的性质为$sum$）：

9.png

若我们要求$[2-5]$区间中数的和：

10.png

若我们要把$a[4]$改为$6$：

先一层一层找到目标节点修改，在依次向上修改当前节点的父节点。

1736745-20190816132553917-146290968.png

接下来的问题是：如何保存这棵线段树？

  • 用数组存储。

12.png

若我们要取$node$结点的左子结点（$left$）与右子节点（$right$），方法如下：

  • $left=2*node+1$
  • $right=2*ndoe+2$

举结点5为例（左子结点为节点11，右子节点为节点12）：

  • $left_5=2*5+1=11$
  • $right_5=2*5+2=12$

接下来给出建树的代码：

#include<bits/stdc++.h>
using namespace std; 

const int N = 1000;

int a[] = {1, 3, 5, 7, 9, 11};
int size = 6;
int tree[N] = {0};

//建立范围为a[start]~a[end] 
void build(int a[], int tree[], int node/*当前节点*/, int start, int end){
    //递归边界(即遇到叶子节点时) 
    if (start == end){
        //直接存储a数组中的值 
        tree[node] = a[start];
    } 

    else {
        //将建立的区间分成两半 
        int mid = (start + end) / 2;

        int left  = 2 * node + 1;//左子节点的下标 
        int right = 2 * node + 2;//右子节点的下标 

        //求出左子节点的值(即从节点left开始,建立范围为a[start]~a[mid])
        build(a, tree, left,  start, mid);
        //求出右子节点的值(即从节点right开始,建立范围为a[start]~a[mid])
        build(a, tree, right, mid+1, end);

        //当前节点的职位左子节点的值加上右子节点的值 
        tree[node] = tree[left] + tree[right];
    }
}

int main(){
    //从根节点(即节点0)开始建树,建树范围为a[0]~a[size-1]
    build(a, tree, 0, 0, size-1);

    for(int i = 0; i <= 14; i ++)
        printf("tree[%d] = %d\n", i, tree[i]);

    return 0;
}

运行结果：

13.PNG

$update$操作：

  • 确定需要改的分支，向下寻找需要修改的节点，再向上修改节点值。
  • 与建树的函数相比，$update$函数增加了两个参数$x$，$val$，即把$a[x]$改为$val$。

例：把$a[x]$改为$6$（代码实现）

11.png 

void update(int a[], int tree[], int node, int start, int end, int x, int val){
    //找到a[x],修改值 
    if (start == end){
        a[x] = val;
        tree[node] = val;
    }

    else {
        int mid = (start + end) / 2;

        int left  = 2 * node + 1;
        int right = 2 * node + 2;

        if (x >= start && x <= mid) {//如果x在左分支 
            update(a, tree, start, mid, x, val);
        }
        else {//如果x在右分支 
            update(a, tree, right, mid+1, end, x, val);
        }

        //向上更新值 
        tree[node] = tree[left] + tree[right]; 
    } 
}

在主函数中调用：
//把a[x]改成6
update(a, tree, 0, 0, size-1, 4, 6);

运行结果：

15.PNG

$query$操作：

  • 向下依次寻找包含在目标区间中的区间，并累加。
  • 与建树的函数相比，$query$函数增加了两个参数$L，R$，即把求a的区间$[L,R]$的和。

例：求$a[2]+a[3]+…+a[5]$的值（代码实现）

16.png 

int query(int a[], int tree[], int node, int start, int end, int L,int R){
    //若目标区间与当时区间没有重叠,结束递归返回0 
    if (start > R || end < L){
        return 0;
    }

    //若目标区间包含当时区间,直接返回节点值 
    else if (L <=start && end <= R){
        return tree[node];
    }

    else {
        int mid = (start + end) / 2;

        int left  = 2 * node + 1;
        int right = 2 * node + 2;

        //计算左边区间的值 
        int sum_left  = query(a, tree, left,  start, mid, L, R);
        //计算右边区间的值 
        int sum_right = query(a, tree, right, mid+1, end, L, R);

        //相加即为答案 
        return sum_left + sum_right;
    } 
}

在主函数中调用：
//求区间[2,5]的和
int ans = query(a, tree, 0, 0, size-1, 2, 5);
printf("ans = %d", ans);

运行结果：

17.PNG

最后，献上完整的代码：

#include<bits/stdc++.h>
using namespace std; 

const int N = 1000;

int a[] = {1, 3, 5, 7, 9, 11};
int size = 6;
int tree[N] = {0};

//建立范围为a[start]~a[end] 
void build(int a[], int tree[], int node/*当前节点*/, int start, int end){
    //递归边界(即遇到叶子节点时) 
    if (start == end) {
        //直接存储a数组中的值 
        tree[node] = a[start];
    } 

    else {
        //将建立的区间分成两半 
        int mid = (start + end) / 2;

        int left  = 2 * node + 1;//左子节点的下标 
        int right = 2 * node + 2;//右子节点的下标 

        //求出左子节点的值(即从节点left开始,建立范围为a[start]~a[mid])
        build(a, tree, left,  start, mid);
        //求出右子节点的值(即从节点right开始,建立范围为a[start]~a[mid])
        build(a, tree, right, mid+1, end);

        //当前节点的职位左子节点的值加上右子节点的值 
        tree[node] = tree[left] + tree[right];
    }
}

void update(int a[], int tree[], int node, int start, int end, int x, int val){
    //找到a[x],修改值 
    if (start == end){
        a[x] = val;
        tree[node] = val;
    }

    else {
        int mid = (start + end) / 2;

        int left  = 2 * node + 1;
        int right = 2 * node + 2;

        if (x >= start && x <= mid) {//如果x在左分支 
            update(a, tree, left, start, mid, x, val);
        }
        else {//如果x在右分支 
            update(a, tree, right, mid+1, end, x, val);
        }

        //向上更新值 
        tree[node] = tree[left] + tree[right]; 
    } 
}

//求a[L]~a[R]的区间和 
int query(int a[], int tree[], int node, int start, int end, int L,int R){
    //若目标区间与当时区间没有重叠,结束递归返回0 
    if (start > R || end < L){
        return 0;
    }

    //若目标区间包含当时区间,直接返回节点值 
    else if (L <=start && end <= R){
        return tree[node];
    }

    else {
        int mid = (start + end) / 2;

        int left  = 2 * node + 1;
        int right = 2 * node + 2;

        //计算左边区间的值 
        int sum_left  = query(a, tree, left,  start, mid, L, R);
        //计算右边区间的值 
        int sum_right = query(a, tree, right, mid+1, end, L, R);

        //相加即为答案 
        return sum_left + sum_right;
    } 
}

int main(){
    //从根节点(即节点0)开始建树,建树范围为a[0]~a[size-1]
    build(a, tree, 0, 0, size-1);

    for(int i = 0; i <= 14; i ++)
        printf("tree[%d] = %d\n", i, tree[i]);
    printf("\n");    

    //把a[x]改成6
    update(a, tree, 0, 0, size-1, 4, 6); 

    for(int i = 0; i <= 14; i ++)
        printf("tree[%d] = %d\n", i, tree[i]);
    printf("\n");

    //求区间[2,5]的和
    int ans = query(a, tree, 0, 0, size-1, 2, 5);
    printf("ans = %d", ans); 

    return 0;
}

运行结果：

18.PNG

17 评论

用户头像
无为自在   2022-02-12 08:10         踩      回复

写的不错，为什么赞数这么少？

用户头像
Conan15   2022-02-05 21:36         踩      回复

赞！（必须的）

用户头像
Karshey   2022-01-10 16:13         踩      回复

博主，query的代码的值是29，不是32，这是update之后的答案

用户头像
Karshey   2022-01-10 15:56         踩      回复

博主，update函数中递归地更新左子树里少了一个参数：update(a, tree, start, mid, x, val);

用户头像
lihua777   2022-05-26 16:48         踩      回复

顶一下

用户头像
Karshey   2022-01-10 15:30         踩      回复

%%%%%%%%%%%%

用户头像
Conan15   2022-01-04 22:00         踩      回复

tql

用户头像
TodayMagic   2021-08-15 00:17         踩      回复

灯神太强了，很早就关注了，声音超级好听

用户头像
陈依劼   2021-07-24 10:35         踩      回复

dddd

用户头像
Moon_light   2020-11-10 11:26         踩      回复

赞

用户头像
马丁   2019-12-19 15:58         踩      回复

在单独那个update函数中，处理左边的时候，您好像写掉了一个参数~~~

用户头像
itdef   2019-11-29 15:59         踩      回复

点赞！！

用户头像
马丁   2019-08-25 16:42         踩      回复

真棒谢谢了

用户头像
吕德华   2019-08-23 22:07         踩      回复

厉害

用户头像
Live   2019-08-21 08:49         踩      回复

666

用户头像
墨染空   2019-08-18 12:55         踩      回复

棒啊

用户头像
銘权   2019-08-17 11:46         踩      回复

666