Dcoder Cody's Assignment Segment Tree Solution

codys_assignment.py

seg = {}

def makeSeg(arr, i, j):
    if (i, j) in seg:
        return seg[(i, j)]
    if i == j:
        seg[(i, j)] = arr[i]
        return arr[i]
    mid = (i + j) // 2
    curr = min(makeSeg(arr, i, mid), makeSeg(arr, mid + 1, j))
    seg[(i, j)] = curr
    return curr

def getMin(arr, i, j, ni, nj):
    if ni >= i and nj <= j:
        return seg[(ni, nj)]
    if (ni < i and nj < i) or (ni > j and nj > j):
        return float('inf')
    mid = (ni + nj) // 2
    return min(getMin(arr, i, j, ni, mid), getMin(arr, i, j, mid + 1, nj))

n, q = input().split()
n, q = int(n), int(q)

s = list([ord(c) for c in input()])

makeSeg(s, 0, n - 1)

for _ in range(q):
    a, b = input().split()
    a, b = int(a), int(b)
    print(chr(getMin(s, a - 1, b - 1, 0, n - 1)))