Dynamic Range Minimum Queries

import sys

input = sys.stdin.readline


class SegmentTree:
    """Generic segment tree; pass an associative func and its identity."""

    def __init__(self, arr, func=lambda a, b: a + b, identity=0):
        self.func = func
        self.identity = identity
        self.n = len(arr)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.tree = [identity] * (2 * self.size)
        for i, x in enumerate(arr):
            self.tree[self.size + i] = x
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, value):
        """Set element at 0-based index i to value."""
        i += self.size
        self.tree[i] = value
        i //= 2
        while i >= 1:
            self.tree[i] = self.func(self.tree[2 * i], self.tree[2 * i + 1])
            i //= 2

    def query(self, a, b):
        """Inclusive [a, b]."""
        res = self.identity
        a += self.size
        b += self.size + 1
        while a < b:
            if a & 1:
                res = self.func(res, self.tree[a])
                a += 1
            if b & 1:
                b -= 1
                res = self.func(res, self.tree[b])
            a //= 2
            b //= 2
        return res


def main():
    n, q = map(int, input().split())
    arr = list(map(int, input().split()))

    seg = SegmentTree(arr, min, float("inf"))

    out = []
    for _ in range(q):
        t, a, b = map(int, input().split())
        if t == 1:
            seg.update(a - 1, b)
        else:
            out.append(str(seg.query(a - 1, b - 1)))

    sys.stdout.write("\n".join(out) + ("\n" if out else ""))


if __name__ == "__main__":
    main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED