何回かに分けてセグメント木ライブラリを整備します。1回目は、1点更新と範囲の最小値を求めることに集中します。
セグメント木（Range Minimum Query 固定版）
AOJ ALDS1 5_D問題（解説記事）で反転数を求めるためにセグメント木について、紹介しました。
今回は、1点更新と範囲の最小値を求めることに固定したセグメント木の実装を紹介します。セグメント木については、検索すれば記事が多数見つかるため、これ以上の解説は省略します。
クラス SegmentTree として実装しました。実装は「蟻本」（「プログラミングコンテストチャレンジブック」第2版 秋葉拓哉、岩田陽一、北川宣稔著、マイナビ 2012年）を参考にしました。コードは以下となります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = (1U << 31) - 1;
class SegmentTree {
private:
vector<int> data;
public:
int size;
SegmentTree(int n) {
size = 1;
while (size < n) {
size *= 2;
}
data.assign(2 * size - 1, INF);
}
void update(int k, int a) {
k += size - 1;
data[k] = a;
while (k > 0) {
k = (k - 1) / 2;
data[k] = min(data[k * 2 + 1], data[k * 2 + 2]);
}
}
int query(int a, int b) {
return query_sub(a, b, 0, 0, size);
}
// call ST.query(a, b, 0, 0, size);
int query_sub(int a, int b, int k, int l, int r) {
if ((r <= a)||(b <= l)) {
return INF;
}
if ((a <= l)&&(r <= b)) {
return data[k];
} else {
int vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
int vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
};ライブラリのテスト
AIZU ONLINE JUDGE で出題されている問題でアルゴリズムをテストします。以下が問題のリンク先です。
この問題を解くプログラムは以下です。AC判定となります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = (1U << 31) - 1;
class SegmentTree {
private:
vector<int> data;
public:
int size;
SegmentTree(int n) {
size = 1;
while (size < n) {
size *= 2;
}
data.assign(2 * size - 1, INF);
}
void update(int k, int a) {
k += size - 1;
data[k] = a;
while (k > 0) {
k = (k - 1) / 2;
data[k] = min(data[k * 2 + 1], data[k * 2 + 2]);
}
}
int query(int a, int b) {
return query_sub(a, b, 0, 0, size);
}
// call ST.query(a, b, 0, 0, size);
int query_sub(int a, int b, int k, int l, int r) {
if ((r <= a)||(b <= l)) {
return INF;
}
if ((a <= l)&&(r <= b)) {
return data[k];
} else {
int vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
int vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
};
int main()
{
int n, q;
cin >> n >> q;
SegmentTree st(n);
for (int i = 0; i < q; ++i) {
int command;
cin >> command;
if (command == 0) {
int pos, x;
cin >> pos >> x;
st.update(pos, x);
} else if (command == 1) {
int L, R;
cin >> L >> R;
++R;
cout << st.query(L, R) << endl;
}
}
return 0;
}最後に
AtCoder の ABC でセグメント木が問われる問題が続いたため（ABC339 E問題、ABC340 E問題）、記事を書いて学ぶことにしました。
