Dynamic Range Minimum Queries

import sys


def next_pow2(n):
    if n <= 1:
        return 1
    return 1 << (n - 1).bit_length()


class SegmentTree:
    def __init__(self, arr: list[int]) -> None:

        biggie = 10**9
        while len(arr) < next_pow2(len(arr)):
            arr.append(biggie)
        self.n = len(arr)

        self.tree = [0] * self.n + arr

        for k in range(self.n - 1, -1, -1):
            self.tree[k] = min(self.tree[2 * k], self.tree[2 * k + 1])

    def update(self, k: int, u: int) -> None:
        k = self.n + k - 1
        self.tree[k] = u
        k = k // 2
        while k >= 1:
            prev = self.tree[k]
            self.tree[k] = min(self.tree[2 * k], self.tree[2 * k + 1])
            if self.tree[k] == prev:
                print(f"after {self.tree}")
                return
            k = k // 2

    def min(self, a: int, b: int) -> int:

        mini = 10**9

        l = 1
        r = self.n
        curr = 1
        # print(f"Searching {a},{b}")
        while curr < len(self.tree):
            # print(f"now searching at {l},{r},{curr}")
            if a == l and b >= r:
                # print(f"found at {l},{r},{curr}")
                mini = min(mini, self.tree[curr])
                break
            mid = (l + r) // 2
            curr *= 2
            if a > mid:  # go right
                curr += 1
                l = mid + 1
            else:  # go left
                r = mid

        l = 1
        r = self.n
        curr = 1
        while curr < len(self.tree):
            # print(f"now searching at {l},{r},{curr}")
            if b == r and l <= a:
                # print(f"found at {l},{r},{curr}")
                mini = min(mini, self.tree[curr])
                break
            mid = (l + r) // 2
            curr *= 2
            if b > mid:  # go right
                curr += 1
                l = mid + 1
            else:  # go left
                r = mid

        return mini


def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    n = int(next(it))
    q = int(next(it))
    arr = [int(next(it)) for _ in range(n)]
    queries = [(int(next(it)), int(next(it)), int(next(it))) for _ in range(q)]

    st = SegmentTree(arr)
    for op, x, y in queries:
        if op == 1:
            st.update(x, y)
        else:
            print(st.min(x, y))


main()

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: OUTPUT LIMIT EXCEEDED