LeetCode Q307: Range Sum Query - Mutable

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:

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

Solution:

	class NumArray {
	public:
	NumArray(vector<int> &_nums) {
	if(_nums.empty())
	return;
	nums=_nums;
	numSum.resize(nums.size(), 0);
	numSum[0]=nums[0];
	for(int i=1; i<nums.size(); i++)
	numSum[i] = nums[i]+numSum[i-1];
	}
	void update(int i, int val) {
	int diff = val - nums[i];
	nums[i]=val;
	for(; i<nums.size(); i++)
	numSum[i]=numSum[i]+diff;
	}
	int sumRange(int i, int j) {
	if(j<i)
	return 0;
	if(i==0)
	return numSum[j];
	else{
	return numSum[j]-numSum[i-1];
	}
	}
	vector<int> numSum;
	vector<int> nums;
	};
	// 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);

view raw Q307.cpp hosted with ❤ by GitHub

Round 2 solution:
Using binary indexed tree. Be careful, the index of binary indexed tree starts from 1 not 0.

	class NumArray {
	public:
	NumArray(vector<int> &_nums) {
	nums=_nums;
	bits.resize(nums.size()+1, 0);
	for(int i=1; i<bits.size(); i++){
	int j = i;
	while(j<bits.size()){
	bits[j]+=nums[i-1];
	j += j&-j;
	}
	}
	}
	void update(int i, int val) {
	val = val-nums[i];
	nums[i]=nums[i]+val;
	i++;
	while(i<bits.size()){
	bits[i]+=val;
	i += i&-i;
	}
	}
	int getSum(int i){
	int sum = 0;
	while(i>0){
	sum+=bits[i];
	i -= i&-i;
	}
	return sum;
	}
	int sumRange(int i, int j) {
	int sum1 = getSum(i);
	int sum2 = getSum(j+1);
	return sum2-sum1;
	}
	vector<int> bits;
	vector<int> nums;
	};
	// 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);

view raw Q307Rnd2.cpp hosted with ❤ by GitHub