线段树

线段树相关知识点梳理

• 1.线段树实现：包括add，update，query方法的实现
• 2.业务代码简单验证
• =========思路============
• 我现在面临的问题是什么？
• 1.有一个需求，需要我将数组中5~99的所有值都统统加5，那么如果按照正常的遍历去实现，时间复杂度是O(N)的。
• 2.假设这个需求调用十分频繁，可想而知会造成比较大的性能消耗。
• 所以线段树就是处理上述问题的，尤其明显的优势：如区间类的更新，累加，查询都适用。
• 先说结论；
• 线段树可以将时间复杂度降到O(logN)级别，并且需要的额外空间复杂度不会超过4*N(画图知道，堆的结构类似一个小山，从上到下铺满了也就是1，2，4，8，16这样铺下来，我们会发现及时arr长度等于N 比如=8的时候 前面的节点个数=7 我们近似看作8 这就是2N，又下面那排最大不超过2N，所以我们只需要准备一个4N的空间，绝对够用)
• 我们需要构造一个类似堆的数据；假设我们原数组内一共有4个数，下标从1-4(这里不从0开始是方便思考)
• 我们需要进行如下转换
• [3,7,5,9]=>[24,10,14,3,7,5,9] 再看一组数据
• [3,7,5,9,1] => [25,10,15,3,7,5,10,null,null,null,null,null,null,9,1]
• 我们姑且把原数组叫arr，转换后的数组叫sum(sum也是从1开始下标)
• 规律就是，先把后面的数组用堆的形势展开，然后sum[1]的位置记录的是arr[1-4]的累加和sum[2]是arr[1-2]的累加和(左孩子)
• null那些说明最后一行有些空间没有用到，但是还是分配了。结构的最后还需要写入信息。
• (当然这种遇到无法被2整除的，是让左孩子分配更多还是右孩子分配更多无所谓，看个人喜好)。比如你把1-5 分成1-3 4-5也可以。
• 基本结构有了，我们需要在分情况进行处理。
• 如果我有一个格子 存放的是2-10的累加和，那么如果新任务也是需要在2-10上加，那么就直接在这层加就好了，不需要在把2-10往下拆，继续加。
• 我们还可以引入一个数组，姑且叫做lazy。它的作用是假设之前任务是在3-29之间都加5 那么我们可以在3-29对应的数组下标同位置的lazy数组下记录一个5，
• 表示这里有一个5要累加，但是可以先不加，因为我们可以看后续还会收到什么命令。如果后续命令是累加2 那么我们直接在lazy数组那里改成7，
• 知道出现一个任务不是把3-29全包，比如出现个新任务要求在3-9之间累加6，
• 那么我们就必须先将之前lazy下来的任务下发，累加完毕，然后在根据3-9往下拆，拆到合适的位置在lazy一个6.
• 当然有可能3-9其实是由3-6，7-9拼成的。没关系，我们直接将连各个分别lazy之后最后结算的时候累加一下即可
• */

public class SegmentTree_31 {
    //构造一下SegmentTree类
    public static class SegmentTree {
        /**
         * max 原数组长度
         * 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 SegmentTree(int[] origin){
            maxN = origin.length+1;
            arr = new int[maxN];
            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];
        }

        private void pushDown(int ln, int rn, int rt){
            // 更新和累加任务如果都存在的话，肯定是要先更新 然后再累加的。所以先判断updete再去判断lazy
            //下面这段代码就是说如果存在更新，那么我下面这些数组要怎么处理
            if(update[rt]){
                // 左右孩子的更新状态设为true
                update[rt<<1] = true;
                update[rt<<1|1] = true;
                // 左右孩子区间更新的值为change[rt]
                change[rt<<1] = change[rt];
                change[rt<<1|1] = change[rt];
                // 左右孩子区间累加和
                sum[rt<<1] = change[rt]*ln;
                sum[rt<<1|1] = change[rt*rn];
                // 更新的时候，左右孩子区间lazy数组设为0
                lazy[rt<<1] = 0;
                lazy[rt<<1|1] = 0;
                // 一定要记住吧update[rt]设为false
                update[rt] =false;
            }
            // 如果lazy位不是0，说明之前已经懒了一些任务在这里了，这个时候要更新lazy数组和sum数组
            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;
            }
        }
        // 初始化构建sum数组,在arr[l~r]区间 去build
        // l r 代表的是arr的左右区间下标 rt代表的是当前这个sum的下标，这个位置的sum 囊括的就是arr[l~r]的累加和
        // 分情况考虑l=r 和l！=r
        private 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区间，每个数加个C
        //l r rt参数代表从最初任务一路往下拆下来，当前的sum节点，rt代表他的下标，l,r分别记录了他所囊括的arr是l-r的区间
        private void add(int L, int R, int C,int l, int r, int rt){
            if(L<=l&&r<=R){
                //说明当前所在的sum节点是完全被任务所包围的，比如我任务是要在1-9区间加个5，现在这个位置是2-7
                sum[rt]+=C*(r-l+1);
                lazy[rt]+=C;
                return;
            }
            int mid = (l+r)>>1;
            //先pushDown,将左右孩子区间的sum lazy数据先更新正确
            pushDown(mid-l+1,r-mid,rt);
            if(L<=mid){
                add(L,R,C,l,mid,rt<<1);
            }
            if (R>mid){
                add(L,R,C,mid+1,r,rt<<1|1);
            }
            pushUp(rt);
        }
        private void update(int L, int R, int C,int l, int r, int rt){
            if(L<=l&&r<=R){
                //说明当前所在的sum节点是完全被任务所包围的，比如我任务是要在1-9区间统一更新成5，现在这个位置是2-7
                update[rt] = true;
                change[rt] = C;
                sum[rt]=C*(r-l+1);
                lazy[rt]=0;
                return;
            }
            int mid = (l+r)>>1;
            //先pushDown,将左右孩子区间的sum lazy数据先更新正确
            pushDown(mid-l+1,r-mid,rt);
            if(L<=mid){
                update(L,R,C,l,mid,rt<<1);
            }
            if (R>mid){
                update(L,R,C,mid+1,r,rt<<1|1);
            }
            pushUp(rt);
        }
        // 因为查询不需要修改数据 所以省去了参数C
        private 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,将左右孩子区间的sum lazy数据先更新正确
            pushDown(mid-l+1,r-mid,rt);
            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{
        private int[] arr;
        public Right(int[] origin){
            arr = new int[origin.length+1];
            for (int i=1;i<arr.length;i++){
                arr[i] = origin[i-1];
            }
        }
        public void add(int L,int R,int C){
            for(int i=L;i<=R;i++){
                arr[i] = arr[i]+C;
            }
        }
        public void update(int L,int R,int C){
            for(int i=L;i<=R;i++){
                arr[i] = C;
            }
        }
        // 查询l-r上的累加和
        public long query(int L,int R){
            long ans = 0;
            for(int i=L;i<=R;i++){
                ans+=arr[i];
            }
            return ans;
        }
    }

    //写个测试
    public static void main(String[] args) {
        int[] origin = new int[]{3,5,6,-5,58,9,5};
        SegmentTree segmentTree = new SegmentTree(origin);
        Right right = new Right(origin);
        segmentTree.build(0, origin.length, 1);
        long num1 = segmentTree.query(2, origin.length-1,0, origin.length, 1);
        long num2 = right.query(2,origin.length-1);
        System.out.println(num1);
        System.out.println(num2);
        System.out.println(num1==num2);
    }
}