Segment Tree
- First, try to build the segment tree.
- lintcode
- suggest code: Currently recursion recommended. (For coding exercise, u can just start with "Interval minimum number" below.)
"""
Definition of SegmentTreeNode:
class SegmentTreeNode:
def __init__(self, start, end):
self.start, self.end = start, end
self.left, self.right = None, None
""" class Solution:
"""
@param: start: start value.
@param: end: end value.
@return: The root of Segment Tree.
"""
def build(self, start, end):
# write your code here
if start > end:
return
root = SegmentTreeNode(start, end)
if start == end:
return root
mid = (end - start) / 2 + start
root.left = self.build(start, mid)
root.right = self.build(mid + 1, end)
return root - Edge case:
- Trees are building by pointers, so u must consider the null pointers!!!
- if start > end
- Try to know about segment tree.
- wiki
- Exactly as its name, segment tree is used to store segments.
- A segment tree is a tree for storing intervals, or segments. It allows querying which of the stored segments contains a given pionts.
- It is, in principle, a static structure; that is, it's a structure that cannot be modified once it's built.
- Complexity:
- A segment tree of a set I of n intervals uses O(nlogn) storage and can be built in O(nlogn) time.
- Segements trees support searching for all the intervals that contain a query point in O(logn + k), k being the number of retrieved intervals or segments.
- Try to use segment tree for simple query...
- Recursion recommended too. But to careful to consider all the cases, see below:
"""
Definition of SegmentTreeNode:
class SegmentTreeNode:
def __init__(self, start, end, max):
self.start, self.end, self.max = start, end, max
self.left, self.right = None, None
""" class Solution:
"""
@param: root: The root of segment tree.
@param: start: start value.
@param: end: end value.
@return: The maximum number in the interval [start, end]
"""
def query(self, root, start, end):
# write your code here
if start > end:
return
if (start <= root.start and end >= root.end):
return root.max
mid = (root.end - root.start) / 2 + root.start
if end <= mid:
return self.query(root.left, start, end)
if start > mid:
return self.query(root.right, start, end)
return max(self.query(root.left, start, mid), self.query(root.right, mid + 1, end)) - Then try to modify the tree...
Please be familiar with this way of recursion: return current val for each recursion."""
Definition of SegmentTreeNode:
class SegmentTreeNode:
def __init__(self, start, end, max):
self.start, self.end, self.max = start, end, max
self.left, self.right = None, None
""" class Solution:
"""
@param: root: The root of segment tree.
@param: index: index.
@param: value: value
@return:
"""
def modify(self, root, index, value):
# write your code here
if not root or index < root.start or index > root.end:
return
self.helper(root, index, value) def helper(self, root, index, value):
if root.start == root.end:
if root.start == index:
root.max = value
return root.max
mid = (root.end - root.start) / 2 + root.start
if index <= mid:
val = self.helper(root.left, index, value)
if root.right:
val = max(val, root.right.max)
root.max = val
else:
val = self.helper(root.right, index, value)
if root.left:
val = max(val, root.left.max)
root.max = val
return root.max
- Recursion recommended too. But to careful to consider all the cases, see below:
- Now, try some usages.
- Interval minimum number: lintcode
- This is the most representative usage of segment: do interval aggregative operation.
"""
Definition of Interval.
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class SegTreeNode:
def __init__(self, start, end, val):
self.start, self.end, self.val = start, end, val
self.left, self.right = None, None class Solution:
"""
@param: A: An integer array
@param: queries: An query list
@return: The result list
"""
def intervalMinNumber(self, A, queries):
# write your code here
if not A or not queries:
return []
# 1. construct a segment tree
root = self.construct_st(A, 0, len(A) - 1)
# 2. search for each query
res = []
for query in queries:
res.append(self.query_st(root, query.start, query.end))
return res def construct_st(self, nums, start, end):
if start == end:
return SegTreeNode(start, end, nums[start])
mid = (end - start) / 2 + start
left = self.construct_st(nums, start, mid)
right = self.construct_st(nums, mid + 1, end)
root = SegTreeNode(start, end, min(left.val, right.val))
root.left = left
root.right = right
return root def query_st(self, root, start, end):
if start <= root.start and end >= root.end:
return root.val
root_mid = (root.end - root.start) / 2 + root.start
if end <= root_mid:
return self.query_st(root.left, start, end)
if start > root_mid:
return self.query_st(root.right, start, end)
return min(self.query_st(root.left, start, root_mid), self.query_st(root.right, root_mid + 1, end))
- For complicated implementation, try Interval Sum II.
- Interval minimum number: lintcode
- Now, try some usage that not that obvious segment tree.
-
Count of Smaller Number.
A useful thing to notice is that the value of from this array is value from 0 to 10000. So we can use a segment tree to denote [start, end, val] and val denotes how many numbers from the array is between [start, end]. class SegTreeNode:
def __init__(self, start, end, val):
self.start, self.end, self.val = start, end, val
self.left, self.right = None, None class Solution:
"""
@param: A: An integer array
@param: queries: The query list
@return: The number of element in the array that are smaller that the given integer
"""
def countOfSmallerNumber(self, A, queries):
# write your code here
if not A:
return [0 for i in range(len(queries))] # 1. construct a segment tree
dict_A = {}
for val in A:
dict_A[val] = dict_A.get(val, 0) + 1
root = self.con_st(0, 10000, dict_A)
# 2. search
res = []
for query in queries:
res.append(self.query_st(root, query))
return res def con_st(self, start, end, dict_A):
if start > end:
return
if start == end:
return SegTreeNode(start, end, dict_A.get(start, 0))
mid = (end - start) / 2 + start
left = self.con_st(start, mid, dict_A)
right = self.con_st(mid + 1, end, dict_A)
root = SegTreeNode(start, end, left.val + right.val)
root.left, root.right = left, right
return root def query_st(self, root, query):
if not root:
return 0
if query > root.end:
return root.val
if query <= root.start:
return 0
mid = (root.end - root.start) / 2 + root.start
if query > mid:
return root.left.val + self.query_st(root.right, query)
if query <= mid:
return self.query_st(root.left, query)- Then, try this: Count of smaller number before itself.
- Obivously, we can use binary search to solve this just almost the same as 'Count of smaller number'. But for this problem, it will cost O(N^2) time, for the O(N) time for insert into a list.
- But still, I tried binary search, as below:
class Solution:
"""
@param: A: an integer array
@return: A list of integers includes the index of the first number and the index of the last number
""" def countOfSmallerNumberII(self, A):
# write your code here
if not A:
return []
# binary search, O(NlogN) time(O(N^2) for insert takes O(N) each time), O(N) space
sorted_subarr = []
res = []
for val in A:
ind = self.binary_search(sorted_subarr, val)
res.append(ind)
return res def binary_search(self, sorted_subarr, val):
if not sorted_subarr:
sorted_subarr.append(val)
return 0
# 1. find the right-most number who is smaller than val
left, right = 0, len(sorted_subarr) - 1
while left < right - 1:
mid = (right - left) / 2 + left
if sorted_subarr[mid] < val:
left = mid
else:
right = mid
# 2. insert val into sorted_subarr
if sorted_subarr[right] < val:
sorted_subarr.insert(right + 1, val)
return right + 1
elif sorted_subarr[left] < val:
sorted_subarr.insert(left + 1, val)
return left + 1
else:
sorted_subarr.insert(left, val)
return left - And a better choice is using segment tree. For each val in A, we search segment tree then insert it into tree.
class SegTreeNode:
def __init__(self, start, end, val):
self.val, self.start, self.end = val, start, end
self.left, self.right = None, None class Solution:
"""
@param: A: an integer array
@return: A list of integers includes the index of the first number and the index of the last number
""" def countOfSmallerNumberII(self, A):
# write your code here
if not A:
return []
# 1. build segment tree, using O(10000log10000)
root = self.build_st(0, max(A))
# 2. search for target value then update segment tree
res = []
for val in A:
res.append(self.search_st(root, val))
self.update_st(root, val)
return res def build_st(self, start, end):
root = SegTreeNode(start, end, 0)
if start == end:
return root
mid = (end - start) / 2 + start
root.left = self.build_st(start, mid)
root.right = self.build_st(mid + 1, end)
return root def search_st(self, root, val):
if val > root.end:
return root.val
if val <= root.start:
return 0
mid = (root.end - root.start) / 2 + root.start
if val <= mid:
return self.search_st(root.left, val)
return root.left.val + self.search_st(root.right, val) def update_st(self, root, val):
root.val += 1
if root.start == root.end:
return
mid = (root.end - root.start) / 2 + root.start
if val <= mid:
self.update_st(root.left, val)
else:
self.update_st(root.right, val)
-
Count of Smaller Number.
Summary of segment tree
- 线段树的每个节点表示一个区间，子节点分别表示父节点的左右半区间。
- 线段树的构建、查询和更新都可以使用递归。构建是O(NlogN) time, 查询和更新时O(logN) time，其中n是root的end - start。
- 常见应用：求区间的最大最小值、区间的sum等。
Binary Search Tree
- The definition of bst is very easy: x.left < x, x.right > x
- Range search in bst: Search Range in BST.
BST(tree)惯用套路：recursionclass Solution:
"""
@param: root: param root: The root of the binary search tree
@param: k1: An integer
@param: k2: An integer
@return: return: Return all keys that k1<=key<=k2 in ascending order
"""
def searchRange(self, root, k1, k2):
# write your code here
if not root or k1 > k2:
return []
results = []
self.helper(root, k1, k2, results)
return results def helper(self, root, start, end, results):
if not root or start > end:
return
if root.val < start:
self.helper(root.right, start, end, results)
elif root.val > end:
self.helper(root.left, start, end, results)
else:
self.helper(root.left, start, root.val, results)
results.append(root.val)
self.helper(root.right, root.val, end, results)