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题目 和区间没有关系，每次都是需要细化到单点。