Sparse Table

from math import log2


class Sparse:
    def __init__(self, a):
        self.a = a
        self.n = len(a)
        self.k = int(log2(self.n)) + 1
        self.lookup = [[0]*self.k for x in range(self.n)]
        self.process()

    def process(self):
        for i in range(self.n):
            self.lookup[i][0] = self.a[i]
        j = 1
        while (1 << j) <= self.n:
            i = 0
            while (i + (1 << j) - 1) < self.n:
                self.lookup[i][j] = min(self.lookup[i][j-1], self.lookup[i + (1 << (j - 1))][j - 1])
                i += 1
            j += 1

    def query(self, a, b):
        x = int(log2(b - a + 1))
        return min(self.lookup[a][x], self.lookup[b - (1 << x) + 1][x])