304 North Cardinal St.
Dorchester Center, MA 02124

# Range Sum Query – Mutable LeetCode Solution

## Problem – Range Sum Query – Mutable LeetCode Solution

Given an integer array `nums`, handle multiple queries of the following types:

1. Update the value of an element in `nums`.
2. 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`.

## Range Sum Query – Mutable LeetCode Solution in Java

``````public class NumArray {

class SegmentTreeNode {
int start, end;
SegmentTreeNode left, right;
int sum;

public SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
this.left = null;
this.right = null;
this.sum = 0;
}
}

SegmentTreeNode root = null;

public NumArray(int[] nums) {
root = buildTree(nums, 0, nums.length-1);
}

private SegmentTreeNode buildTree(int[] nums, int start, int end) {
if (start > end) {
return null;
} else {
SegmentTreeNode ret = new SegmentTreeNode(start, end);
if (start == end) {
ret.sum = nums[start];
} else {
int mid = start  + (end - start) / 2;
ret.left = buildTree(nums, start, mid);
ret.right = buildTree(nums, mid + 1, end);
ret.sum = ret.left.sum + ret.right.sum;
}
return ret;
}
}

void update(int i, int val) {
update(root, i, val);
}

void update(SegmentTreeNode root, int pos, int val) {
if (root.start == root.end) {
root.sum = val;
} else {
int mid = root.start + (root.end - root.start) / 2;
if (pos <= mid) {
update(root.left, pos, val);
} else {
update(root.right, pos, val);
}
root.sum = root.left.sum + root.right.sum;
}
}

public int sumRange(int i, int j) {
return sumRange(root, i, j);
}

public int sumRange(SegmentTreeNode root, int start, int end) {
if (root.end == end && root.start == start) {
return root.sum;
} else {
int mid = root.start + (root.end - root.start) / 2;
if (end <= mid) {
return sumRange(root.left, start, end);
} else if (start >= mid+1) {
return sumRange(root.right, start, end);
}  else {
return sumRange(root.right, mid+1, end) + sumRange(root.left, start, mid);
}
}
}
}
``````

## Range Sum Query – Mutable LeetCode Solution in Python

``````"""
The idea here is to build a segment tree. Each node stores the left and right
endpoint of an interval and the sum of that interval. All of the leaves will store
elements of the array and each internal node will store sum of leaves under it.
Creating the tree takes O(n) time. Query and updates are both O(log n).
"""

#Segment tree node
class Node(object):
def __init__(self, start, end):
self.start = start
self.end = end
self.total = 0
self.left = None
self.right = None

class NumArray(object):
def __init__(self, nums):
"""
initialize your data structure here.
:type nums: List[int]
"""
#helper function to create the tree from input array
def createTree(nums, l, r):

#base case
if l > r:
return None

#leaf node
if l == r:
n = Node(l, r)
n.total = nums[l]
return n

mid = (l + r) // 2

root = Node(l, r)

#recursively build the Segment tree
root.left = createTree(nums, l, mid)
root.right = createTree(nums, mid+1, r)

#Total stores the sum of all leaves under root
#i.e. those elements lying between (start, end)
root.total = root.left.total + root.right.total

return root

self.root = createTree(nums, 0, len(nums)-1)

def update(self, i, val):
"""
:type i: int
:type val: int
:rtype: int
"""
#Helper function to update a value
def updateVal(root, i, val):

#Base case. The actual value will be updated in a leaf.
#The total is then propogated upwards
if root.start == root.end:
root.total = val
return val

mid = (root.start + root.end) // 2

#If the index is less than the mid, that leaf must be in the left subtree
if i <= mid:
updateVal(root.left, i, val)

#Otherwise, the right subtree
else:
updateVal(root.right, i, val)

#Propogate the changes after recursive call returns
root.total = root.left.total + root.right.total

return root.total

return updateVal(self.root, i, val)

def sumRange(self, i, j):
"""
sum of elements nums[i..j], inclusive.
:type i: int
:type j: int
:rtype: int
"""
#Helper function to calculate range sum
def rangeSum(root, i, j):

#If the range exactly matches the root, we already have the sum
if root.start == i and root.end == j:
return root.total

mid = (root.start + root.end) // 2

#If end of the range is less than the mid, the entire interval lies
#in the left subtree
if j <= mid:
return rangeSum(root.left, i, j)

#If start of the interval is greater than mid, the entire inteval lies
#in the right subtree
elif i >= mid + 1:
return rangeSum(root.right, i, j)

#Otherwise, the interval is split. So we calculate the sum recursively,
#by splitting the interval
else:
return rangeSum(root.left, i, mid) + rangeSum(root.right, mid+1, j)

return rangeSum(self.root, i, j)

# Your NumArray object will be instantiated and called as such:
# numArray = NumArray(nums)
# numArray.sumRange(0, 1)
# numArray.update(1, 10)
# numArray.sumRange(1, 2)``````

## Range Sum Query – Mutable LeetCode Solution in C++

``````class NumArray {
public:
// Check the constructor for the initialization of these variables.
vector<int> seg; // Segment Tree to be stored in a vector.
int n; // Length of the segment tree vector.

// Function to build the Segment Tree
// This function will fill up the child values first
// (left == right) will satisfy for the leaf values and they will be updated in segment tree
// seg[pos]=seg[2*pos+1]+ seg[2*pos+2]; -> This will help populate all other intermediate nodes
// as well as the root node with the "sum" of their child nodes.
// Finally we have a segment tree which has all 'nodes' with sum values of their child.
void buildTree(vector<int>& nums, int pos, int left, int right){
if (left == right){
seg[pos] = nums[left];
return;
}
int mid = (left+right)/2;
buildTree(nums, 2*pos+1, left, mid);
buildTree(nums, 2*pos+2, mid+1, right);
seg[pos]=seg[2*pos+1]+ seg[2*pos+2];
}

// Function to update a node in the segment tree
// When a node is updated, then the change in the node value has to be propagated to the root
// left, right -> represents the range of the node of segment tree. (Ex: [0, n-1] -> root)
// pos       -> represents "position" in the segment tree data structure (Ex: 0 -> root)
// Using left, right and pos -> we have all the information on the segment tree
// Node at 'pos' in segment tree will have children at 2pos+1(left) and 2pos+2(right)

// If index is less than left or more than right, then it is out of bound
//      for this node's range so we ignore it and return (This makes the algo O(logn))
// If left==right==index, then we found the index,
//      update the value of the segment tree node & return
// Otherwise, we need to find the index and we do this by checking child nodes (2pos+1, 2pos+2)
//      update the segment tree pos with the updated child values' sum.
//      This would help propagate the updated value of the chid indexes to the parent (through recursion)
void updateUtil(int pos, int left, int right, int index, int val) {
// no overlap
if(index <left || index >right) return;

// total overlap
if(left==right){
if(left==index)
seg[pos]=val;
return;
}

// partial overlap
int mid=(left+right)/2;
updateUtil(2*pos+1,left,mid,index,val); // left child
updateUtil(2*pos+2,mid+1,right,index,val); // right child
seg[pos]=seg[2*pos+1]+seg[2*pos+2];
}

// Function to get the sum from the range [qlow, qhigh]
// low, high -> represents the range of the node of segment tree. (Ex: [0, n-1] -> root)
// pos       -> represents "position" in the segment tree data structure (Ex: 0 -> root)
// Using low, high and pos -> we have all the information on the segment tree
// Node at 'pos' in segment tree will have children at 2pos+1(left) and 2pos+2(right)

// While searching for the range, there will be three cases: (Ex: arr: [-1, 4, 2, 0])
//  - Total Overlap:    Return the value. (Ex: qlow, qhigh: 0,3 and low, high: 1,2)
//  - No Overlap:       Return 0. (Ex: qlow, qhigh: 0,1 and low, high: 2,3)
//  - Partial Overlap:  Search for it in both the child nodes and their ranges.
//                      (Ex: Searching for 1,2 and node range is 0,1)
int rangeUtil(int qlow, int qhigh, int low, int high, int pos){
if (qlow <= low && qhigh>= high){ // total overlap
return seg[pos];
}
if (qlow > high || qhigh < low) { // no overlap
return 0;
}
// partial overlap
int mid = low+(high-low)/2;
return (rangeUtil(qlow, qhigh, low, mid, 2*pos+1) + rangeUtil(qlow, qhigh, mid+1, high, 2*pos+2));
}

// Constructor for initializing the variables.
NumArray(vector<int>& nums) {
if(nums.size() > 0){
n = nums.size();
seg.resize(4*n,0);  // Maximum size of a segment tree for an array of size n is 4n
buildTree(nums, 0, 0, n-1); // Build the segment tree
// Print Segment Tree
// for(int i=0;i<4*n;i++)
//     cout<<seg[i]<<" ";
// cout<<endl;
}
}

// Update the segment Tree recurively using updateUtil
void update(int index, int val) {
if(n==0)return;
updateUtil(0,0,n-1, index, val);
}

// Get the sum for a specific range for the segment Tree
int sumRange(int left, int right) {
if(n==0)return 0;
return rangeUtil(left, right, 0, n-1, 0);
// query from left to right while segment tree is now at 'root' (pos=0) and range(0, n-1)
}
};

/**
* 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);
*/
``````
##### Range Sum Query – Mutable LeetCode Solution Review:

In our experience, we suggest you solve this Range Sum Query – Mutable LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Range Sum Query – Mutable LeetCode Solution

Find on Leetcode

##### Conclusion:

I hope this Range Sum Query – Mutable LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions