Dynamic Range Minimum Queries

#include <bits/stdc++.h>

template <typename T, typename Combine>
class SegmentTree {
public:
    SegmentTree(
        const std::vector<T>& values, T identity, Combine combineOp) : n(values.size()), identity(std::move(identity)), combine(std::move(combineOp)), tree(2 * n, this->identity) {
        if (n == 0) {
            throw std::invalid_argument("Tree must contain values");
        }

        for (std::size_t i = 0; i < n; i++) {
            tree[n + i] = values[i];
        }

        for (std::size_t i = n; i-- > 1;) {
            tree[i] = combine(tree[2*i], tree[2*i+1]);
        }
    }

    void update(std::size_t pos, const T& value) {
        if (pos >= n) {
            throw std::out_of_range("Invalid position");
        }

        pos += n;
        tree[pos] = value;

        while (pos > 1) {
            pos /= 2;
            tree[pos] = combine(tree[2 * pos], tree[2 * pos + 1]);
        }
    }

    T query(std::size_t left, std::size_t right) const {
        if (left > right || right >= n) {
            throw std::out_of_range("Invalid range");
        }

        left += n;
        right += n;

        T resultLeft = identity;
        T resultRight = identity;

        while (left <= right) {
            if (left %2 == 1) {
                resultLeft = combine(resultLeft, tree[left++]);
            }
            if (right %2 == 0) {
                resultRight = combine(tree[right--], resultRight);
            }
            left /= 2;
            right /= 2;
        }
        return combine(resultLeft, resultRight);
    }

private:
    std::size_t n;
    T identity;
    Combine combine;
    std::vector<T> tree;
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;

    std::vector<long> values (n);
    for (long& value : values) {
        std::cin >> value;
    }

    SegmentTree tree(values, std::numeric_limits<long>::max(), [](const long a, const long b){return std::min(a, b);});

    for (int i = 0; i < q; i++) {
        int type;
        std::cin >> type;
        if (type == 1) {
            int k;
            long u;
            std::cin >> k >> u;
            tree.update(k - 1, u);
        } else if (type == 2) {
            int a, b;
            std::cin >> a >> b;
            std::cout << tree.query(a - 1, b - 1) << std::endl;
        } else {
            throw std::invalid_argument("Unsupported operation");
        }
    }

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED