0307. Range Sum Query - Mutable

https://leetcode.com/problems/range-sum-query-mutable

Description

Given an integer array nums, handle multiple queries of the following types:

1. Update the value of an element in nums.

2. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

• NumArray(int[] nums) Initializes the object with the integer array nums.

• void update(int index, int val) Updates the value of nums[index] to be val.

• int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

**Input**
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
**Output**
[null, 9, null, 8]
**Explanation**
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

Constraints:

• 1 <= nums.length <= 3 * 104

• -100 <= nums[i] <= 100

• 0 <= index < nums.length

• -100 <= val <= 100

• 0 <= left <= right < nums.length

• At most 3 * 104 calls will be made to update and sumRange.

ac1: Binary Indexed Tree

careful: bit.length = nums.length + 1; so need to do i++ in methods

class NumArray {
    int[] bit;
    int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        bit = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            nums[i] = 0;
            update(i, val);
        }
    }

    public void update(int i, int val) {
        // index + last '1' bit 
        int diff = val - nums[i];
        nums[i] = val;

        i++;
        while (i < bit.length) {
            bit[i] += diff;
            i += i & (-i);
        }
    }

    private int getSum(int i) {
        // index - last '1' bit 
        i++;
        int res = 0;
        while (i > 0) {
            res += bit[i];
            i -= i & (-i);
        }
        return res;
    }

    public int sumRange(int i, int j) {
        return getSum(j) - getSum(i-1);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

ac2: Segment Tree

more intuitive, yet more code. Notice: use divide and conquer, no need to care about the mid point unless building the tree.

class NumArray {

    class SegTreeNode{
        int start, end, sum;
        SegTreeNode left, right;
        public SegTreeNode(int start, int end){
            this.start = start;
            this.end = end;
            sum = 0;
        }
    }

    SegTreeNode root;

    public NumArray(int[] nums) {
        root = build(nums, 0, nums.length-1);
    }
    private SegTreeNode build(int[] nums, int start, int end) {
        if (start < 0 || end >= nums.length || start > end) return null;

        int mid = start + (end - start) / 2;
        SegTreeNode node = new SegTreeNode(start, end);
        if (start == end) {
            node.sum = nums[start];
        } else {
            node.left = build(nums, start, mid);
            node.right = build(nums, mid+1, end);
            node.sum = node.left.sum + node.right.sum;
        }
        return node;
    }

    public void update(int i, int val) {
        update(root, i, val);
    }
    private void update(SegTreeNode root, int i, int val) {
        if (i < root.start || i > root.end) return; // out of range
        if (root.start == root.end) {
            root.sum = val; // leaf, sum = nums[i]
            return;
        }

        // divide and conquer
        update(root.left, i, val);
        update(root.right, i, val);
        root.sum = root.left.sum + root.right.sum;  
    }

    public int sumRange(int i, int j) {
        return sumRange(root, i, j);
    }
    private int sumRange(SegTreeNode root, int i, int j) {
        if (i > root.end || j < root.start) return 0; // out of range
        if (i <= root.start && root.end <= j) return root.sum;  // current node within range, return value

        // divide and conquer
        int res = 0;
        res += sumRange(root.left, i, j);
        res += sumRange(root.right, i, j);
        return res;
    }

}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */