307. Range Sum Query - Mutable

Problem

Tags: Array, Design, Binary Indexed Tree, Segment Tree

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 * 10^4
• -100 <= nums[i] <= 100
• 0 <= index < nums.length
• -100 <= val <= 100
• 0 <= left <= right < nums.length
• At most 3 * 10^4 calls will be made to update and sumRange.

Code

JS

// 307. Range Sum Query - Mutable (5/11/53433)
// Runtime: 588 ms (86.18%) Memory: 71.32 MB (94.31%) 

// lowbit: x 化為二進位後只保留最右邊的 1 的數
function lowbit(x) {
    return x & (-x);
}

// 二元索引樹 (Binary Indexed Tree) 
class BIT {
    constructor(nums) {
        this.val = new Array(nums.length + 1).fill(0);
        for(let i = 0; i < nums.length; i++) this.update(i + 1, nums[i]);
    }
    
    update(index, delta) {
        while (index < this.val.length) {
            this.val[index] += delta;
            index += lowbit(index);
        }
    }
    
    query(index) {
        let sum = 0;
        while (index > 0) {
            sum += this.val[index];
            index -= lowbit(index);
        }
        return sum;
    }
}

class NumArray {
    constructor(nums) {
        this.nums = nums;
        this.bit = new BIT(nums);
    }
    
    update(index, value) {
        this.bit.update(index + 1, value - this.nums[index]);
        this.nums[index] = value;
    }
    
    sumRange(left, right) {
        return this.bit.query(right + 1) - this.bit.query(left);
    }
}