0300 - 0399
0307 - Range Sum Query - Mutable (Medium)
Problem Link
https://leetcode.com/problems/range-sum-query-mutable/
Problem Statement
Given an integer array nums, handle multiple queries of the following types:
- Update the value of an element in
nums. - Calculate the sum of the elements of
numsbetween indicesleftandrightinclusive whereleft <= right.
Implement the NumArray class:
NumArray(int[] nums)Initializes the object with the integer arraynums.void update(int index, int val)Updates the value ofnums[index]to beval.int sumRange(int left, int right)Returns the sum of the elements ofnumsbetween indicesleftandrightinclusive (i.e.nums[left] + nums[left + 1] + ... + nums[right]).
Example 1:
Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]
Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2); // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8Constraints:
1 <= nums.length <= 3 * 10^4-100 <= nums[i] <= 1000 <= index < nums.length-100 <= val <= 1000 <= left <= right < nums.length- At most
3 * 10^4calls will be made toupdateandsumRange.
Approach 1: Segment Tree
struct segtree {
vector<long long> sums;
int size;
void init(int n) {
size = 1;
while (size < n) size *= 2;
sums.assign(size * 2, 0LL);
}
void set(int i, int v, int x, int lx, int rx) {
if (rx - lx == 1) {
sums[x] = v;
return;
}
int m = (lx + rx) / 2;
if (i < m) {
set(i, v, 2 * x + 1, lx, m);
} else {
set(i, v, 2 * x + 2, m, rx);
}
sums[x] = sums[2 * x + 1] + sums[2 * x + 2];
}
void set(int i, int v) {
set(i, v, 0, 0, size);
}
long long sum(int l, int r, int x, int lx, int rx) {
// no intersection
if (lx >= r || l >= rx) return 0;
// inside
if (lx >= l && rx <= r) return sums[x];
int m = (lx + rx) / 2;
long long s1 = sum(l, r, 2 * x + 1, lx, m);
long long s2 = sum(l, r, 2 * x + 2, m, rx);
return s1 + s2;
}
long long sum(int l, int r) {
return sum(l, r, 0, 0, size);
}
};
class NumArray {
public:
NumArray(vector<int>& nums) {
n = nums.size();
st.init(n);
for (int i = 0; i < n; i++) {
st.set(i, nums[i]);
}
}
void update(int index, int val) {
st.set(index, val);
}
int sumRange(int left, int right) {
return st.sum(left, right + 1);
}
private:
segtree st;
int n;
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* obj->update(index,val);
* int param_2 = obj->sumRange(left,right);
*/