Editorial for Min Max Queries

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Maintain a segment tree over the array where each node stores the minimum and maximum value in its range. Combining two child nodes takes the pairwise min and max of their stored values.

An update of type 1 is a standard point update.
A query of type 2 returns the min and max over $[l, r]$ ~[l, r]~.

With $O(1)$ ~O(1)~ work per combine, each update and query costs $O(\log n)$ ~O(\log n)~. The total time complexity is $O((n + q) \log n)$ ~O((n + q) \log n)~.

Solution (Python)

from __future__ import annotations

from dataclasses import dataclass
from typing import Callable, Generic, List, TypeVar
import copy

T = TypeVar("T")


class SegmentTree(Generic[T]):
    def __init__(self, arr: List[T], combine: Callable[[T, T], T]) -> None:
        self.combine = combine
        self.length = len(arr)
        self.array = [0] * (self.length * 4 + 1)
        self.__build(1, 0, self.length - 1, arr)

    def __build(self, v: int, tl: int, tr: int, arr: List[T]) -> None:
        if tl == tr:
            self.array[v] = arr[tl]
        else:
            tm = (tl + tr) // 2
            self.__build(2 * v, tl, tm, arr)
            self.__build(2 * v + 1, tm + 1, tr, arr)
            self.array[v] = self.combine(self.array[2 * v], self.array[2 * v + 1])

    def update(self, index: int, value: T) -> None:
        self.__update(index, 1, 0, self.length - 1, value)

    def __update(self, index: int, v: int, tl: int, tr: int, value: T) -> None:
        if tl == tr:
            self.array[v] = value
            return

        tm = (tl + tr) // 2
        if index <= tm:
            self.__update(index, 2 * v, tl, tm, value)
        else:
            self.__update(index, 2 * v + 1, tm + 1, tr, value)

        self.array[v] = self.combine(self.array[2 * v], self.array[2 * v + 1])

    def query(self, l: int, r: int) -> T:
        return copy.copy(self.__query(1, 0, self.length - 1, l, r))

    def __query(self, v: int, tl: int, tr: int, l: int, r: int) -> T:
        if tl == l and tr == r:
            return self.array[v]

        tm = (tl + tr) // 2
        if r <= tm:
            return self.__query(2 * v, tl, tm, l, r)
        if l > tm:
            return self.__query(2 * v + 1, tm + 1, tr, l, r)
        return self.combine(
            self.__query(2 * v, tl, tm, l, tm),
            self.__query(2 * v + 1, tm + 1, tr, tm + 1, r),
        )


@dataclass
class Node:
    max: int
    min: int


def combine(a: Node, b: Node) -> Node:
    return Node(max(a.max, b.max), min(a.min, b.min))


n = int(input())
arr = [Node(int(x), int(x)) for x in input().split()]
segtree = SegmentTree[Node](arr, combine)

for _ in range(int(input())):
    t, a, b = (int(x) for x in input().split())
    if t == 1:
        segtree.update(a - 1, Node(b, b))
    else:
        res = segtree.query(a - 1, b - 1)
        print(f"{res.min} {res.max}")

Comments

There are no comments at the moment.