【算法&数据结构体系篇class31】：线段树

系统管理员 2024-03-23 16:22 100阅读 0赞

> 1，一种支持范围整体修改和范围整体查询的数据结构
> 
> 2，解决的问题范畴：
> 
> **大范围信息可以只由左、右两侧信息加工出，**
> 
> **而不必遍历左右两个子范围的具体状况**

### 一、线段树实例一 ###

> 给定一个数组arr，用户希望你实现如下三个方法
> 
> 1）void add(int L, int R, int V) : 让数组arr\[L…R\]上每个数都加上V
> 
> 2）void update(int L, int R, int V) : 让数组arr\[L…R\]上每个数都变成V
> 
> 3）int sum(int L, int R) :让返回arr\[L…R\]这个范围整体的累加和
> 
> **怎么让这三个方法，时间复杂度都是O(logN)**

package class31;
    
    import sun.reflect.generics.tree.Tree;
    
    /**
     * 线段树
     *
     * 1，一种支持范围整体修改和范围整体查询的数据结构
     *
     * 2，解决的问题范畴：
     * 大范围信息可以只由左、右两侧信息加工出，
     * 而不必遍历左右两个子范围的具体状况
     *
     *
     * 线段树实例一
     *
     * 给定一个数组arr，用户希望你实现如下三个方法
     * 1）void add(int L, int R, int V) :  让数组arr[L…R]上每个数都加上V
     * 2）void update(int L, int R, int V) :  让数组arr[L…R]上每个数都变成V
     * 3）int sum(int L, int R) :让返回arr[L…R]这个范围整体的累加和
     * 怎么让这三个方法，时间复杂度都是O(logN)
     */
    public class SegmentTree {
        public static class sTree{
            // arr[]为原序列的信息从0开始，但在arr里是从1开始的
            // sum[]模拟线段树维护区间和
            // lazy[]为累加和懒惰标记
            // change[]为更新的值
            // update[]为更新慵懒标记
            private int maxn;
            private int[] arr;
            private int[] sum;
            private int[] lazy;
            private int[] change;
            private boolean[] update;
    
            public sTree(int[] origin){
                maxn = origin.length + 1;
                arr = new int[maxn];  // arr[0] 不用 从1开始使用  所以长度+1
    
                //注意四个数组 长度是原数组长度的4倍 右移2位   因为根据我们将数组转换成一个线段树结构 我们能发现长度大约是2N+2N的长度
                //比如[3,2,1,0,3]     对应的线段树结构：
                /**
                 *                                         1: 1-5之和9
                 *                           2： 1-2之和5              3： 3-5之和4
                 *                   4： 1-1之和3    5： 2-2之和2   6： 3-3之和1       7：4-5之和3
                 *           8：  0    9: 0      10: 0    11:0     12:0     13:0     14: 4-4之和0   15： 5-5之和3
                 *
                 *
                 *           其就是sum数组 树结构   转换数组形式  1-15对应的就是数组值，i 索引的左右子节点 i*2  i*2+1
                 *           其长度大致分析 最后一行是大约2N 个 前面几行也是与最后一行大小差不多一致  所以长度4N足够用
                 */
    
                sum = new int[maxn << 2];    // 累加数组 某一个范围的累加和信息
                lazy = new int[maxn << 2];   // 懒加数组 某一个范围还沒有往下傳遞的纍加任務
                change = new int[maxn << 2];  //更新数组 某一个范围有没有更新操作的任务
                update = new boolean[maxn << 2]; //更新判断 某一个范围更新任务，是否更新 因为这里change 默认0  也可以表示修改为0 所以避免歧义我们通过布尔数组来判定
    
                for(int i = 1; i < maxn; i++){  //将源构造的数组 入参后 添加到arr数组中 从1索引开始
                    arr[i] = origin[i-1];
                }
            }
    
    
            // 在初始化阶段，先把sum数组，填好
            // 在arr[l~r]范围上，去build，1~N，
            // rt : 这个范围在sum中的下标
            public void build(int l, int r, int rt){
                //base case: 当前边界相等时值只有一个 那么sum求和数组就是该值本身
                if(l == r){
                    sum[rt] = sum[l];
                    return;
                }
                //如果不止一个值 那么就分左右区间去递归求值
                int mid = (l + r) >> 1; //得出区间的中间值
                build(l,mid,rt << 1);    //左区间去递归 同时rt也来到左节点
                build(mid+1,r,rt << 1 | 1);   //右区间去递归 同时rt也来到右节点
                pushUp(rt);
            }
    
    
            //添加刷新累加数组   rt参数表示数组下标
            public void pushUp(int rt){
                //rt 和 等于 左子节点 rt*2下标  + 右子节点 rt*2 +1下标 两者之和
                sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
            }
    
    
            // 下发任务  之前的，所有懒增加，和懒更新，从父范围，发给左右两个子范围
            // 分发策略是什么
            // ln表示左子树元素结点个数，rn表示右子树结点个数
            public void pushDown(int rt, int ln, int rn){
                //注意 需要先判断 懒更新 因为更新 就需要把我们lazy左右子节点懒数组数据需要同步清空  接着再去刷新下层的求和数组
                if(update[rt]){   //当前索引需要更新
                    update[rt << 1] = true;        //刷新左节点的更新状态
                    update[rt << 1 | 1] = true;   //刷新右节点的更新状态
                    change[rt << 1] = change[rt];      //将当前修改下 都下放到左右子修改数组中
                    change[rt << 1 | 1] = change[rt];
                    lazy[rt << 1] = 0;                 //因为是更新操作 是把rt 这个区间的全部值都修改为当前change[rt] 所以之前的懒加数组就需要作废清空
                    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] != 0){  //当前索引需要累加
                    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;                     //累加完之和 将懒数组清空
                }
            }
    
            // L-R  区间  添加C 的 添加任务
            //l r是数组的左右边界 rt是该边界对应的当前位置
            public  void add(int L, int R, int C, int l, int r, int rt){
                //任务区间包含了 当前的数组范围  比如 1-100 添加3   当前在 2-50 区间 是完全包含的 表示l,r区间都是要添加3  懒执行
                if(L <= l && R >= r){
                    //直接刷新求和数组 一共l-r+1个数 每个数加C    懒数组累加当前区间增加的C值
                    sum[rt] += C*(r-l+1);
                    lazy[rt] += C;
                    return;
                }
    
                //任务区间没有包含 比如 20-100 添加3    当前在 10-150 区间 部分包含 需要分左右两边来执行
                //然后先将当前的懒数组 有存在需要 刷新更新 刷新添加的操作 先下发了  避免影响当前任务
                int mid = (l + r) >> 1;
                //刷新当前lazy[] update[] 的懒数组操作  传递当前的位置rt 以及左右区间的个数
                pushDown(rt, mid - l + 1, r - mid);
    
                //然后开始当前的任务操作 如果L<= mid 说明需要递归左边界
                if(L <= mid){
                    //递归参数  左区间的位置 刷新来到rt*2 左区间为l,mid
                    add(L,R,C,l,mid,rt <<1);
                }
                if(R > mid){
                    //右边界R大于中间值 说明mid,r区间就需要进行添加操作
                    add(L,R,C,mid+1,r,rt << 1|1);
                }
                //最后合并左右区间的值 刷新当前位置的sum数组
                pushUp(rt);
            }
    
    
            //L-R 区间 修改为C 的 修改任务
            //l r是数组的左右边界 rt是该边界对应的当前位置
            public void update(int L, int R, int C, int l, int r, int rt){
                //任务区间包含了当前数组范围 那么就是直接刷新 change update sum数组    懒执行
                if(L <= l && R >= r){
                    change[rt] = C;      //修改值赋值C
                    update[rt] = true;   //修改值状态修改true
                    sum[rt] = C*(r-l+1);  //求和数组 刷新
                    lazy[rt] = 0;         //同时需要将累加的懒数组清空
                    return;
                }
    
                //任务不包含 分左右区间
                //先刷新当前的懒数组的修改 添加操作
                int mid = (l + r) >>1;
                pushDown(rt,mid-l+1,r-mid);
    
                //判断L边界是否小于等于mid 如果是说明当前l,mid 存在数值需要进行修改操作
                if(L <= mid){
                    update(L,R,C,l,mid,rt << 1);
                }
                //R边界大于mid 就需要将右区间数组进行修改操作
                if(R > mid){
                    update(L,R,C,mid+1,r,rt << 1 | 1);
                }
    
                //再将两左右区间的值得到 刷新当前的sum数组
                pushUp(rt);
            }
    
            //L-R 区间查询累加和
           public long query(int L, int R, int l, int r, int rt){
                //如果查询区间 就包含了l,r 那么我们就直接返回 累加和就是当前l,r区间和
               if(L <= l && R >= r){
                   return sum[rt];
               }
    
               //不包含，那么就分左右区间进行操作
               int mid = (l + r) >> 1;
               //先将当前的懒数组操作 lazy change 的添加 修改操作进行下发任务先
               pushDown(rt,mid-l+1,r-mid);
               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;
           }
        }
    
    
        public static class Right {
            public int[] arr;
    
            public Right(int[] origin) {
                arr = new int[origin.length + 1];
                for (int i = 0; i < origin.length; i++) {
                    arr[i + 1] = origin[i];
                }
            }
    
            public void update(int L, int R, int C) {
                for (int i = L; i <= R; i++) {
                    arr[i] = C;
                }
            }
    
            public void add(int L, int R, int C) {
                for (int i = L; i <= R; i++) {
                    arr[i] += C;
                }
            }
    
            public long query(int L, int R) {
                long ans = 0;
                for (int i = L; i <= R; i++) {
                    ans += arr[i];
                }
                return ans;
            }
    
        }
    
        public static int[] genarateRandomArray(int len, int max) {
            int size = (int) (Math.random() * len) + 1;
            int[] origin = new int[size];
            for (int i = 0; i < size; i++) {
                origin[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
            }
            return origin;
        }
    
        public static boolean test() {
            int len = 100;
            int max = 1000;
            int testTimes = 5000;
            int addOrUpdateTimes = 1000;
            int queryTimes = 500;
            for (int i = 0; i < testTimes; i++) {
                int[] origin = genarateRandomArray(len, max);
                sTree seg = new sTree(origin);
                int S = 1;
                int N = origin.length;
                int root = 1;
                seg.build(S, N, root);
                Right rig = new Right(origin);
                for (int j = 0; j < addOrUpdateTimes; j++) {
                    int num1 = (int) (Math.random() * N) + 1;
                    int num2 = (int) (Math.random() * N) + 1;
                    int L = Math.min(num1, num2);
                    int R = Math.max(num1, num2);
                    int C = (int) (Math.random() * max) - (int) (Math.random() * max);
                    if (Math.random() < 0.5) {
                        seg.add(L, R, C, S, N, root);
                        rig.add(L, R, C);
                    } else {
                        seg.update(L, R, C, S, N, root);
                        rig.update(L, R, C);
                    }
                }
                for (int k = 0; k < queryTimes; k++) {
                    int num1 = (int) (Math.random() * N) + 1;
                    int num2 = (int) (Math.random() * N) + 1;
                    int L = Math.min(num1, num2);
                    int R = Math.max(num1, num2);
                    long ans1 = seg.query(L, R, S, N, root);
                    long ans2 = rig.query(L, R);
                    if (ans1 != ans2) {
                        return false;
                    }
                }
            }
            return true;
        }
    
        public static void main(String[] args) {
            int[] origin = { 2, 1, 1, 2, 3, 4, 5 };
            sTree seg = new sTree(origin);
            int S = 1; // 整个区间的开始位置，规定从1开始，不从0开始 -> 固定
            int N = origin.length; // 整个区间的结束位置，规定能到N，不是N-1 -> 固定
            int root = 1; // 整棵树的头节点位置，规定是1，不是0 -> 固定
            int L = 2; // 操作区间的开始位置 -> 可变
            int R = 5; // 操作区间的结束位置 -> 可变
            int C = 4; // 要加的数字或者要更新的数字 -> 可变
            // 区间生成，必须在[S,N]整个范围上build
            seg.build(S, N, root);
            // 区间修改，可以改变L、R和C的值，其他值不可改变
            seg.add(L, R, C, S, N, root);
            // 区间更新，可以改变L、R和C的值，其他值不可改变
            seg.update(L, R, C, S, N, root);
            // 区间查询，可以改变L和R的值，其他值不可改变
            long sum = seg.query(L, R, S, N, root);
            System.out.println(sum);
    
            System.out.println("对数器测试开始...");
            System.out.println("测试结果 : " + (test() ? "通过" : "未通过"));
    
        }
    }

### 二、线段树实例二 ###

> 想象一下标准的俄罗斯方块游戏，X轴是积木最终下落到底的轴线
> 
> 下面是这个游戏的简化版：
> 
> 1）只会下落正方形积木
> 
> 2）\[a,b\] \-> 代表一个边长为b的正方形积木，积木左边缘沿着X = a这条线从上方掉落
> 
> 3）认为整个X轴都可能接住积木，也就是说简化版游戏是没有整体的左右边界的
> 
> 4）没有整体的左右边界，所以简化版游戏不会消除积木，因为不会有哪一层被填满。
> 
> 给定一个N\*2的二维数组matrix，可以代表N个积木依次掉落，
> 
> 返回每一次掉落之后的最大高度

[699.掉落的方块][699.]

![4108dc0d215b4d44879afd0ad0b16753.png][]![6086309cb16b479cbc41d8d6e0775b80.png][]

package class31;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.TreeSet;
    
    /**线段树实例二:https://leetcode.cn/problems/falling-squares/
     * 想象一下标准的俄罗斯方块游戏，X轴是积木最终下落到底的轴线
     * 下面是这个游戏的简化版：
     * 1）只会下落正方形积木
     * 2）[a,b] -> 代表一个边长为b的正方形积木，积木左边缘沿着X = a这条线从上方掉落
     * 3）认为整个X轴都可能接住积木，也就是说简化版游戏是没有整体的左右边界的
     * 4）没有整体的左右边界，所以简化版游戏不会消除积木，因为不会有哪一层被填满。
     *
     * 给定一个N*2的二维数组matrix，可以代表N个积木依次掉落，
     * 返回每一次掉落之后的最大高度
     */
    public class FallingSquares {
    
        //定义线段树结构类  根据题意 我们通过 最大值线段数据 以及更新数组 来进行完善结构
        public static class SegmentTree{
            private int[] max;      //线段区间维护最大数组
            private int[] change;   //修改数组保存修改值
            private boolean[] update;   //标记修改数组是否修改
    
            public SegmentTree(int size){
                int n = size+1;     //初始化 数组场地是 入参大小+1  因为线段数组都是从1开始的 规定
    
                //为三个数组赋值4N长度 证明：转换成线段数组 原长度数组的4N 就足够使用了
                //比如[3,2,1,0,3]     对应的线段树结构：
                /**
                 *                                         1: 1-5之和9
                 *                           2： 1-2之和5              3： 3-5之和4
                 *                   4： 1-1之和3    5： 2-2之和2   6： 3-3之和1       7：4-5之和3
                 *           8：  0    9: 0      10: 0    11:0     12:0     13:0     14: 4-4之和0   15： 5-5之和3
                 *
                 *
                 *           其就是sum数组 树结构   转换数组形式  1-15对应的就是数组值，i 索引的左右子节点 i*2  i*2+1
                 *           其长度大致分析 最后一行是大约2N 个 前面几行也是与最后一行大小差不多一致  所以长度4N足够用
                 */
                max = new int[n << 2];
                change = new int[n << 2];
                update = new boolean[n << 2];
            }
    
            //刷新max 最大线段数组值 判断左右子节点较大值即为当前位置的值
            public void pushUp(int rt){
                //当前位置rt 其表示某个范围 假设是 1，100   max[rt]表示其区间数值最大值
                //根据线段树结构 rt 是拆分了 左节点 rt *2  以及 右节点 rt*2+1  两个节点max数组值得较大值
                max[rt] = Math.max(max[rt << 1], max[rt << 1 | 1]);
            }
    
            //刷新当前已有懒加载的数组  最大值change值任务下发 左右子节点    ln rn  ln表示左子树元素结点个数，rn表示右子树结点个数省去参数
            public void pushDown(int rt){
                //如果当前update数组标记存在着修改值，那么就进行刷新
                if(update[rt]){
                    update[rt << 1] = true;          //修改左右子节点的标记
                    update[rt << 1 | 1] = true;
                    change[rt << 1] = change[rt];    //刷新左右子节点的修改数组值
                    change[rt << 1 | 1] = change[rt];
                    max[rt << 1] = change[rt];
                    max[rt << 1 | 1] = change[rt];
                    update[rt] = false;
    
                }
            }
    
            //更新操作
            //L-R 区间 修改为C 的 修改任务
            //l r是数组的左右边界 rt是该边界对应的当前位置
            public  void update(int L, int R, int C, int l, int r, int rt){
                //如果任务L R包住了当前数组范围lr  L..l..r..R 那么 就表示整个max[rt]需要刷新
                if(L <= l && R >= r){
                    update[rt] = true;   //刷新该位置的标记
                    change[rt] = C;         //修改数组保存当前修改值
                    max[rt] = C;           //最大值线段数组修改当前C值
                    return;
                }
    
                //如果没有包住 l..L...R..r  或者其他形式 的包含 交集形式 那么就是需要分左右区间来执行
                //在此之前，我们需要先刷新这个懒加载数组 通过pushDown将当前存在右需要下发更新修改的值先进行修改
                pushDown(rt);
                int mid = (l + r) >> 1;
                //修改任务L边界 小于等于Mid  那么数组的左节点 rt<<1 其区间l,mid就需要修改
                if(L <= mid){
                    update(L, R, C, l, mid,rt<<1);
                }
                //修改任务R边界 大于Mid  那么数组的右节点 rt<<1|1 其区间mid+1，r就需要修改
                if(R > mid){
                    update(L, R, C, mid+1, r,rt<<1|1);
                }
                //最后对左右区间 进行一个比较 刷新当前rt位置的最大值
                pushUp(rt);
            }
    
            //查询操作
            //L-R 区间查询最高高度
            public int query(int L, int R, int l, int r, int rt){
                //任务包含 则直接返回当前max[rt]值 表示该区间的最大值
                if(L <= l && R >= r){
                    return max[rt];
                }
    
                //没有包含，那么分左右区间进行
                //先执行懒加载函数 将存有change数组 的更新操作进行下发
                pushDown(rt);
                int max = 0;  //保存最大值
                //对左右区间进行判断 是否需要进行 左边 右边 节点的查询
                int mid= (l+r) >> 1;
                if(L <= mid){
                    max = Math.max(max,query(L,R,l,mid,rt<<1));
                }
                if(R > mid){
                    max = Math.max(max,query(L,R,mid+1,r,rt<<1|1));
                }
                return max;
            }
        }
    
        //定义一个函数，获取方块下落后的索引位置 将其转换成线段树结构的数组长度重要一个转换
        //pos 参数就是题目的原函数入参[[1,2],[2,3]].. [1,2]  表示第一个2*2的方块落在1下标 那么方块在x轴上 l边界就是在1 r边界就是在3
        public static HashMap<Integer,Integer> getIndex(int[][] pos){
            HashMap<Integer,Integer> map = new HashMap<>();   //哈希表 返回值
            TreeSet<Integer> set = new TreeSet<>();           //有序表 右需存放每个方块的l r区间位置
            for(int[] arr: pos){
                set.add(arr[0]);                            //依次添加每个方块的l坐标
                set.add(arr[0] + arr[1] -1);                //依次添加每个方块的r坐标 注意这里-1 是为了防止下个方块是贴着上一个方块的情况下，方块1的r边界与方块2的l边界同值重复累加  所以我们坐标就是[l,r) r是开区间 -1
            }
            int count = 0;                                  //计数 表示方块长度
            for(Integer index: set){
                map.put(index, ++count);                   //每个下标做键  值则是对应的++count 个数
            }
            return map;
        }
    
    
        //程序入口 pos方块  [[1,2],[2,3]].. [1,2]  表示第一个2*2的方块落在1下标 那么方块在x轴上 l边界就是在1 r边界就是在3
        public List<Integer> fallingSquares(int[][] positions) {
            List<Integer> res = new ArrayList<>();     //定义结果集
            HashMap<Integer, Integer> map = getIndex(positions);  //调用函数 得到一个方块下标索引：个数的哈希表
            int n = map.size();             //哈希表长度 表示线段树结构的大小长度
            SegmentTree tree = new SegmentTree(n);
            int max = 0;          //定义方块落后的最大高度
            for(int[] pos: positions){
                int L =map.get(pos[0]);               //依次遍历每个方块 获取对应的值 0位置表示L  pos[0]+pos[1]-1的对应值表示R
                int R =map.get(pos[0]+pos[1] - 1);
                int height = tree.query(L,R,1,n,1) + pos[1];   //刷新查询任务L,R范围高度值+当前的方块高度值
                max = Math.max(max, height);                         //刷新当前前面已经落下方块的情况下的最大高度值
                res.add(max);                                        //刷新当前结果集合 添加最大高度
                tree.update(L,R,height,1,n,1);                 //同时要进行更新线段树结构
            }
            return res;
        }
    }

[699.]: https://leetcode.cn/problems/falling-squares/description/
[4108dc0d215b4d44879afd0ad0b16753.png]: https://img-blog.csdnimg.cn/4108dc0d215b4d44879afd0ad0b16753.png
[6086309cb16b479cbc41d8d6e0775b80.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/d6a8549ade504c65abc4d76beb925c40.png