307 Range Sum Query - Mutable

這題是Google出題率蠻高的308 Range Sum Query 2D - Mutable的簡單版。

Input是一個1D int array，和一個integer pair，代表array的起始index和終止index。目標是要算出起始index和中止index之間(inclusive)所有element的總和。

程式分成三個部分：Constructor, update, sumRange。

update讓我們可以更改input array的內容，sumRange讓我們可以算出範圍內的總和。

int sum = 0;

for(int idx = i; idx <= j; idx++)
    sum+=input[i];

這樣的時間複雜度是O(n)

為了再降低時間複雜度，學了一個新的資料結構：Binary indexed tree，有一篇很好的教學可以參考。

宣告全域變數：

int[] tree 儲存binary indexed tree中每個node的值

int[] numsCopy 儲存input array

1) public NumArray(int[] nums)

初始化tree和numsCopy，需注意nums[]固定由0開始，而binary indexed tree的第0個element是0，從1開始放值，為了配合bit operation，numsCopy也要和tree一樣從1開始。

tree[idx] = numsCopy[idx-2^r+1]+...+numsCopy[idx]

r表示idx的binary expression中最後一個1後面的0的數量

實作上先new出nums.length+1的空間（第0格的值定為0）給tree和numsCopy，並用for迴圈從1跑到nums.length+1，每個迴圈中先給定numsCopy[idx]=nums[idx-1]，再進入第二層while迴圈從numsCopy[idx-2^r+1]一直累加到numsCopy[idx]存入tree[idx]。

2) void update(int i, int value)

因為nums[i]已經更新為val，必須更新有使用到nums[i]的tree node。

當tree[i]有用到nums[i]，它的ancestor就也有用到nums[i]，所以必須找出這些tree[i]所有的ancestor並更新。找到ancestor的方法為：idx = i, idx = i+(i&-i), ... 直到idx超過nums.length，根據binary indexed tree的定義，tree[i]的parent即為tree[i+(i&-i)]。

實作上先宣告變數int diff = val - numsCopy[i+1]。用for迴圈從j=i跑到tree.length，j+= j&-j，迴圈中tree[j]+=diff。

最後把numsCopy[i+1]的值更新為value。

3) int sumRange(int i, int j)

sumRange要計算 nums[i] + nums[i+1] + … + nums[j], 我們可以用cumulative[j]-cumulative[i-1]得到這個和。

如何利用binary indexed tree得到cumulative[j]和cumulative[i-1]?

舉例來說，13(1101)是三個區間的和：[1101,1101], [1001,1100], [0001,1000]，分別是tree[13], tree[12], tree[8]內存的值。

1101 - (1101 & -1101) = 1101 - 1 = 1100 -> 12

1100 - (1100 & -1100) = 1100 - 100 =1000 -> 8

實作上我們要算出cumulative[j]和cumulative[i-1] 最後將兩者相減並return。

cumulative的計算用一個while迴圈來做，在迴圈外宣告一個cumulativeJ=tree[j]，並將idx設為j-(j&-j)，迴圈中cumulativeJ+=tree[idx]，並更新idx為idx-(idx&-idx)。迴圈終止條件設為idx>0。

用了這個方法後，因為是binary search，可以將時間複雜度降到O(logn)。

public class NumArray {
    int[] tree;
    int[] numsCopy;
    public NumArray(int[] nums) {
        /*
        For each i in nums
        Calculate 2^r (by idx & -idx)
        Int i=1
        while(idx-2^r+i<=idx)
        tree[idx]+=nums[idx-2^r+i]
        i++
        */
        tree = new int[nums.length+1];
        numsCopy = new int[nums.length+1];
        for(int idx=1; idx<nums.length+1; idx++){
            numsCopy[idx] = nums[idx-1];
            int r = idx & -idx;
            int i=1;
            while(idx-r+i<=idx){
                tree[idx]+=numsCopy[idx-r+i];
                i++;
            }
        }
    }

    void update(int i, int val) {
        /*
        diff = val - nums[i];
        For int j=i; j<nums.length; j+= j & (-j)
            Tree[j] += diff
        nums[i] = val
        */
        int diff = val - numsCopy[i+1];
        for(int j=i+1; j<numsCopy.length; j+=(j & -j)){
            tree[j] += diff;
        }
        numsCopy[i+1] = val;
    }

    public int sumRange(int i, int j) {
        //cumulative j
        int cumulateJ = tree[j+1];
        int idx = j+1 - ((j+1) & -(j+1));
        while(idx>0){
            cumulateJ += tree[idx];
            idx -= idx & -idx;
        }
        //cumulative i
        int cumulateI = tree[i];
        idx = i - (i & -i);
        while(idx>0){
            cumulateI += tree[idx];
            idx -= idx & -idx;
        }
        return cumulateJ-cumulateI;
    }
}


// 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);

為什麼idx & -idx可以取出idx的最後一位1呢? 舉個例子，如果idx == 0110，那-idx就是1001+0001 == 1010，所以以最後一位1為中心: 1. 他之後的bit一定都是0(因為取負號會+1) 2. 他之前的bit跟原本是反向的，例如原本是01，取負號之後會變成10，&之後一定都是0

所以0110 & 1010 => 0010，可以取出最後一位1。