Sparse Table Implementation in Python

sparse_table.py

def genSparse(arr):
  n = len(arr)
  k = len("{:b}".format(n))
  table = [[float('inf')] * k for _ in range(n)]
  for l in range(k):
    for i in range(n):
      if l == 0:
        table[i][l] = arr[i]
      else:
        a = table[i][l - 1]
        b = float('inf')
        if i + (1 << l - 1) < n:
          b = table[i + (1 << l - 1)][l - 1]
        table[i][l] = min(a, b)
  return table

def getMin(table, l, r):
  bits = "{:b}".format(r - l)[::-1]
  res = float('inf')
  for i, b in enumerate(bits):
    if b == "1":
      res = min(res, table[l][i])
      l += 1 << i
  return res

arr = [10, 2, 8, 7, 5, 7, 3, 4, 1, 6]

table = genSparse(arr)

print(getMin(table, 1, 7))