題意#
給定一個長度為 \( n \) 的陣列，並且有 \( q \) 次操作。
操作分為兩種：
- 將陣列在索引 \( k \) 的值更新為 \( u \)。
- 查詢區間 \( [a, b] \) 內的最小值。
思路#
這題同樣有著單點修改與區間查詢的需求，
但與「區間和」不同的是，「區間最小值」無法像加法一樣透過相減來抵銷（也就是不具備可減性）。
因此，我們必須搬出更強大的資料結構：線段樹（Segment Tree）。
這是一棵最基礎的線段樹（不需要懶人標記），
每個節點負責維護一段區間的最小值。
建樹的時間複雜度為 \( O(n) \)，而單點修改與區間查詢的時間複雜度皆為 \( O(\log n) \)。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
// 定義左右子節點的索引
#define lc now*2
#define rc now*2+1
vector<int> v;
vector<int> tree; // 線段樹陣列
// 建樹（由下而上合併最小值）
void build(int l, int r, int now) {
if (l == r) return void(tree[now] = v[l]);
int m = (l+r) / 2;
build(l, m, lc), build(m+1, r, rc);
tree[now] = min(tree[lc], tree[rc]);
}
// 單點修改：將點 idx 的值更新為 k
void upd(int idx, int ql, int qr, int now, int k) {
if (ql == qr) return void(tree[now] = k);
int m = (ql+qr) / 2;
if (idx <= m) upd(idx, ql, m, lc, k);
else upd(idx, m+1, qr, rc, k);
tree[now] = min(tree[lc], tree[rc]);
}
// 區間查詢：回傳區間 [l, r] 的最小值
int query(int l, int r, int ql, int qr, int now) {
// 查詢區間完全覆蓋當前節點所管理的區間
if (l <= ql && qr <= r) return tree[now];
int m = (ql+qr) / 2, mnL = 1e9, mnR = 1e9;
if (l <= m) mnL = query(l, r, ql, m, lc);
if (r >= m+1) mnR = query(l, r, m+1, qr, rc);
return min(mnL, mnR);
}
signed main() { WA();
int n, q; cin >> n >> q;
v.resize(n+1);
tree.resize(4*n); // 線段樹空間大約開到 4*n
for (int i = 1; i <= n; i++) cin >> v[i];
build(1, n, 1);
while (q--) {
int cmd, a, b;
cin >> cmd >> a >> b;
if (cmd == 1) upd(a, 1, n, 1, b); // 單點更新
else cout << query(a, b, 1, n, 1) << '\n'; // 區間查詢最小值
}
}
