From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001
From: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 6 Jul 2026 19:08:08 +0200
Subject: Initial commit

---
 .../dynamic_range_minimum_queries_1649.cpp         | 54 ++++++++++++++++++++++
 1 file changed, 54 insertions(+)
 create mode 100644 05_range_queries/dynamic_range_minimum_queries_1649.cpp

(limited to '05_range_queries/dynamic_range_minimum_queries_1649.cpp')

diff --git a/05_range_queries/dynamic_range_minimum_queries_1649.cpp b/05_range_queries/dynamic_range_minimum_queries_1649.cpp
new file mode 100644
index 0000000..c4d9b34
--- /dev/null
+++ b/05_range_queries/dynamic_range_minimum_queries_1649.cpp
@@ -0,0 +1,54 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+constexpr size_t inf = 1999999999;
+
+class SegmentTree {
+public:
+	SegmentTree(size_t n) : m{pow2ceil(n)}, v(2*m, inf) {}
+
+	void update(size_t i, size_t x) {
+		v[m+i-1] = x;
+		for (size_t p = (m+i-1)/2; p > 0; p /= 2)
+			v[p] = std::min(v[2*p], v[2*p+1]);
+	}
+
+	size_t min(size_t a, size_t b) { return q(a-1, b, 1, 0, m); }
+
+private:
+	size_t m;
+	std::vector<size_t> v;
+	static constexpr size_t pow2ceil(size_t x) {
+		size_t c;
+		for (c = 1; c < x; c *= 2) ;
+		return c;
+	}
+
+	size_t q(size_t a, size_t b, size_t i, size_t l, size_t r) {
+		if (a == l && b == r) return v[i];
+		size_t p{(l+r)/2}, s{inf};
+		if (a < p) s = std::min(s, q(a, std::min(b, p), 2*i, l, p));
+		if (b > p) s = std::min(s, q(std::max(a, p), b, 2*i+1, p, r));
+		return s;
+	}
+};
+
+int main() {
+	size_t n, q;
+	std::cin >> n >> q;
+	SegmentTree t(n);
+	for (size_t i = 0; i < n; i++) {
+		size_t x;
+		std::cin >> x;
+		t.update(i+1, x);
+	}
+	for (size_t i = 0; i < q; i++) {
+		int u, a, b;
+		std::cin >> u >> a >> b;
+		if (u == 1)
+			t.update(a, b);
+		else
+			std::cout << t.min(a, b) << "\n";
+	}
+}
-- 
cgit v1.3