线段树

class SegmentTree {
    int[] arr;
    int[] d;
    int[] b;
    boolean[] v;

    public SegmentTree(int[] arr) {
        this.arr = arr;
        d = new int[arr.length * 4];
        b = new int[arr.length * 4];
        v = new boolean[arr.length * 4];

        buildTree(0, arr.length - 1, 0, d, arr);
    }

    private void buildTree(int s, int t, int p, int[] d, int[] arr) {
        if(s == t) {
            d[p] = arr[s];
            return;
        }

        int m = (s + t) >> 1;
        buildTree(s, m, 2 * p + 1, d, arr);
        buildTree(m + 1, t, 2 * p + 2, d, arr);
        d[p] = d[2 * p + 1] + d[2 * p + 2];
    }

    public void rangeUpdate(int l, int r, int c) {
        rangeUpdate(l, r, c, 0, arr.length - 1, 0, d, b, v);
    }

    private void rangeUpdate(int l, int r, int c, int s, int t, int p, int[] d, int[] b, boolean[] v) {
        if(s >= l && t <= r) {
            d[p] = c * ((t - s) + 1);
            b[p] = c;
            v[p] = true;
            return;
        }

        int m = (s + t) >> 1;
        if(v[p]) {
            tagDown(d, b, v, m, s, t, p);
        }

        if(m >= l) rangeUpdate(l, r, c, s, m, 2 * p + 1, d, b, v);
        if(m + 1 <= r) rangeUpdate(l, r, c, m + 1, t, 2 * p + 2, d, b, v);
        d[p] = d[2 * p + 1] + d[2 * p + 2];
    }

    public int rangeSum(int l, int r) {
        return rangeSum(l, r, 0, arr.length - 1, 0, d, b, v);
    }

    private int rangeSum(int l, int r, int s, int t, int p, int[] d, int[] b, boolean[] v) {
        if(s >= l && t <= r) {
            return d[p];
        }

        int sum = 0;
        int m = (s + t) >> 1;
        if(v[p]) {
            tagDown(d, b, v, m, s, t, p);
        }

        if(m >= l) sum += rangeSum(l, r, s, m, 2 * p + 1, d, b, v);
        if(m + 1 <= r) sum += rangeSum(l, r, m + 1, t, 2 * p + 2, d, b, v);

        return sum;
    }

    private void tagDown(int[] d, int[] b, boolean[] v, int m, int s, int t, int p) {
        d[2 * p + 1] = b[p] * ((m - s) + 1);
        d[2 * p + 2] = b[p] * ((t - (m + 1)) + 1);
        b[2 * p + 1] = b[p];
        b[2 * p + 2] = b[p];
        v[2 * p + 1] = true;
        v[2 * p + 2] = true;
        b[p] = 0;
        v[p] = false;
    }
}

class SegmentTree {
    int[] arr;
    int[] d;
    int[] b;

    public SegmentTree(int[] arr) {
        this.arr = arr;
        d = new int[arr.length * 4];
        b = new int[arr.length * 4];

        // build tree
        buildSegmentTree(0, arr.length - 1, 0, arr, d);
    }

    /**
     * 线段树初始化
     *
     * @param s     区间左边界
     * @param t     区间有边界
     * @param p     区间编号
     * @param arr   原始数组
     * @param d     线段树树状数组
     */
    private void buildSegmentTree(int s, int t, int p, int[] arr, int[] d) {
        if(s == t) {
            d[p] = arr[s];
            return;
        }

        int m = (s + t) >> 1;
        buildSegmentTree(s, m, 2 * p + 1, arr, d);
        buildSegmentTree(m + 1, t, 2 * p + 2, arr , d);
        d[p] = d[2 * p + 1] + d[2 * p + 2];
    }

    /**
     * 外部调用方法
     *
     * @param l     更新左边界
     * @param r     更新右边界
     * @param c     增量
     */
    public void rangeUpdate(int l, int r, int c) {
        rangeUpdate(l, r, c, 0, arr.length - 1, 0, d, b);
    }

    /**
     *
     * @param l     更新左边界
     * @param r     更新右边界
     * @param c     增量
     * @param s     区间左边界
     * @param t     区间右边界
     * @param p     区间编号
     * @param d     线段树树状数组
     * @param b     标记数组
     */
    private void rangeUpdate(int l, int r, int c, int s, int t, int p, int[] d, int[] b) {
        if(s >= l && t <= r) {
            d[p] += c * ((t - s) + 1);
            b[p] += c;
            return;
        }

        int m = (s + t) >> 1;
        if(s != t && b[p] != 0) {
            tagDown(d, b, m, s, t, p);
        }

        if(m >= l) rangeUpdate(l, r, c, s, m, 2 * p + 1, d, b);
        if(m + 1 <= r) rangeUpdate(l, r, c, m + 1, t, 2 * p + 2, d, b);
        d[p] = d[2 * p + 1] + d[2 * p + 2];
    }

    /**
     *  外部调用方法
     * @param l     查询左边界
     * @param r     查询右边界
     * @return      区间和
     */
    public int rangeSum(int l, int r) {
        return rangeSum(l, r, 0, arr.length - 1, 0, d, b);
    }

    /**
     *
     * @param l     查询左边界
     * @param r     查询右边界
     * @param s     区间左边界
     * @param t     区间右边界
     * @param p     区间编号
     * @param d     线段树树状数组
     * @param b     标记数组
     * @return      区间和
     */
    private int rangeSum(int l, int r, int s, int t, int p, int[] d, int[] b) {
        if(s >= l && t <= r) {
            return d[p];
        }

        int sum = 0;
        int m = (s + t) >> 1;
        if(s != t && b[p] != 0) {
            tagDown(d, b, m, s, t, p);
        }

        if(m >= l) sum += rangeSum(l, r, s, m, 2 * p + 1, d, b);
        if(m + 1 <= r) sum += rangeSum(l, r, m + 1, t, 2 * p + 2, d, b);

        return sum;
    }

    private void tagDown(int[] d, int[] b, int m, int s, int t, int p) {
        d[2 * p + 1] += b[p] * ((m - s) + 1);
        d[2 * p + 2] += d[p] * ((t - (m + 1)) + 1);
        b[2 * p + 1] += b[p];
        b[2 * p + 2] += b[p];
        b[p] = 0;
    }
}