leetCode Question: Range Sum Query - Mutable

Range Sum Query - Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

Analysis

An intuitive but less efficient solution of this problem is to use simple loop:

  • loop from index i to j, accumulate the sum and return.

It is not difficult to find out the time complexity is O(n) for finding the sum and O(1) for the update.

Another solution: use the data structure segment tree. In this post, we are going to briefly introduce this data structure and focus on how to implement it in an intuitive way.

Specifically in our problem, segment tree can be viewed as a binary tree, where:

  • Leaf nodes are the elements of input array.
  • inernal nodes are the some merging of the leaf nodes. In this problem, internal nodes are the sum of leaf nodes under it.

An example of segment tree is shown below in the figure:

Now I will try to answer the following questions:

  • How does this help solving our problem?
  • How to construct the segment tree?
  • How to compute the range sum?
  • How to update the segment tree?

How does this help solving our problem?
From the tree structure shown above, we can see that, for each internal node (not leaf nodes), we already comput certain range sum (in a binary saerch fashion). If we could utilize these ranges sums to compute any range sums, it will be much more efficient than using loop. So what shall we do to compute the range sum? Don't worry, we will discuss this later.

How to construct the segment tree?
As we said, given an input array, we want to construct a tree structure where (1) Leaf nodes are the elements of input array. (2) Inernal nodes are the some merging of the leaf nodes. In this problem, internal nodes are the sum of leaf nodes under it.

Binary search is a good way constructing the tree. Specifically, we have a root node and an input array, the value of root node is the sum of its left and right children's value. The left and right children are also a segment tree, where the input array now becomes the left half and right half of the original array. Now we can build the segment tree using recursion.

How to compute the range sum?
We have a segment tree, the goal is to compute the range sum given the start and end indices. As the definition of segment tree, we have a range [st, ed] with each node, which represent the node value is actually the sum of range [st, ed].
Say now we have a query to compute range sum in [ i, j ]:

  1. If [st, ed] and [ i, j ] are identical, so the node value is what we want.
  2. If [st, ed] is totally inside the range [ i, j ], so current node's value is part of our sum, but it is not enough. We also have to add the sum in [ i, st-1 ], and [ ed+1, j ].
  3. If [st, ed] is totally outside the range [ i, j ], current range has no relation to our goal, we just ignore the current node (and tree nodes below it).
  4. If [st, ed] has partial overlap with range [ i, j ]. We shoud keep search the left and right chrildren of current node.

After listing all the possibilities of our query range [ i, j ], and any range corresponding to one tree node in the segment tree, we could write the algorithm to find the range sum just using the tree search. (see the figure below)

The time complexity of computing sum now becomes O(log n), where n is the number of elements in input array. The time complexity for constructing the segment tree is O(n).

How to update the segment tree?
Updating tree node is pretty straight forward, we just have to find the path goes from root node to the specific node we want to update, and update each node value through the path by delta, where delta is the difference between the new value and the original value. Because every node through the path, records the sum of range where the new leaf node to lies in, so we have to update all its values when updating this leaf node.
The time complexity of updating leaf node is also O(log n).

Code (C++):

class NumArray {
public:
NumArray(vector<int> nums) {
n = nums.size();
if (n==0){return;}
this->nums = nums;
segTree = constructSegTree(nums, 0, n-1);
//checkSegTree(segTree);
}
void update(int i, int val) {
//cout << "updating i=" << i << ", val = " << val << endl;
updateSegTree(segTree, 0, n-1, i, val);
nums[i] = val;
//checkSegTree(segTree);
}
int sumRange(int i, int j) {
return treeSum(segTree, 0, n-1, i, j);
}
private:
struct TreeNode
{
int value;
TreeNode* left;
TreeNode* right;
};
TreeNode* segTree; // segmentation tree
vector<int> nums; // input array
int n; // length of input array
TreeNode* constructSegTree(const vector<int>& nums, int st, int ed){
TreeNode *tnode = new TreeNode();
if (st == ed){
tnode->value = nums[st];
//cout << "set value to node: " << nums[st] << endl;
}else{
int mid = st + (ed-st)/2;
//cout << "mid = " << mid << endl;
tnode->left = constructSegTree(nums, st, mid);
//cout << "left val:" << tnode->left->value << endl;
tnode->right = constructSegTree(nums, mid+1, ed);
//cout << "right val:" << tnode->right->value << endl;
tnode->value = tnode->left->value + tnode->right->value;
//cout << "value= " << tnode->value << endl;
}
return tnode;
}
int treeSum(TreeNode* segTree, int st, int ed, int l, int r){
if (st >= l && ed <= r){
return segTree->value;
}else if (ed < l || st > r){
return 0;
}else{
int mid = st + (ed-st)/2;
return treeSum(segTree->left, st, mid, l, r) + treeSum(segTree->right, mid+1, ed, l, r);
}
}
void updateSegTree(TreeNode* segTree, int st, int ed, int i, int val){
int mid = st + (ed-st)/2;
int diff = val - nums[i];
//cout << "diff=" << diff << endl;
//cout << "st, ed = " << st << ", " << ed << endl;
if (st == ed){
segTree->value += diff;
}else if (i <= mid){
segTree->value += diff;
updateSegTree(segTree->left, st, mid, i, val);
}else{
segTree->value += diff;
updateSegTree(segTree->right, mid+1, ed, i, val);
}
}
// print segTree level by level (debug only)
void checkSegTree(TreeNode* segTree){
//cout << "Printing segTree structure" << endl;
queue<TreeNode*> q1;
queue<TreeNode*> q2;
q1.push(segTree);
while (!q1.empty()){
while (!q1.empty()){
TreeNode* tmp = q1.front();
q1.pop();
if (tmp->left){ q2.push(tmp->left);}
if (tmp->right){ q2.push(tmp->right);}
}
q1 = q2;
q2 = queue<TreeNode*>();
}
}
};
/**
* 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);
*/

Code (Python):

class TreeNode(object):
def __init__(self, val=0):
self.value = val
self.left = None
self.right = None
class NumArray(object):
def __init__(self, nums):
"""
:type nums: List[int]
"""
self.nums = nums
self.n = len(nums)
if self.n == 0:
return
self.seg_tree = self.construct_seg_tree(0, self.n-1)
#self.print_tree()
def update(self, i, val):
"""
:type i: int
:type val: int
:rtype: void
"""
self.update_seg_tree(self.seg_tree, 0, self.n-1, i, val)
self.nums[i] = val
def sumRange(self, i, j):
"""
:type i: int
:type j: int
:rtype: int
"""
return self.tree_sum(self.seg_tree, 0, self.n-1, i, j)
def construct_seg_tree(self, st, ed):
tmp = TreeNode()
mid = st + (ed-st)/2
if st == ed:
tmp.value = self.nums[st]
else:
tmp.left = self.construct_seg_tree(st, mid)
tmp.right = self.construct_seg_tree(mid+1, ed)
tmp.value = tmp.right.value + tmp.left.value
return tmp
def tree_sum(self, seg_tree, st, ed, i, j):
if st>=i and ed <=j:
return seg_tree.value
elif ed < i or st > j:
return 0
else:
mid = st + (ed-st)/2
return self.tree_sum(seg_tree.left, st, mid, i, j) + self.tree_sum(seg_tree.right, mid+1, ed, i, j)
def update_seg_tree(self, seg_tree, st, ed, i, val):
mid = st + (ed-st)/2
diff = val - self.nums[i]
if st==ed:
seg_tree.value += diff
else:
if i <= mid:
seg_tree.value += diff
self.update_seg_tree(seg_tree.left, st, mid, i, val)
else:
seg_tree.value += diff
self.update_seg_tree(seg_tree.right, mid+1, ed, i, val)
def print_tree(self):
node = self.seg_tree
q1 = []
q2 = []
q1.append(node)
while q1:
while q1:
tmp = q1.pop(0)
print tmp.value,
print ", ",
if tmp.left:
q2.append(tmp.left)
if tmp.right:
q2.append(tmp.right)
q1 = q2
q2 = []
print
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)
3 comments:
Labels: , ,

leetCode Question: Range Sum Query 2D - Immutable

Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

Analysis

First glance at this problem give us an intuitive but less efficient solution: Loop through row1 to row2, loop through col1 to col2, add the matrix element one by one.

Given the condition that there are many function calls, we could start thinking of more efficient algorithm. Since the matrix does not change, we could possiblly store some information before the "sumRegion" calls, in order to help on the time complexity.

Firstly let's simplify the problem to the following description:
given a matrix, and one point, which is the bottom right corner, compute the sum of the region between (0, 0) and the point.

It's more intuitive to draw the figure below ( see (1) ):

From the figure, we could see the procedure to compute the sum of region by addition and subtraction.

Looking back to the original problem, it is then not hard to find out (figure (2) ):

sumRegion(row1, col1, row2, col2) = sum( (row2, col2) ) - sum( (row1-1, col2) ) - sum( (row2, col1-1) ) + sum( (row1-1, col1-1) )

Now, the only thing of which you may not get the idea is the initialization part. Actually it is not that hard but need more attention dealing with the indices. Specifically, we build a matrix of the same size, where every position [ i, j ] stores the sum of element between [0 , 0] and [ i, j ]. We are still using the procedure shown in figure (1):

For each position [ i, j ] in our sum matrix, we are checking [ i-1, j ] and [ i, j-1 ], the sum of [ i, j ] is:
m[ i, j ] = m[ i-1, j ] + m[ i, j-1 ] - m[ i-1, j-1 ], the procedure is shown below:

Code (C++)

class NumMatrix {
public:
NumMatrix(vector<vector<int>> matrix) {
nrow = matrix.size();
if (nrow == 0){ return; }
ncol = matrix[0].size();
matrix_sum = vector<vector<int>> (nrow+1, vector<int>(ncol+1, 0));
for (int i=1;i <= nrow; ++i){
for (int j=1;j <= ncol; ++j){
matrix_sum[i][j] = matrix_sum[i-1][j] + matrix_sum[i][j-1] - matrix_sum[i-1][j-1] + matrix[i-1][j-1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int p1_i, p1_j, p2_i, p2_j, p3_i, p3_j, p4_i, p4_j;
p1_i = row1;
p1_j = col1;
p2_i = row1;
p2_j = col2 + 1;
p3_i = row2+1;
p3_j = col2+1;
p4_i = row2+1;
p4_j = col1;
return matrix_sum[p3_i][p3_j] - matrix_sum[p2_i][p2_j] - matrix_sum[p4_i][p4_j] + matrix_sum[p1_i][p1_j];
}
private:
vector<vector<int> > matrix_sum;
int nrow;
int ncol;
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/

Code (Python)

class NumMatrix(object):
def __init__(self, matrix):
"""
:type matrix: List[List[int]]
"""
if len(matrix) == 0:
return
self.n_row = len(matrix)
self.n_col = len(matrix[0])
self.matrix_sum = [ [0 for i in range(self.n_col+1)] for j in range(self.n_row+1)]
for i in xrange(1, self.n_row+1):
for j in xrange(1, self.n_col+1):
self.matrix_sum[i][j] = self.matrix_sum[i-1][j] + self.matrix_sum[i][j-1] - self.matrix_sum[i-1][j-1] + matrix[i-1][j-1]
def sumRegion(self, row1, col1, row2, col2):
"""
:type row1: int
:type col1: int
:type row2: int
:type col2: int
:rtype: int
"""
p1_i, p1_j = row1, col1
p2_i, p2_j = row1, col2 + 1
p3_i, p3_j = row2 + 1, col2 + 1
p4_i, p4_j = row2 + 1, col1
return self.matrix_sum[p3_i][p3_j] + self.matrix_sum[p1_i][p1_j] - self.matrix_sum[p2_i][p2_j] - self.matrix_sum[p4_i][p4_j]
# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)
3 comments:
Labels: ,
Subscribe to: Posts (Atom)