[LeetCode] 307. Range Sum Query - Mutable

https://leetcode.com/problems/range-sum-query-mutable/

Solution:
Will use dynamic programming strategy. Let dp(i) represent the sum of elements from 0 to i-1. Then the sum of elements from i to j inclusively can be expressed as (dp[j+1] - dp[i]). Once one element is changed, all the dp[i] after that elements need to be updated.

Code:

class NumArray {
public:
    NumArray(vector<int> &nums) {
        sum.push_back(0);
        for(auto a:nums) sum.push_back(sum.back() + a);
    }

    void update(int i, int val) {
        if(i<sum.size()-1){
            int t = val - (sum[i+1]-sum[i]);
            for(int j=i+1; j<sum.size(); ++j) sum[j] += t;  
        }
    }

    int sumRange(int i, int j) {
        if(j<sum.size()-1) return sum[j+1]-sum[i];
    }
private:
    vector<int> sum;
};