Dynamic Range Minimum Queries

input/code.cpp: In function 'size_t {anonymous}::findNextPowerOf2(size_t)':
input/code.cpp:6:22: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
    6 |         while (n & n - 1) {
      |                    ~~^~~
input/code.cpp:7:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
    7 |             n = n & n - 1;
      |                     ~~^~~

#include <bits/stdc++.h>

namespace {
    size_t findNextPowerOf2(size_t n) {
        n = n - 1;
        while (n & n - 1) {
            n = n & n - 1;
        }
        return n << 1;
    }

    template <typename T, typename Combine>
    class SegmentTree {
    public:
        SegmentTree(
            const std::vector<T>& values, T identity, Combine combineOp) : n(findNextPowerOf2(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