Given an integer array nums, handle multiple queries of the following types:
nums.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] <= 1000 <= index < nums.length-100 <= val <= 1000 <= left <= right < nums.length3 * 104 calls will be made to update and sumRange.class NumArray {
public:
vector <int> tree;
int n;
NumArray(vector<int>& nums) {
if (nums.size()>0){
n = nums.size();
tree.resize(2*n, 0);
buildtree(nums);
}
}
void buildtree(vector<int>& nums){
for(int i=n, j=0; i<2*n; i++, j++) // n to 2n-1 of array `tree`
tree[i] = nums[j];
for(int i=n-1; i>0; --i) // FYI these are parents of n to 2n-1
tree[i] = tree[2*i] + tree[2*i+1]; // 0 to n-1 of array `tree`
}
void update(int index, int val) {
index+=n; //update the i b/w n & 2n-1
tree[index]=val;
// now the tough part... update all nodes in whom
// the changed node had contribution
while(index>0){
int lt = index, rt = index;
if (index%2)
lt = index-1;
else rt = index+1;
tree[index/2] = tree[lt] + tree[rt]; //update parent after child
index/=2; // now do their parents (grandparents of leaves & so on)
}
}
int sumRange(int lt, int rt) {
// get the lt & rt leaves & then traverse upwards the tree
lt += n;
rt += n;
int sum = 0;
while (lt<=rt){
if(lt%2){ // lt is odd => lt is rt child of it parent
// => its parent has the lt child's value surplus
sum+=tree[lt]; // just add up reqd val in sum counter
lt++; // and then set lt ptr to child node to its rt
}
if(!(rt%2)){ // rt is even => rt is lt child of it parent
// => its parent has the rt child's value surplus
sum+=tree[rt]; // just add up reqd val in sum counter
rt--; // and then set rt ptr to child node to its lt
}
// at this point both lt & rt ptr are pointing to such leaves such that just finding their common parent will do the reqd task
lt/=2;
rt/=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);
*/