线段树学习

• 参考资料: 《算法竞赛入门到进阶》、左神算法课
• 线段树示意图, 图片摘自《算法竞赛入门到进阶》
  
• 解决区间更新、区间查询、区间累加问题
• 基于原数组的4倍数组长度建立sum数组，完成对原数组origin的树化
• 线段树采用一种懒惰的做法，当累加(更新)操作是针对一个整个的区间时，只对这个线段区间做整体上的修改，其内部的元素先不变，当这段区间的一致性被破坏时才将变化值传递给子区间，时间复杂度 O(nlogn)
• 字段解释
  • max：原始数组的最大长度
  • arr[]：原始数组src的copy, arr[]下标从1开始, 用数组表示一棵树时, 根节点下标为 i, 则左孩子为 (i << 1)，右孩子为 (i << 1 | 1), 所以树的根节点用1表示比较方便
  • sum[]：累加和数组, 存储arr[]上一段区间的范围, 其下标用 rt表示
  • lazy[]：懒数组, 存储sum[]区间上未下发的累加信息
  • change[]：sum[]范围上所有的值被更新成了啥
  • update[]：表示change[]中的特殊值是是要更新的值还是系统默认值, 比如数字 0, 是sum[rt]区间被更新为 0还是系统默认值为 0呢？ true表示被更新的值
• 建树操作
  • 如果区间分为 l == r，说明此时递归到叶子节点了, 直接给sum[rt]赋值为arr[l]即可
  • 否则递归构建左右子树，当程序返回到后序位置时说明rt节点的左右子树都构建完毕, 自然地sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]
• 累加操作：
  • 考虑数组范围[1, 500]上进行如下两次累加操作 [1, 500]范围上的所有数加上 2, [6, 366]范围上的所有数加上 6
    • 第一次累加2时判断区间 [1, 500] == [1, 500]所以'懒'住信息不下发, 标记lazy[rt] += 2
    • 第二次累加6时判断区间 [6, 366] <= [1, 500], 所以将区间[1, 500]上次懒住的信息下发一层, 然后再进行本次累加操作, 此后分别递归[6, 250]、[251, 500]....等等范围, 直到信息能够被懒住, 期间每次遇到上一次的懒任务都先下发。
  • 为什么只下发一层呢？
    • 因为本次累加操作当前看的层的线段区间一致性被破坏, 第一次[1, 500]累加了2但是第二次[6, 366]上又累加了6,破坏了线段区间的一致性所以将第一次累加的2下发一层，
    • 因为是递归操作，所以处理下一层时会发现[1, 250]区间存在懒信息累加2, 本次又要在[3, 250]上累加6，又破坏了[1, 250]区间上的一致性，所以继续下发上次的lazy[rt]=2的累加信息,然后在处理本次的lazy[rt]=6。
  • 什么叫线段区间一致性？
    • 对于区间[1, 5]上只能有一段覆盖区间[1, 5]的累加信息, 不能既有[1, 5]上累加2, [2, 5]上累加6这种操作, 所以要清算历史旧账
• 更新操作:
  • 类似累加操作, 只不过操作的数组是 update[]和 change[], 同样现下发懒人物任务后在进行更新, 防止更新操作之后的累加任务丢失, 比如[1, 500]上的数更新为3, 然后[1, 500]上的数累加2, 则先更新是对的, 先累加在更新会导致累加结果丢失, 即[1, 500]上的数都变成了3, 实际是5才对
• 区间查询操作:
  • 类似累加操作, 如果懒住了直接返回, 否则现下发之前的懒任务, 然后递归计算答案后返回

package com.lxpstu.tree;

/**
 * @Author: lxpStu
 * @Date: 2023/02/16/17:52
 * @Description: 线段树模板
 *
 */
public class SegmentTree {
    int max;
    int[] arr;
    int[] sum;
    int[] lazy;
    int[] change;
    boolean[] update;

    public SegmentTree(int[] origin) {
        this.max = origin.length + 1;
        this.arr = new int[max];
        System.arraycopy(origin, 0, arr, 1, max - 1);
        this.sum = new int[max << 2];
        this.lazy = new int[max << 2];
        this.change = new int[max << 2];
        this.update = new boolean[max << 2];
    }

    /**
     * rt:arr[l...r]范围在sum[]中的下标
     */
    public void build(int l, int r, int rt){
        if(l == r) {
            // 此时递归到叶子节点了
            sum[rt] = arr[l];
            return;
        }
        // 取中点, 构建左右子树
        int mid = l + (r - l) >> 1;
        build(l, mid, rt << 1);
        build(mid + 1, r, rt << 1 | 1);
        // 递归处理完左右孩子的sum[rt]之后处理自己的sum[rt]
        pushUp(rt);
    }

    /**
     * sum[rt]表示线段树的区间范围 l...r上的数字之和
     * C:  [L, R]本次下发的任务范围, 将[L, R]范围上的数加上C
     */
    public void add(int rt, int l, int r, int L, int R, int C){
        if(L <= l && r <= R){
            // 任务范围包括了线段树区间
            // 区间上所有数(r - l + 1个)都加上 C
            sum[rt] += C * (r - l + 1);
            // 懒标记
            lazy[rt] += C;
            return;
        }
        int mid = l + (r - l >> 1);
        // 下发之前的老任务
        pushDown(rt, mid - l + 1, r - mid);
        // 处理如区间[1, 500]下发任务[3, 384]这种无法懒住的情况, 递归下发任务给左右孩子
        if (L <= mid) {
            add(rt << 1, l, mid, L, R, C);
        }
        if (R > mid) {
            add(rt << 1 | 1, mid + 1, r, L, R, C);
        }
        // 处理自己的sum[rt]
        pushUp(rt);
    }

    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;
        }
        int mid = l + (r - l >> 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);
        }
        pushUp(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 - l >> 1);
        pushDown(rt, mid - l + 1, r - mid);
        long res = 0;
        if (L <= mid) {
            res += query(L, R, l, mid, rt << 1);
        }
        if(R > mid){
            res += query(L, R, mid + 1, r, rt << 1 | 1);
        }
        return res;
    }

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

    /**
     * ln:左孩子节点个数, rn:右孩子节点个数
     */
    private void pushDown(int rt, int ln, int rn){
        // 必须先检查update再检查add,因为最近一次更新之后如果存在累加操作之后再次更新的话会将累加的值清空
        // 先累加再更新会导致白累加，最终还是被更新了。
        // 如果是[1, 500]上的数更新为3, 然后[1, 500]上的数累加2, 则先更新是对的, 先累加在更新会导致累加
        // 结果丢失, 导致[1, 500]上的数都变成了3, 实际是5才对
        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;
            lazy[rt << 1 | 1] = 0;
            sum[rt << 1] = change[rt] * ln;
            sum[rt << 1 | 1] = change[rt] * rn;
            update[rt] = false;
        }
        // 当前节点懒不下去了, 下发一层, 然后将自己的懒信息置为 0
        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;
        }
    }
}