线段树，，

线段树解决的问题

假设给定一个数组，长度为1000，要求 1~200 范围上所有的数都统一增加6；7 ~ 375 范围上的所有数都更新为4；查询3 ~ 999 范围上所有的数的累加和。

所以，线段树解决的问题就是：

1.区间上的统一增加add
2.区间上的统一更新update
3.区间上的累加和统一查询query

暴力解

暴力解只能遍历，时间复杂度毫无疑问都是O(N)

特殊情况

其实大多数时候，一个题中并不需要用到线段树中的所有结构，也就是并不是要同时用到add、update、query，这是比较难的，因为要确保add和update单独使用的时候要互相独立，不打架

线段树也有非递归版本，但是非递归版本太难了，而且用递归版本就可以解决所有问题了，一般用递归版本也不用担心栈会爆掉，因为深度不会特别大。

建立类似树状的结构

在线段树中，数组下标一般从1开始算。

任何一个结点 i 的父结点是 i / 2，
任何一个结点 i 的左孩子是 2 * i，右孩子是 2 * i + 1
因为下标从1开始算，有点像堆。

数组是长度为偶数个的时候

数组长度为奇数个的时候

申请的数组长度需要多大

数组长度是2的某次方时候，最省空间，只需要准备2N长度的数组；

数组长度是2的某次方+1的时候，最浪费空间，但也只需要准备4N长度的数组就可以了。

为什么？因为二叉树最底层结点的数量 等于 最底层往上所有层的结点数量相加

线段树的时间复杂度

O(logN)

在想象出来的物理结构上实现线段树的三个操作

add操作

原始数组，准备一个累加和数组和存懒信息的数组
在数组1 ~ 4 范围上的每个值加上3

1 ~ 2 范围上的每个值都加个4

任何一个结点的累加和如何得到

左孩子的累加和加上右孩子的累加和

private void pushUp(int rt){
    
            sum[rt]=sum[rt<<1]+sum[rt<<1|1];
        }

构建二叉树（自己想象出来的类似树状的结构）

// 在初始化阶段，先把sum数组填好
        // 在arr[l~r]范围上，去build，1~N
        // rt：这个范围在sum中的下标!!!
        // 范围和下标是解耦的，也就是说前两个参数跟第三个参数是没有关联的
        public 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);
            pushUp(rt);
        }

懒更新

线段树时间复杂度是O(logN)的关键体现，一个任务下来以后，卡着一条左边界下去一次，卡着一条右边界下去一次。

一个新的任务到来时，先检查当前范围是否已经懒住信息，如果有，先把懒信息下发一层，再处理新的任务（但是在代码中实现的是把新任务跟之前已经懒住的信息累加，也就是说之前的懒信息先不下发了）

什么时候可以用线段树

左边可以得到某一个信息，右边可以得到某一个信息，父结点的信息可以由左右两个信息在O(1)时间内加工好，而且不用具体调研底层状况的，这一类区间查询，区间更新，区间增加问题，可以用线段树。

package com.harrison.class21;

/** * @author Harrison * @create 2022-03-31-22:40 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。 */
public class Code01_SegmentTree {
    
    public static class SegmentTree {
    
        // 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;// true：表示该位置上的信息是有效的，否则无效

        public SegmentTree(int[] origin) {
    
            MAXN = origin.length + 1;
            arr = new int[MAXN]; //arr[0]不用，从1开始用
            for (int i = 1; i < MAXN; i++) {
    
                arr[i] = origin[i - 1];
            }
            sum = new int[MAXN << 2]; // 用来支持脑补概念中，某一个范围的累加和信息
            lazy = new int[MAXN << 2]; // 用来支持脑补概念中，某一个范围没有往下传递的累加任务
            change = new int[MAXN << 2]; // 用来支持脑补概念中，某一个范围没有更新操作的任务
            update = new boolean[MAXN << 2]; // 用来支持脑补概念中，某一个范围更新任务，更新成了什么
        }

        private void pushUp(int rt) {
    
            sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
        }

        // 之前的，所有懒增加，和懒更新，从父范围，发给左右两个子范围
        // 分发策略是什么
        // ln表示左子树元素结点个数，rn表示右子树结点个数
        // 该方法就是把之前的懒信息分发下去
        public void pushDown(int rt, int ln, int rn) {
    
            // 一定要先检查有没有update，再检查有没有累加和
            if (update[rt]) {
    // 如果父结点有了一个更新信息
                // 左右孩子都改为true
                update[rt << 1] = true;
                update[rt << 1 | 1] = true;
                // change 左右两个孩子都改成父结点的信息
                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;
            }
            if (lazy[rt] != 0) {
    
                lazy[rt << 1] += lazy[rt];
                sum[rt << 1] += lazy[rt] * ln;
                lazy[rt << 1 | 1] += lazy[rt];
                sum[rt << 1 | 1] += lazy[rt] * rn;
                lazy[rt] = 0;
            }
        }


        // 在初始化阶段，先把sum数组填好
        // 在arr[l~r]范围上，去build，1~N
        // rt：这个范围在sum中的下标!!!
        // 范围和下标是解耦的，也就是说前两个参数跟第三个参数是没有关联的
        public 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);
            pushUp(rt);
        }

        // L~R -> 任务范围， 所有的值变成C
        // l,r -> 表达的范围
        // rt -> 去哪找l,r范围上的信息
        public 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;
            }
            // 当前任务并没有把l...r全包住，就要把当前任务往下发
            // 为什么要求中点？因为要标记左侧和右侧各有几个数
            int mid = (l + r) >> 1;// l...mid (rt<<1) mid+1...r (rt<<1|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);
            }
            // 左右孩子做完任务后，更新我的sum信息
            pushUp(rt);
        }

        // L~R -> 任务范围，所有的值累加上C
        // l,r -> 表达的范围
        // rt -> 去哪找l,r范围上的信息
        public void add(int L, int R, int C, int l, int r, int rt) {
    
            // 任务的范围彻底覆盖了，当前表达的范围
            if (L <= l && r <= R) {
    
                sum[rt] += C * (r - l + 1);
                lazy[rt] += C;
                return;// 懒住就不下发了，时间复杂度优秀的关键体现
            }
            // 当前任务并没有把l...r全包住，就要把当前任务往下发
            // 为什么要求中点？因为要标记左侧和右侧各有几个数
            int mid = (l + r) >> 1;// l...mid (rt<<1) mid+1...r (rt<<1|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);
            }
            // 左右孩子做完任务后，更新我的sum信息
            pushUp(rt);
        }

        // 1~6 累加和是多少？ 1~8 rt
        public 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 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);
            SegmentTree seg = new SegmentTree(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};
        SegmentTree seg = new SegmentTree(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() ? "通过" : "未通过"));

    }
}