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

  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

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