https://leetcode.com/problems/range-sum-query-mutable/
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 nums between indices left and right **inclusive** where left <= right.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 elements of nums between indices left and right **inclusive** (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 = 8
Constraints:
1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
At most 3 * 104 calls will be made to update and sumRange.
- code
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];
}
void update(int pos, int val) {
pos += n;
tree[pos] = val;
while (pos > 0) {
int left = pos;
int right = pos;
if (pos % 2 == 0) {
right = pos + 1;
} else {
left = pos - 1;
}
// parent is updated after child is updated
tree[pos / 2] = tree[left] + tree[right];
pos /= 2;
}
}
public int sumRange(int l, int r) {
// get leaf with value 'l'
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;
}
}
- code
public class NumArray {
int[] tree;
int n;
public NumArray(int[] nums) {
n = nums.length;
tree = new int[n << 1];
buildTree(nums);
}
private void buildTree(int[] nums) {
for (int i = n; i < n << 1; i++) {
tree[i] = nums[i - n];
}
for (int i = n - 1; i > 0; i--) {
tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
}
void update(int i, int val) {
for (tree[i += n] = val; i > 0; i >>= 1) {
tree[i >> 1] = tree[i] + tree[i ^ 1];
}
}
public int sumRange(int i, int j) {
int ret = 0;
for (i += n, j += n; i <= j; i >>= 1, j >>= 1) {
if ((i & 1) == 1) ret += tree[i++];
if ((j & 1) == 0) ret += tree[j--];
}
return ret;
}
}