class SparseTable:
def __init__(self, arr):
self.n = len(arr)
self.LOG = [0] * (self.n + 1)
for i in range(2, self.n + 1):
self.LOG[i] = self.LOG[i // 2] + 1
K = self.LOG[self.n] + 1
self.st = [[0] * K for _ in range(self.n)]
for i in range(self.n):
self.st[i][0] = arr[i]
for j in range(1, K):
for i in range(self.n - (1 << j) + 1):
self.st[i][j] = min(
self.st[i][j-1],
self.st[i + (1 << (j-1))][j-1]
)
def query(self, l, r):
k = self.LOG[r - l + 1]
return min(self.st[l][k], self.st[r - (1 << k) + 1][k])
Preprocessing: . Each query: .