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.
[Analysis]
By using brute force on array itself, the update() can be achieved in O(1) and the sumRange() in O(N). It is not optimal when sumRange() to be called more often.
An alternative way is to use Segment Tree. The Segment Tree is heap like data structure. Both update() and sumRange() can be achieved in O(LogN). Extra O(N) space is used though.
Another range sum problem is "Count of Range Sum".
[Solution]
//
//-- Segment Tree --
//
class NumArray {
vector<int> seg;
int n;
public:
NumArray(vector<int> &nums) {
n = nums.size();
seg.resize(n<<1);
for (int i=n; i< (n<<1); i++) seg[i] = nums[i-n];
for(int i=n-1; i>0; i--) seg[i] = seg[i<<1] + seg[i<<1|1];
}
void update(int i, int val) {
int diff = val-seg[i+n];
for( i+=n; i>0; i>>=1 )
seg[i] += diff;
}
int sumRange(int i, int j) {
int res=0;
for (i+=n, j+=n; i<=j; i>>=1, j>>=1) {
if (i&1) res+=seg[i++];
if (!(j&1)) res+=seg[j--];
}
return res;
}
};
