307. Range Sum Query - Mutable

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.

303.Range Sum Query - Immutable的follow-up，如果nums array的elements被更改得很頻繁，建立binary index tree來儲存計算range sum會使得update和query都是O(logn) time complexity。

參考GeeksForGeeks的Binary Index Tree/Fenwick Tree教學。

Binary Index Tree比Segment Tree省空間且相對容易implement。

BIT的size是input nums array的長度+1，BIT[0]是一個dummy node。

概念源自所有正整數都可以表示為power of 2的數的總和。 e.g. 19 = 2^4 + 2^1 + 2^0

BIT裡的每個node存的數是n個數的和，n為power of 2。

n & -n 是為了取rightmost bit。

// Binary Index Tree
class NumArray {
public:
    NumArray(vector<int> nums) : BIT(nums.size() + 1, 0) {
        for (int i = 0; i < nums.size(); ++i) {
            int val = nums[i];
            int index = i + 1;
            while (index < BIT.size()) {
                BIT[index] += val;
                index += (index & -index);
            }
        }
    }
    
    int getSum(int i) {
        int sum = 0;
        int index = i + 1;
        while (index > 0) {
            sum += BIT[index];
            index -= (index & -index);
        }
        return sum;
    }
    
    void update(int i, int val) { // time: O(logn)
        int orig = getSum(i) - getSum(i - 1);
        int diff = val - orig;
        int index = i + 1;
        while (index < BIT.size()) {
            BIT[index] += diff;
            index += (index & -index);
        }
    }
    
    int sumRange(int i, int j) { // time: O(logn)
        return getSum(j) - getSum(i - 1);
    }
    vector<int> BIT;
};

307. Range Sum Query - Mutable