LeetCode------Range Sum Query - Mutable

解法一：线段树

关于线段树，详细介绍参见文章：https://blog.csdn.net/DjokerMax/article/details/81941464

package com.zhumq.lianxi;

public class NumArray {
    private SegmentTreeNode root;
    // Time Complexity: O(n)
    //初始建树
    public NumArray(int[] nums) {
        this.root = buildTree(nums, 0, nums.length);
    } 
    // Time Complexity: O(log n)
    void update(int i, int val) {
        updateHelper(this.root, i, val);
    } 
    // Time Complexity: O(log n)
    public int sumRange(int i, int j) {
        return sumRangeHelper(this.root, i, j+1);
    }

    //递归建树
    private static SegmentTreeNode buildTree(int[] nums, int begin, int end) {
        if (nums == null || nums.length == 0 || begin >= end) return null;
        if (begin == end - 1) // one element
            return new SegmentTreeNode(begin, end, nums[begin]);
        final SegmentTreeNode root = new SegmentTreeNode(begin, end);
        final int middle = begin + (end - begin) / 2;
        root.left = buildTree(nums, begin, middle);
        root.right = buildTree(nums, middle, end);
        root.sum = root.left.sum + root.right.sum;
        return root;
    } 

    //递归修改sum值，总共需要修改节点个数为树的高度
    private static void updateHelper(SegmentTreeNode root, int i, int val) {
        if (root.begin == root.end - 1 && root.begin == i) {
            root.sum = val;
            return;
        } 

        final int middle = root.begin + (root.end - root.begin) / 2;

        if (i < middle) {
            updateHelper(root.left, i, val);
        } else {
            updateHelper(root.right, i, val);
        } 

        root.sum = root.left.sum + root.right.sum;
    } 

    //递归获取某个区间的sum值
    private static int sumRangeHelper(SegmentTreeNode root, int begin, int end) {
        //节点为空或者要求的区间完全在当前区间外面则返回0
        if (root == null || begin >=root.end || end <= root.begin) return 0;
        //如果当前区间包含在要求的区间里面，则直接返回当前节点的sum值
        if (begin <= root.begin && end >= root.end)
            return root.sum;
        //分开为左右两区间的中间位置
        final int middle = root.begin + (root.end - root.begin) / 2;
        //递归到左右子树
        //这里一定是Math.min(end,middle)和Math.max(begin,middle)，直接使用middle可能会出错
        return sumRangeHelper(root.left, begin, Math.min(end, middle)) + sumRangeHelper(root.right, Math.max(middle, begin), end);
    } 

    static class SegmentTreeNode {
        private int begin;
        private int end;
        private int sum;
        private SegmentTreeNode left;
        private SegmentTreeNode right;
        public SegmentTreeNode(int begin, int end, int sum) {
            this.begin = begin;
            this.end = end;
            this.sum = sum;
        } 
        public SegmentTreeNode(int begin, int end) {
            this(begin, end, 0);
        }
    }
}

解法二：树状数组

关于线段树，详细介绍参见文章：https://blog.csdn.net/DjokerMax/article/details/81950065

package com.zhumq.lianxi;

public class NumArray2 {
    // Range Sum Query - Mutable
    // Binary Indexed Tree
    private int[] nums;
    private int[] bit;
    // Time Complexity: O(n)
    public NumArray2(int[] nums) {
        // index 0 is unused
        // 下标0没有使用
        this.nums = new int[nums.length + 1];
        this.bit = new int[nums.length + 1];
        for (int i = 0; i < nums.length; ++i) {
            update(i, nums[i]);
        }
    } 

    // Time Complexity: O(log n)
    public void update(int index, int val) {
        final int diff = val - nums[index + 1];
        //区间靠有端点的，并且这里下标实际使用的1~nums.length
        for (int i = index + 1; i < nums.length; i += lowbit(i)) {
            //更新相关的bit[i]
            bit[i] += diff;
        } 
        //最后更新该节点
        nums[index + 1] = val;
    } 

    // Time Complexity: O(log n)
    public int sumRange(int i, int j) {
        //区间靠右端点，通过区间相减来获取某一段区间的和
        return read(j + 1) - read(i);
    } 

    //获取从某个下标开始的后缀和
    private int read(int index) {
        int result = 0;
        for (int i = index; i > 0; i -= lowbit(i)) {
            result += bit[i];
    } 
        return result;
    } 

    private static int lowbit(int x) {
        return x & (-x); // must use parentheses
    }
}