307. Range Sum Query Mutable - jiejackyzhang/leetcode-note GitHub Wiki

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

解题思路为segment tree。

public class NumArray {
    
    int[] tree;
    int len;

    public NumArray(int[] nums) {
        len = nums.length;
        tree = new int[len * 2];
        buildTree(nums);
    }
    
    private void buildTree(int[] nums) {
        for(int i = len; i < len * 2; i++) {
            tree[i] = nums[i-len];
        }
        for(int i = len-1; i > 0; i--) {
            tree[i] = tree[2*i] + tree[2*i+1];
        }
    }

    void update(int i, int val) {
        int pos = i + len;
        int diff = val - tree[pos];
        while(pos > 0) {
            tree[pos] += diff;
            pos /= 2;
        }
    }

    public int sumRange(int i, int j) {
        int sum = 0;
        int left = i + len, right = j + len;
        while(left <= right) {
            if(left % 2 == 1) {
                sum += tree[left];
                left++;
            }
            if(right % 2 == 0) {
                sum += tree[right];
                right--;
            }
            left /= 2;
            right /= 2;
        }
        return sum;
    }
}


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);