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.

RangeMinimumQuery.png

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/

Advertisements