Alibi

My Life is Getting Better

Leetcode[307] Range Sum Query - Mutable

08 Dec 2015

###Task1 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:

The array is only modifiable by the update function. You may assume the number of calls to update and sumRange function is distributed evenly.

###Java

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

    public NumArray(int[] nums) {
        this.nums = nums;
        int sum = 0;
        int lowbit;
        tree = new int[nums.length + 1];
        for (int i = 1; i < tree.length; i++) {
            sum = 0;
            lowbit = i & (-i);
            for (int j = i; j > i - lowbit; j--) {
                sum += nums[j - 1];
            }
            tree[i] = sum;
        }
    }

    void update(int i, int val) {
        int diff = val - nums[i];
        nums[i] = val;
        i++;
        for (; i < tree.length; i += (i & (-i))) {
            tree[i] += diff;
        }
    }

    public int sumRange(int i, int j) {
        return getSum(j) - getSum(i - 1);
    }
    
    public int getSum(int i) {
        int sum = 0;
        i++;
        while (i > 0) {
            sum += tree[i];
            i -= (i & (-i));
        }
        return sum;
    }
}


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

###Points

Related Posts