当前位置: 首页 > article >正文

leetcode|刷算法 线段树原理以及模板

线段树出现的题目特征

线段树使用的题目。每次操作都要得到返回结果的。

比如

699. 掉落的方块 - 力扣(LeetCode)

2286. 以组为单位订音乐会的门票 - 力扣(LeetCode)

1845. 座位预约管理系统 - 力扣(LeetCode)

线段树的原理

线段树的原理就是使用递归的思想对数值进行更新。

比如查询6到10区间上的最大值。如果传统的需要遍历一遍。但是如果有一个node刚好记录了这个范围6到10上的最大值,那么直接将这里的node上的数值返回即可。

另外,除了最大值,还有一个范围上的累加和,使得一个范围上进行更新操作,一个范围上进行累加操作。

原数组 orginArr

范围1到n上,需要使用4*(n+1) 的长度来记录树 使用arrSum表示

节点使用node标识,范围左边是left,右边是right

根节点就是 node=1 left=1 right=n

任意节点的左节点就是 node*2 左边边界 left 右边边界 right/2

任意节点的右节点就是 node*2+1 左边边界 right/2+1 右边边界 right

当左边界,右边界相同时候。left也就是1-n范围上的这个值对应的 arrSum[node] 就是表示原数组的该值origin[left]

线段树的模板

模板改自左程云老师的模板,属于二次改造,就高级写法进行降级,使得易懂。对单字母的变量进行多个字母命名,使得看着没有这么眼花


    public static void main(String[] args) {
        int[] origin = {2, 1, 1, 2, 3, 4, 5};
        SegmentTree seg = new SegmentTree(origin);
        int start = 2;
        int end = 5;
        int value = 4;
        seg.add(start, end, value);  // start到end区间上统一增加值
        seg.update(start, end, value);  //  start到end区间上统一更新
        long sum = seg.querySum(start, end);  //  start到end区间求和
    }

这里入参会看着简洁些。start,end,value 也容易理解

另外的参数是left,right,node。

对于维护的数组,sumArr 树节点上的累加和 ,taskArr 树节点上的需要下发的增加数值的任务,changeArr 树节点上的需要下发的修改任务

taskArr[node] = 5 node的left和right。比如为6和10,也就是范围6到10上,都需要增加10

模板如下
public static void main(String[] args) {
    int[] origin = {2, 1, 1, 2, 3, 4, 5};
    SegmentTree seg = new SegmentTree(origin);
    int start = 2;
    int end = 5;
    int value = 4;
    seg.add(start, end, value);  // start到end区间上统一增加值
    seg.update(start, end, value);  //  start到end区间上统一更新
    long sum = seg.querySum(start, end);  //  start到end区间求和
    System.out.println(sum);
    System.out.println("对数器测试开始...");
    System.out.println("测试结果 : " + (test() ? "通过" : "未通过"));

}

// 线段树模板
public static class SegmentTree {
    int right;
    int left = 1;
    int[] arr;
    int[] sumArr;
    int[] taskArr;
    int[] changeArr;
    boolean[] updateArr;

    public SegmentTree(int[] origin) {
        right = origin.length;
        int length = right + 1;
        arr = new int[length];
        for (int i = 1; i < length; i++) {
            arr[i] = origin[i - 1];
        }
        sumArr = new int[length * 4];
        taskArr = new int[length * 4];
        // changeArr和updateArr是一起使用的,但是一般题目可以不需要updateArr,因为通常修改的数值是大于0的。可以用是否为0来判断
        changeArr = new int[length * 4];
        updateArr = new boolean[length * 4];
        // 构建线段树的 SumArr
        buildSumArr(left, right, 1);
    }

    public void buildSumArr(int left, int right, int node) {
        if (left == right) { // 一定要拆解到单个节点的时候才可以进行赋值
            sumArr[node] = arr[left];
            return;
        }
        int mid = (left + right) / 2;
        buildSumArr(left, mid, node * 2); // 左节点
        buildSumArr(mid + 1, right, node * 2 + 1); // 右节点
        // 求左右节点的和
        sumArr[node] = sumArr[node * 2] + sumArr[node * 2 + 1];
    }



    private void refresh(int root, int leftNum, int rightNum) {
        // update和change必须是一起出现的
        // task是单独出现的,而且上面操作的会将task给覆盖掉

        if (updateArr[root]) {  // 它以及下面的树需要更新
            updateArr[root * 2] = true;
            updateArr[root * 2 + 1] = true;

            changeArr[root * 2] = changeArr[root]; // 需要更新的值
            changeArr[root * 2 + 1] = changeArr[root]; // 需要更新的值

            taskArr[root * 2] = 0; // 既然都更新了,那么lazy的值就可以清空了
            taskArr[root * 2 + 1] = 0;

            sumArr[root * 2] = changeArr[root] * leftNum; // 更新求和信息
            sumArr[root * 2 + 1] = changeArr[root] * rightNum; // 更新求和信息
            updateArr[root] = false;  // 自身更新好了
        }
        if (taskArr[root] != 0) {     // 这个值是需要下发的值
            taskArr[root * 2] += taskArr[root]; // 自身需要下发的值,加上来自上面的值
            sumArr[root * 2] += taskArr[root] * leftNum; // 结算上面下发的值

            taskArr[root * 2 + 1] += taskArr[root];
            sumArr[root * 2 + 1] += taskArr[root] * rightNum;  // 同上
            taskArr[root] = 0;  // 需要下发的值更新
        }
    }

    public void update(int start, int end, int value) {
            // 这里的left,right,1非常重要,1代表的是节点的位置,而left和right代表的是改节点的管辖范围。这里是root开始,root为1
            // int left, int right, int node  代表这个节点的范围,每次会更新传递
            // 这里的left和right最终会聚合到一起,代表的是arr的位置
            update(start, end, value, left, right, 1);
        }

        public void update(int start, int end, int value, int left, int right, int node) {
            // 满足更新的条件
            if (start <= left && right <= end) {
                updateArr[node] = true;  // 它以及下面的树需要更新
                changeArr[node] = value;  //更新数字
                sumArr[node] = value * (right - left + 1); // 求和
                taskArr[node] = 0;
                return;
            }
            // 任务下发。
            int mid = (left + right) / 2;
            // 左树的个数,和右树的个数
            refresh(node, mid - left + 1, right - mid);
            if (start <= mid) {
                update(start, end, value, left, mid, node * 2);
            }
            if (end > mid) {
                update(start, end, value, mid + 1, right, node * 2 + 1);
            }
            sumArr[node] = sumArr[node * 2] + sumArr[node * 2 + 1];
        }

        // 添加
        public void add(int start, int end, int value) {
            add(start, end, value, left, right, 1);
        }

        public void add(int start, int end, int value, int left, int right, int node) {
            // 开始点和结束点,把树的左右范围给包括了
            if (start <= left && right <= end) {
                sumArr[node] += value * (right - left + 1); // 这里的结算逻辑非常重要,会根据不同的题目进行变换
                taskArr[node] += value;
                return;
            }
            int mid = (left + right) / 2;
            // 这里最要是对于changeArr和taskArr的操作
            refresh(node, mid - left + 1, right - mid);

            if (start <= mid) { // 如果开始位置比mid大,那么左边就没有下发的意义了,只要下发右边就行了
                add(start, end, value, left, mid, node * 2); // 左节点 这里和初始化的策略一样
            }
            if (end > mid) {
                add(start, end, value, mid + 1, right, node * 2 + 1); // 右节点
            }
            sumArr[node] = sumArr[node * 2] + sumArr[node * 2 + 1];
        }

        public long querySum(int start, int end) {
            return querySum(start, end, left, right, 1);
        }

        public long querySum(int start, int end, int left, int right, int node) {
            // 这里是返回当前节点,因为start和end已经被包围了。
            if (start <= left && right <= end) {
                return sumArr[node];
            }
            int mid = (left + right) / 2;
            refresh(node, mid - left + 1, right - mid);
            long ans = 0;
            if (start <= mid) { // 下发左边的
                ans += querySum(start, end, left, mid, node * 2);
            }
            if (end > mid) { // 下发右边的
                ans += querySum(start, end, mid + 1, right, node * 2 + 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);
            SegmentTree seg = new SegmentTree(origin);
            int N = origin.length;
            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);
                    rig.add(L, R, C);
                } else {
                    seg.update(L, R, C);
                    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.querySum(L, R);
                long ans2 = rig.query(L, R);

                if (ans1 != ans2) {
                    System.out.println(k);
                    System.out.println(ans1 + "   " + ans2);
                    return false;
                }
            }
        }
        return true;
    }
总结

个人练习了3道线段树的题目。写出来非常不容易,带着模板都没这么简单可以做出来

更多的是要学会这里递归的思想,做到灵活运用。像是2286题目 和区间没有关系,每次都是需要细化到单点。


http://www.kler.cn/a/327145.html

相关文章:

  • 【深度学习基础】深入理解 卷积与卷积核
  • MySQL的约束和三大范式
  • 算法笔记:Day-09(初始动态规划)
  • 浅谈QT中Tab键的切换逻辑
  • YOLOv11改进策略【卷积层】| CGblock 内容引导网络 利用不同层次信息,提高多类别分类能力 (含二次创新)
  • Data+AI━━揭秘千亿参数背后的技术较量:全球巨头的大模型布局!
  • 用OpenSSL搭建PKI证书体系
  • react 前端框架中的 三层(service,model,index)具体操作
  • CSS 参考手册
  • 某星球预约抢票脚本
  • 25中国烟草校园招聘面试问题总结 烟草面试全流程及面试攻略
  • 人工智能辅助的神经康复
  • Thinkphp/Laravel旅游景区预约系统的设计与实现
  • open-resty 服务安装jwt插件
  • SpringBoot教程(三十一) | SpringBoot生成Docker镜像包
  • Gdao v1.2.0:Go语言高效ORM框架
  • 初学51单片机之I2C总线与E2PROM二
  • 【动态规划-最长公共子序列(LCS)】力扣583. 两个字符串的删除操作
  • Python和C++及MATLAB距离相关性生物医学样本统计量算法及数据科学
  • WebRTC入门
  • 大屏走马灯与echarts图表柱状图饼图开发小结
  • 嵌入式单片机底层原理详解
  • 一文详解WebRTC、RTSP、RTMP、SRT
  • 《深圳大学学报理工版》
  • 【玩转贪心算法专题】56. 合并区间【中等】
  • 004集—— txt格式坐标写入cad(CAD—C#二次开发入门)