Segment Tree: min/max range queries problem.
Given an array arr[0…n-1] and multiple queries. With each query, we need to find the minimum (or maximum) value from index qs (query start) to qe (query end) where 0 <= qs <= qe < n.
Examples:
Input : arr[] = {1, 8, 5, 9, 6, 14, 2, 4, 3, 7} queries = 5 qs = 0 qe = 4 qs = 3 qe = 7 qs = 1 qe = 6 qs = 2 qe = 5 qs = 0 qe = 8 Output: Minimum = 1 and Maximum = 9 Minimum = 2 and Maximum = 14 Minimum = 2 and Maximum = 14 Minimum = 5 and Maximum = 14 Minimum = 1 and Maximum = 14
There are multiple ways for solving this problem.
1. Simple solution:
Each query, we run through arr[qs…qe], find and print out the min/maximum value. This approach is useful on a small scale problem, but when array involves thousands of elements and we have thousands of queries, it is impractical, since its time complexity is O(q * n), with q is number of queries and n is number of elements in array.
2. Segment Tree
Utilize the properties of segment tree can help us solve this problem efficiently.
A segment tree is a binary tree, the way it is built can be compared to merge sort algorithm. The root node contains the min value in range [0…n-1], left and right child of root node contains range of half left and half right: [0…mid] and [mid+1…0], respectively. This can be applied on left and right child of any node.
Except leaf nodes, leaf nodes contain elements in the original array.
Segment tree of array: [2, 5, 1, 4, 9, 3]
Number of elements in segment tree is 2*n – 1, with n is the number of elements in the array. But since we gonna use array for the implementation, we need 2*next_power_of_two(n) – 1, next_power_of_two is a function return the smallest possible power of two that is bigger than n. Example next_power_of_two(5) will yield 8.
Time complexity will be O(q * logn) with q is the number of queries and n is number of elements in array, which is significantly faster than the simple approach.
class SegmentTree: ########################### Private Interface ############################ def __init__(self, arr): self._seg_tree = [float('Inf')]*(2*self._next_power_of_two(len(arr))-1) # input array self._arr = arr self._construct_tree(self._arr, self._seg_tree, 0, len(self._arr)-1, 0) def _construct_tree(self, arr, seg_tree, low, high, pos): if low >= high: # build two child first # (value, (range)) -> help query easier seg_tree[pos] = (arr[low], (low, low)) return mid = (low+high) // 2 # build left subtree self._construct_tree(arr, seg_tree, low, mid, 2*pos+1) # build right subtree self._construct_tree(arr, seg_tree, mid+1, high, 2*pos+2) # build the parent of two children above # get min of two children, and range is [low, high] seg_tree[pos] = (min(seg_tree[self._left(pos)][0], seg_tree[self._right(pos)][0]), (low, high)) def _is_power_of_two(self, n): return n > 0 and (n & (n-1)) == 0 def _next_power_of_two(self, n): # if n is already a power of two, return it if self._is_power_of_two(n): return n count = 0 while n > 0: count += 1 # right shift bit = divide by 2 n = n >> 1 # 1 << count = 2**count return 1 << count def _left(self, p): # return left child of p return p*2 + 1 def _right(self, p): # return right child of p return p*2 + 2 def _has_child(self, p): # check if p has children return self._left(p) < len(self._seg_tree) and self._right(p) < len(self._seg_tree) ########################### Public Interface ############################ def query_min(self, qs, qe, pos): # since there are some INF element # we need to check instance type if isinstance(self._seg_tree[pos], float): return float('Inf') # get range of the current 'pos' # and min of current range start, end = self._seg_tree[pos][1] min_val = self._seg_tree[pos][0] # case 1: range of node is within qs and qe # => return min of range if qs <= start and qe >= end: return min_val # case 2: range of node is outside qs and qe # => return INF (indicate redundant value) if end < qs or start > qe: return float('Inf') # case 3: range of node is partition overlapped with qs and qe # return min([left_child, qs, qe], [right_child, qs, qe]) # first we need to check if it has child # if no, return its value, otherwise call query_min for left and right child if self._has_child(pos): return min(self.query_min(qs, qe, self._left(pos)), self.query_min(qs, qe, self._right(pos))) else: return self._seg_tree[pos][0]
As you can see in the query_min() method, there are three cases can happen.
1. The range of current node is completely inside the range of query.
2. The range of current node is completely outside the range of query.
3. The range of current node is partition overlapped with the range of query.
More understanding can be gained after watching this video. In my opinion, it is by far the most understandable video describing how a min/max query works on segment tree.
Segment Tree Query Demo
Some problem for practising:
https://www.hackerrank.com/challenges/service-lane/problem
http://www.spoj.com/problems/RMQSQ/
Reply