RangeSumQueryMutable.cpp

// Source : https://leetcode.com/problems/range-sum-query-mutable/
// Author : Hao Chen
// Date   : 2015-11-24

/*************************************************************************************** 
 *
 * 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.
 *
 ***************************************************************************************/


// The following idea is using `Binary Index Tree`
// There are two articles explaine this technique quite well:
// 1) http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
// 2) http://cs.stackexchange.com/questions/10538/bit-what-is-the-intuition-behind-a-binary-indexed-tree-and-how-was-it-thought-a

class NumArray {
private:
    int _sz;
    vector<int> _nums;
    vector<int> _sums;    
public:
    NumArray(vector<int> &nums)  {
        _sz = nums.size();
        _nums.resize(_sz+1, 0);
        _sums.resize(_sz+1, 0);
        for(int i=0; i< _sz; i++) {
            update(i, nums[i]);          
        }
    }

    void update(int i, int val) {
        int oldv = _nums[i+1];
        for(int idx = i+1; idx <= _sz; idx += (idx & (-idx))  ) {
            _sums[idx] = _sums[idx] - oldv + val;
        }
        _nums[i+1] = val;
    }

    int sumRange(int i, int j) {
        return sumRange(j+1) - sumRange(i);
    }
    
    int sumRange(int i) {
        int ret = 0;
        for(int idx=i; idx>0; idx -= (idx & (-idx)) ) {
            ret += _sums[idx];
        }
        return ret;
    }
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);