Algorithm
Problem Name: 307. 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
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 = 8
Constraints:
1 <= nums.length <= 3 * 104-100 <= nums[i] <= 1000 <= index < nums.length-100 <= val <= 1000 <= left <= right < nums.length- At most
3 * 104calls will be made toupdateandsumRange.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class NumArray {
public:
NumArray(vector<int> nums) {
this->nums = nums;
}
void update(int i, int val) {
nums[i] = val;
}
int sumRange(int i, int j) {
int sum = 0;
for(int a = i; a < = j; a++) sum += nums[a];
return sum;
}
private:
vector<int> nums;
};
// Segment Tree
class NumArray {
struct SegmentTreeNode{
int start;
int end;
int sum;
SegmentTreeNode* left;
SegmentTreeNode* right;
SegmentTreeNode(int l, int r):start(l), end(r), sum(0), left(NULL), right(NULL){}
};
SegmentTreeNode* root;
SegmentTreeNode* buildTree(vector<int>& nums, int start, int end){
if(start > end) return NULL;
SegmentTreeNode* p = new SegmentTreeNode(start, end);
if(start == end){
p->sum = nums[start];
}
else{
int mid = start + (end - start) / 2;
p->left = buildTree(nums, start, mid);
p->right = buildTree(nums, mid + 1, end);
p->sum = p->left->sum + p->right->sum;
}
return p;
}
void update(SegmentTreeNode* p, int i, int val){
if(p->start == i && p->end == i){
p->sum = val;
}
else{
int mid = p->start + (p->end - p->start) / 2;
if(i <= mid> update(p->left, i, val);
else update(p->right, i, val);
p->sum = p->left->sum + p->right->sum;
}
}
int sumRange(SegmentTreeNode* p, int i, int j){
if(p->start == i && p->end == j){
return p->sum;
}
int mid = p->start + (p->end - p->start) / 2;
if(j <= mid>
return sumRange(p->left, i, j);
else if(i > mid)
return sumRange(p->right, i, j);
else
return sumRange(p->left, i, mid) + sumRange(p->right, mid + 1, j);
}
public:
NumArray(vector<int> nums) {
root = buildTree(nums, 0, nums.size() - 1);
}
void update(int i, int val) {
update(root, i, val);
}
int sumRange(int i, int j) {
return sumRange(root, i, j);
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(i,val);
* int param_2 = obj.sumRange(i,j);
*/
class NumArray {
struct TreeNode {
int start;
int end;
int sum;
TreeNode* left;
TreeNode* right;
TreeNode(int x, int y):start(x), end(y), sum(0), left(NULL), right(NULL) {}
};
public:
NumArray(vector<int> nums) {
root = buildTree(nums, 0, nums.size() - 1);
}
void update(int i, int val) {
dfs(root, i, val);
}
int sumRange(int i, int j) {
return i == 0 ? getSum(root, j) : getSum(root, j) - getSum(root, i - 1);
}
int getSum(TreeNode* root, int idx) {
if (root->end == idx) {
return root->sum;
}
int mid = root->start + (root->end - root->start)/2;
if (idx <= mid> {
return getSum(root->left, idx);
} else {
return root->left->sum + getSum(root->right, idx);
}
}
void dfs(TreeNode* root, int i, int val) {
if (root->start == i && root->end == i) {
root->sum = val;
return;
}
int mid = root->start + (root->end - root->start)/2;
if (i < = mid) {
dfs(root->left, i, val);
} else {
dfs(root->right, i, val);
}
root->sum = root->left->sum + root->right->sum;
}
TreeNode* buildTree(vector<int>& nums, int start, int end) {
if (start > end) {
return NULL;
}
if (start == end) {
TreeNode* node = new TreeNode(start, end);
node->sum = nums[start];
return node;
}
TreeNode* node = new TreeNode(start, end);
int mid = start + (end - start)/2;
node->left = buildTree(nums, start, mid);
node->right = buildTree(nums, mid + 1, end);
node->sum = node->left->sum + node->right->sum;
return node;
}
private:
TreeNode* root;
};
Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]
#2 Code Example with Java Programming
Code -
Java Programming
class NumArray {
private BIT bit;
private int[] nums;
public NumArray(int[] nums) {
this.bit = new BIT(nums.length);
this.nums = nums;
for (int i = 0; i < nums.length; i++) {
this.bit.update(i + 1, nums[i]);
}
}
public void update(int index, int val) {
int delta = val - nums[index];
this.bit.update(index + 1, delta);
this.nums[index] = val;
}
public int sumRange(int left, int right) {
return this.bit.query(right + 1) - this.bit.query(left);
}
private static class BIT {
private int[] sum;
public BIT(int n) {
this.sum = new int[n + 1];
}
private void update(int idx, int delta) {
while (idx < sum.length) {
sum[idx] += delta;
idx += (idx & -idx);
}
}
private int query(int idx) {
int result = 0;
while (idx > 0) {
result += sum[idx];
idx -= (idx & -idx);
}
return result;
}
}
}
Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const NumArray = function(nums) {
this.arr = nums
};
NumArray.prototype.update = function(i, val) {
this.arr[i] = val
};
NumArray.prototype.sumRange = function(i, j) {
let sum = 0;
for (let k = i; k < = j; k++) {
sum += this.arr[k];
}
return sum;
};
Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]
#4 Code Example with Python Programming
Code -
Python Programming
class NumArray:
def __init__(self, nums):
if nums:
self.n = len(nums)
self.tree = [0] * (2 * (2 ** int(math.ceil(math.log(self.n, 2)))) - 1)
def dfs(node, s, e):
if s == e: self.tree[node] = nums[s]
else:
m = (s + e) // 2
dfs(2 * node + 1, s, m)
dfs(2 * node + 2, m + 1, e)
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
dfs(0, 0, self.n - 1)
def update(self, i, val):
def dfs(node, s, e, idx, val):
if s == e: self.tree[node] = val
else:
m = (s + e) // 2
if s <= idx <= m: dfs(2 * node + 1, s, m, idx, val)
else: dfs(2 * node + 2, m + 1, e, idx, val)
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
dfs(0, 0, self.n - 1, i, val)
def sumRange(self, i, j):
def dfs(node, s, e, l, r):
if r < s or l > e: return 0
if l <= s and e <= r: return self.tree[node]
m = (s + e) // 2
return dfs(2 * node + 1, s, m, l, r) + dfs(2 * node + 2, m + 1, e, l, r)
return dfs(0, 0, self.n - 1, i, j)
Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]