[数据结构与算法]线段树 JAVA

class SegmentTree
{
    int[] arr;
    int[] sign;
    int len;
    //建一棵空树
    public SegmentTree( int len )
    {
        this.len = len;
        len *= 4;
        this.sign = new int[len];
        this.arr = new int[len];
    }
    //由一个已知数组来建树
    public SegmentTree( int[] nums )
    {
        this( nums.length );
        build( nums , 0 , nums.length-1 , 1 );
    }
    //对 nums 数组的 low-high 区间进行建树 ， 以 arr 数组的 index 为根节点
    private int build( int[] nums , int low , int high , int index  )
    {
        //叶子节点
        if( low == high )
        {
            arr[index] = nums[low];
            return arr[index];
        }
        //非叶子节点
        else
        {
            int mid = ((low+high)>>1);
            arr[index] = build( nums , low , mid , index*2 ) + build( nums , mid+1 , high , index*2+1 );
            return arr[index];
        }
    }
    public void update( int low , int high , int change  )
    {
        update( low , high , change , 1 , 0 , len-1 );
    }
    //区间修改和懒惰标记
    private void update( int low, int high, int change, int root, int lowOfRoot, int highOfRoot )
    {
        if( low <= lowOfRoot && highOfRoot <= high )
        {
            arr[root] += change*(highOfRoot-lowOfRoot+1);
            sign[root] += root;
            return;
        }

        int mid = ((lowOfRoot+highOfRoot)>>1);
        if( sign[root]!=0 && lowOfRoot!=highOfRoot )
        {
            arr[root*2] += sign[root]*(mid-lowOfRoot+1);
            arr[root*2+1] += sign[root]*(high-mid-1+1);
            sign[root*2] += sign[root];
            sign[root*2+1] += sign[root];
            sign[root] = 0;
        }

        if( mid >= low )
            update( low , high , change , root*2 , lowOfRoot , mid );
        if( mid+1 <= high )
            update( low , high , change , root*2+1 , mid+1 , highOfRoot );

        arr[root] = arr[root*2] + arr[root*2+1];

    }
    public int getSum( int low , int high )
    {
        return getSum( low , high , 1 , 0 , len-1 );
    }
    //区间求和
    private int getSum( int low , int high , int root , int lowOfRoot , int highOfRoot )
    {
        //如果当前根节点表示的区间是待查询区间的子集  返回value
        if( lowOfRoot>=low && highOfRoot<=high )
        {
            return arr[root];
        }
        else
        {
            int mid = ((lowOfRoot+highOfRoot)>>1);
            if( sign[root]!=0 && lowOfRoot != highOfRoot )
            {
                arr[root*2] += sign[root]*(mid-lowOfRoot+1);
                arr[root*2+1] += sign[root]*(highOfRoot-mid-1+1);
                sign[root*2] += sign[root];
                sign[root*2+1] += sign[root];
                sign[root] = 0;
            }
            int res = 0;
            if( mid >= low )
                res += getSum(low,high,root*2,lowOfRoot,mid);
            if( mid+1<=high )
                res += getSum(low , high , root*2+1 , mid+1 , highOfRoot);
            return res;
        }
    }
}