使用线段树(SegmentTree)求解区间和

import java.util.Arrays;

public class SegmentTree {
    int[] nums;
    int n;
    int[] st;

    public SegmentTree(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        this.st = new int[2 * n];// segment tree 的size是nums的2倍即可
        init();
    }

    void init() {
//        for (int i = n; i < n * 2; i++) {
//            st[i] = nums[i - n];
//        }
        System.arraycopy(nums, 0, st, n, n);
        for (int i = n - 1; i > 0; i--) {
            st[i] = st[i << 1] + st[(i << 1) | 1]; // 因为 (i << 1) 永远是偶数，所以 (i << 1) | 1 = (i << 1) + 1
            // st[i << 1] 和 st[(i << 1) | 1] 分别表示左右孩子
        }
    }

    void update(int i, int val) {
        i += n; // 转成st的下标
        st[i] = val; // 更新叶子
        while (i > 0) {
            // st[i ^ 1] 表示 st[i] 的兄弟
            st[i >> 1] = st[i] + st[i ^ 1];
            i >>= 1;
        }
    }

    /**
     * 计算nums数组left到right的和
     *
     * @param left  nums的下标，从0开始
     * @param right nums的下标，从0开始
     * @return
     */
    int between(int left, int right) {
        // 转成到st的下标
        left += n;
        right += n;

        int res = 0;
        while (left <= right) {
            if ((left & 1) == 1) res += st[left++]; // st[left]是右子节点(索引是奇数)
            if ((right & 1) == 0) res += st[right--]; // st[right]是左子节点(索引是偶数)

            left >>= 1;
            right >>= 1;
        }

        return res;
    }

    // test code below

    public static void main(String[] args) {
        int[] input = new int[10];
        Arrays.fill(input, 1);

        SegmentTree segTree = new SegmentTree(input);

        segTree.update(4, 1);
        segTree.update(9, 10);

        System.out.println(segTree.st.length);
        System.out.println("=============");
        System.out.println(segTree.between(1, 2));
        System.out.println(segTree.between(3, 5));
        System.out.println(segTree.between(3, 9));
        System.out.println(segTree.between(0, 9));
    }
}