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.
class NumArray 2 { 3 public: 4 NumArray(vector<int> &nums) 5 { 6 sums.push_back(0); 7 for (int i = 0; i < nums.size(); i++) 8 { 9 sums.push_back(sums[i] + nums[i]); 10 values.push_back(nums[i]); 11 } 12 } 13 14 void update(int i, int val) 15 { 16 int diff = val - values[i]; 17 for (int k = i + 1; k < sums.size(); k++) 18 sums[k] = sums[k] + diff; 19 values[i] = val; 20 } 21 22 int sumRange(int i, int j) 23 { 24 return sums[j + 1] - sums[i]; 25 } 26 private: 27 vector<int> sums; 28 vector<int> values; 29 };