LeetCode 307. Range Sum Query – Mutable

Problem.

This problem extends to previous 1D range query problem to allow hot update of the values. If we still use the same cache sum approach, we will end up having O(n) on the update operation, since if we update position i, we need to update all the sums from i to the end of the array, which is far from optimal.

Instead, I will utilize a data structure called Binary Indexed Tree to optimize the complexity of update operation to O(logn), with a price of degrading the query operation from O(1) to O(logn).

By the way BIT is one of the data structure I learnt from the topcoder website during my college. It definitely brings back some good memories.

My code:

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

    public NumArray(int[] nums) {
        tree = new int[nums.Length];
        this.nums = nums;
        for(int i = 1; i < nums.Length; i++){
            UpdateDelta(i, nums[i]);
        }
    }
    
    public void UpdateDelta(int idx, int dt) {
        while (idx> 0 && idx < nums.Length){
            tree[idx] += dt;
            idx += (idx & -idx);
        }
    }
    public void Update(int idx, int val) {
        int dt = val - nums[idx];
        UpdateDelta(idx, dt);
        nums[idx] = val;
    }
    
    public int Sum(int idx){
        int sum = 0;
        while (idx > 0){
            sum += tree[idx];
            idx -= (idx & -idx);
        }
        return sum;
    }
    
    public int SumRange(int i, int j) {
        if(i == 0) { return Sum(j) + nums[0]; }
        else { return Sum(j) - Sum(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);
 */

Leave a Reply

Your email address will not be published. Required fields are marked *