Dynamic Range Minimum Queries

import math

n, q = [int(x) for x in input().split()]
array = [int(x) for x in input().split()]
minimums = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]

# def calculateMins():
#     for i in range(n):
#         for j in range(i, n):
#             if i != j and math.log2(j-i + 1) % 1 == 0:
#                 minimums.update({str((i+1, j+1)) : min(array[i:j+1])}) 
#     # print(minimums)
#     return minimums

def calculateMin(a, b):
    if minimums[a][b] != -1: return minimums[a][b]
    if a == b: value = array[max(0, a - 1)]
    elif a + 1 == b or a - 1 == b: value = min(array[max(0, a - 1)], array[b - 1])
    else:
        minPower = 2 ** int(math.log2(b-a+1))
        if minPower >= b-a+1: minPower = 2 ** int(math.log2(b-a))
        w = int(minPower / 2)
        value = min(calculateMin(a, a + w - 1), calculateMin(a + w, b))
    minimums[a][b] = value
    return value

output = []
for i in range(q):
    action, k, u = [int(x) for x in input().split()]
    if action == 1: 
        array[k - 1] = u
        minimums = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
    else: output.append(str(calculateMin(k, u)))

print("\n".join(output))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: RUNTIME ERROR