Range Sum Query - Mutable - Medium - L - Star
Published:
Question
- https://leetcode.com/problems/range-sum-query-mutable/
Given an array nums and two types of queries where you should update the value of an index in the array, and retrieve the sum of a range in the array.
Implement the NumArray class:
NumArray(int[] nums) initializes the object with the integer array nums. void update(int index, int val) updates the value of nums[index] to be val. int sumRange(int left, int right) returns the sum of the subarray nums[left, right] (i.e., nums[left] + nums[left + 1], …, nums[right]).
Approach
- Naive
- Square Root Decomposition **
- Segment Tree **
Solution
class NumArray {
int[] tree;
int n;
public NumArray(int[] nums) {
if (nums.length > 0) {
n = nums.length;
tree = new int[n * 2];
buildTree(nums);
}
}
private void buildTree(int[] nums) {
for (int i = n, j = 0; i < 2 * n; i++, j++)
tree[i] = nums[j];
for (int i = n - 1; i > 0; --i)
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
public void update(int index, int val) {
index += n;
tree[index] = val;
while (index > 0) {
int left = index;
int right = index;
if (index % 2 == 0) {
right = index + 1;
} else {
left = index - 1;
}
// parent is updated after child is updated
tree[index / 2] = tree[left] + tree[right];
index /= 2;
}
}
public int sumRange(int left, int right) {
// get leaf with value 'l'
int l = left;
int r = right;
l += n;
// get leaf with value 'r'
r += n;
int sum = 0;
while (l <= r) {
if ((l % 2) == 1) {
sum += tree[l];
l++;
}
if ((r % 2) == 0) {
sum += tree[r];
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
}
/**
* 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);
*/