# 307. 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:
- The array is only modifiable by the update function.
- You may assume the number of calls to update and sumRange function is distributed evenly.
# Solution
Approach 1: Accumulated sum.
Approach 2: Segment tree.
Approach 3: Binary index tree.
# Code (Python)
Approach 1:
Approach 2:
# Code (C++)
Approach 1:
// Accumulated sum.
class NumArray {
private:
vector<int> sum;
public:
NumArray(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i)
{
sum.push_back(nums[i]);
if (i > 0)
sum[i] += sum[i-1];
}
}
void update(int i, int val) {
int tmp = sum[i];
if (i > 0)
tmp -= sum[i-1];
int diff = val - tmp;
for (int j = i; j < sum.size(); ++j)
{
sum[j] += diff;
}
}
int sumRange(int i, int j) {
int res = sum[j];
if (i > 0)
res -= sum[i-1];
return res;
}
};
/**
* 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);
*/
Approach 2:
// Segment tree.
class NumArray {
private:
vector<int> tree;
int n;
public:
NumArray(vector<int>& nums) {
n = nums.size();
if (n == 0)
return;
tree = vector<int>(n*2, 0);
for (int i = 0; i < n; ++i)
{
tree[i+n] = nums[i];
}
for (int i = n-1; i > 0; --i)
{
tree[i] = tree[i*2] + tree[i*2+1];
}
}
void update(int i, int val) {
int diff = val - tree[i+n];
tree[i+n] = val;
for (int j = (i+n)/2; j > 0; j /= 2)
{
tree[j] += diff;
}
}
int sumRange(int i, int j) {
int head = i + n;
int tail = j + n;
int sum = 0;
while (head <= tail)
{
if (head % 2 != 0)
{
sum += tree[head];
head++;
}
if (tail % 2 == 0)
{
sum += tree[tail];
tail--;
}
head /= 2;
tail /= 2;
}
return sum;
}
};
Approach 3:
// Binary index tree.
class NumArray {
private:
vector<int> oriNum;
vector<int> bitNum;
public:
NumArray(vector<int> &nums) {
int n = nums.size();
oriNum = vector<int>(n+1, 0);
bitNum = vector<int>(n+1, 0);
for (int i = 0; i < n; ++i) {
update(i, nums[i]);
}
}
void update(int i, int val) {
if (i < 0 || i >= bitNum.size() - 1)
return;
int oldVal = oriNum[i+1];
oriNum[i+1] = val;
int diff = val - oldVal;
for (int j = i+1; j < bitNum.size(); j += j & -j) {
bitNum[j] += diff;
}
}
int getSum(int i) {
if (i < 0 || i >= bitNum.size() - 1)
return 0;
int sum = 0;
for (int j = i+1; j > 0; j -= j & -j) {
sum += bitNum[j];
}
return sum;
}
int sumRange(int i, int j) {
return getSum(j) - getSum(i-1);
}
};