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)

leetCode Question: Serialize and Deserialize Binary Tree

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

1

/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Analysis:

In this problem, I have implemented a differrent way of serialization (in C++ code shown below). If you would like to see the simple version which is the same way of LeetCode OJ, please check out the pyhton code below.

Let's first see the simple way of doing this. We will encode the node value level by level, and only encode the "Null" (or "None" in python) node when it is a leaf node. Since we are "searching" the tree level by level, DFS is usually a good way to do so. Here in my solution, I choose to use two queues, to store nodes in current level, and nodes in next level, respectively. For the deserialization, we could still keep two queues for the BFS, and keep track of the node we are expanding.

Secondly, I'l like to show the implementation using a different way. Although it is not a quite efficient method, it still provides good practice of binary tree and binary tree traversal. Particularly, we have a binary tree, rather than the level by level traversal, we still have three depth-first traversal: preorder, inorder, and postorder. Therefore, we could use preorder and inorder traversal to reconstruct the binary tree. Please take a look at my previous post for details. Note that in this problem, there might be duplicate values in different nodes, we have to use the indices of each node for the traversal. So, our encoding format is: "preorder string;inorder string;value string". The "preorder string" is the indices of each node in preorder order, actually, I have given the sequence from 1 to the number of nodes in this string for simplicity. The "inorder string" is the indices of each node in inorder order. The "vaule string" is the values of each node (using preorder order) in string format. All the elements in three strings are splited using ",".

Code (C++):

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class Codec {

public:

TreeNode* reconstruct(vector<int>& in, vector<int>& pre, int st, int ed, int& idx, vector<int>& val){

if (idx!=pre.size()){

TreeNode* node = new TreeNode(val[pre[idx]]);

int i=st;

for ( ;i<ed;i++){

if (in[i]==pre[idx]){break;}

}

idx++;

if (i-1 >=st){

node->left = reconstruct(in, pre, st, i-1, idx,val);

}else{

node->left = NULL;

}

if (ed >= i+1){

node->right = reconstruct(in, pre, i+1,ed, idx,val);

}else{

node->right = NULL;

}

return node;

}else{

return NULL;

}

}

void inOrder(TreeNode* root, string& res, string& val, int& i){

if (!root){return;}

inOrder(root->left, res, val, i);

val += to_string(root->val) + ',';

root->val = i;

res += to_string(i) + ',';

i++;

inOrder(root->right,res, val, i);

}

void preOrder(TreeNode* root, string& res){

if (!root){ return; }

res += to_string(root->val) + ',';

preOrder(root->left, res);

preOrder(root->right,res);

}

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

//inorder

string in; //store the inorder tree traversal using index NOT!!! the actural value

string val; //store the actural values of each node according to the "inorder" order

int i=0;

inOrder(root, in, val, i); //inorder traversal

//preorder

string pre; //stroe the preorder tree traversal using index NOT!!! the actural value

preOrder(root, pre); //preorder traversal

//return the encoded string: inorder(index);preorder(index);values

// e.g., Tree [1,2,3,null,null,4,5] returns "0,1,2,3,4,;1,0,3,2,4,;2,1,4,3,5,"

return in + ";" + pre+ ";" + val;

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

// decode the string

int pos_1 = data.find(';');

string in = data.substr(0,pos_1);

string tmp = data.substr(pos_1+1);

int pos_2 = tmp.find(';');

string pre = tmp.substr(0,pos_2);

string val = tmp.substr(pos_2+1);

vector<int> in_vec; // save the index of inorder traversal

vector<int> pre_vec; // save the index of preorder traversal

vector<int> val_vec; // save the values according to the inorder order

while (val.find(',')!=-1){

val_vec.push_back(stoi(val.substr(0,val.find(','))));

val = val.substr(val.find(',')+1);

}

while (in.find(',')!=-1){

in_vec.push_back(stoi(in.substr(0,in.find(','))));

in = in.substr(in.find(',')+1);

}

while (pre.find(',')!=-1){

pre_vec.push_back(stoi(pre.substr(0,pre.find(','))));

pre = pre.substr(pre.find(',')+1);

}

// reconstruct tree using preorder and inoreder traversal

int idx = 0;

return reconstruct(in_vec, pre_vec, 0, in_vec.size(),idx, val_vec);

}

};

// Your Codec object will be instantiated and called as such:

// Codec codec;

// codec.deserialize(codec.serialize(root));

Code (Python):

# Definition for a binary tree node.

# class TreeNode(object):

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Codec:

def serialize(self, root):

"""Encodes a tree to a single string.

:type root: TreeNode

:rtype: str

"""

q1 = []

q2 = []

res = ""

q1.append(root)

while True:

while len(q1) != 0:

tmp = q1.pop(0)

if tmp is None:

res += "null,"

else:

res += str(tmp.val) + ","

q2.append(tmp.left)

q2.append(tmp.right)

if len(q2) == 0:

break

q1 = q2[:]

q2 = []

return res

def deserialize(self, data):

"""Decodes your encoded data to tree.

:type data: str

:rtype: TreeNode

"""

data_list = data[0:-1].split(',') # [0:-1] eliminates the last ','

mp1 = []

mp2 = []

head = None

if data_list[0] != "null":

mp1.append(TreeNode(int(data_list[0])))

head = mp1[0]

i = 1

while i < len(data_list):

for node in mp1:

if node is not None:

if data_list[i] != "null":

node.left = TreeNode(int(data_list[i]))

i+=1

mp2.append(node.left)

if data_list[i] != "null":

node.right = TreeNode(int(data_list[i]))

i+=1

mp2.append(node.right)

mp1 = mp2[:]

mp2 = []

return head

# Your Codec object will be instantiated and called as such:

# codec = Codec()

# codec.deserialize(codec.serialize(root))