/**
 * 线段树
 * @author zzr
 * @create 2023-11-13-10:34
 */
public class SegmentTree {
    int[] arr;//原数组
    int[] sum;//线段树，保存区间信息：区间和
    int[] lazy;//懒标记，区间更新优化用，可以暂时不更新下层区间区间信息，等到需要的时候再下发更新

    public SegmentTree(int[] origin) {
        int n = origin.length + 1;
        this.arr = new int[n];
        System.arraycopy(origin, 0, this.arr, 1, n - 1);
        //4倍空间，保证够用
        sum = new int[n << 2];
        lazy = new int[n << 2];
        //从索引1开始放数据，用位运算提高计算效率
        build(1, n - 1, 1);
    }

    /**
     * 构建线段树：初始化区间信息
     * @param l 区间左端点
     * @param r 区间右端点
     * @param i 结点索引
     */
    private void build(int l, int r, int i) {
        if (l == r) {//叶子结点，直接填写值
            sum[i] = arr[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, i << 1);//递归构建左子树 左孩子索引：i*2
        build(mid + 1, r, i << 1 | 1);//递归构建右子树 右孩子索引：i*2+1
        sum[i] = sum[i << 1] + sum[i << 1 | 1];//汇总
    }

    /**
     * 区间查询
     * @param l 当前区间左端点
     * @param r 当前区间右端点
     * @param i 当前结点索引
     * @param left 查询区间左端点
     * @param right 查询区间右端点
     * @return 返回查询区间和
     */
    public int query(int l, int r, int i, int left, int right) {
        //当前区间全部不在查询区间
        if (r < left || l > right) {
            return 0;
        }
        //当前区间全部在查询区间内
        if (l >= left && r <= right) {
            return sum[i];
        }
        //当前区间只包含查询区间一部分
        push_down(i, r - l + 1);//如果当前区间有攒着的懒标记，则将懒标记下发，更新下层区间区间信息
        int mid = (l + r) >> 1;
        int lSum = query(l, mid, i << 1, left, right);//查询当前区间左子区间和
        int rSum = query(mid + 1, r, i << 1 | 1, left, right);//查询当前区间右子区间和
        return lSum + rSum;//返回两子区间和
    }

    /**
     * 区间增加（对区间所有值统一增加一个值，令区间相等时，为单点增加）
     * @param l 当前区间左端点
     * @param r 当前区间右端点
     * @param i 当前结点索引
     * @param left 增加区间左端点
     * @param right 增加区间右端点
     * @param val 增加的值
     */
    public void add(int l, int r, int i, int left, int right, int val) {
        //当前区间全部不在增加区间
        if (r < left || l > right) {
            return;
        }
        //当前区间全部在增加区间内
        if (l >= left && r <= right) {
            sum[i] += (r - l + 1) * val;//之前累加和+当前区间结点个数*增加的值
            lazy[i] += val;//打上懒标记，不继续向下更新
            return;
        }
        //当前区间只包含增加区间一部分
        push_down(i, r - l + 1);//如果当前区间有攒着的懒标记，则将懒标记下发，更新下层区间区间信息
        int mid = (l + r) >> 1;
        add(l, mid, i << 1, left, right, val);//当前区间左子区间增加值
        add(mid + 1, r, i << 1 | 1, left, right, val);//当前区间右子区间增加值
        sum[i] = sum[i << 1] + sum[i << 1 | 1];//汇总
    }

    /**
     * 将懒标记下发一级
     * @param i
     * @param len
     */
    private void push_down(int i, int len) {
        //有懒标记
        if (lazy[i] != 0) {
            //将标记传给左孩子
            sum[i << 1] += lazy[i] * (len - len / 2);
            lazy[i << 1] += lazy[i];
            //将标记传给右孩子
            sum[i << 1 | 1] += lazy[i] * (len / 2);
            lazy[i << 1 | 1] += lazy[i];
            //自己标记清0
            lazy[i] = 0;
        }
    }

}

public class NumArray {
    int[] sum;//区间和
    int n;

    public NumArray(int[] nums) {
        this.n = nums.length;
        sum=new int[n <<2];
        build(0,n-1,0,nums);
    }

    private void build(int l, int r, int i, int[] nums) {
        if (l==r){
            sum[i]=nums[l];
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,i*2+1,nums);
        build(mid+1,r,i*2+2,nums);
        sum[i]=sum[i*2+1]+sum[i*2+2];
    }

    /**
     * 单点修改
     * @param index
     * @param val
     */
    public void update(int index, int val) {
        change(0,n-1,0,index,val);
    }

    private void change(int l, int r, int i, int index, int val) {
        if (l==r){
            sum[i]=val;
            return;
        }
        int mid=(l+r)>>1;
        if (index<=mid) {//index在左子区间
            change(l,mid,i*2+1,index,val);
        }else {//index在右子区间
            change(mid+1,r,i*2+2,index,val);
        }
        sum[i]=sum[i*2+1]+sum[i*2+2];
    }

    /**
     * 区间查询
     * @param left
     * @param right
     * @return
     */
    public int sumRange(int left, int right) {
       return range(0,n-1,0,left,right);
    }

    private int range(int l, int r, int i, int left, int right) {
        if (r<left||l>right){
            return 0;
        }
        if (l>=left&&r<=right){
            return sum[i];
        }
        int mid=(l+r)>>1;
        int lSum = range(l, mid, i * 2 + 1, left, right);
        int rSum = range(mid+1, r, i * 2 + 2, left, right);
        return lSum+rSum;
    }
}