セグメント木
参考
プログラミングコンテストチャレンジブック [第2版] p.153-
初心者の初心者による初心者のための典型segment tree - DEGwerの競技プログラミングと時々数学
セグメント木をソラで書きたいあなたに - hogecoder
遅延評価セグメント木をソラで書きたいあなたに - hogecoder
セグメント木
- どういう写像が合成されていくか意識するのが大切
RMQセグメント木
#include <vector> #include <climits> using namespace std; const int INF = INT_MAX; // 0-indexed RMQ segment tree class SegTree { private: int n; vector<int> dat; public: SegTree(int n_) { n = 1; while (n < n_) n *= 2; dat.assign(2 * n - 1, INF); } void update(int k, int a) { k += n - 1; dat[k] = a; while (k > 0) { k = (k - 1) / 2; dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]); } } int query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return INF; if (a <= l && r <= b) return dat[k]; else { int vl = query(a, b, 2 * k + 1, l, (l + r) / 2); int vr = query(a, b, 2 * k + 2, (l + r) / 2, r); return min(vl, vr); } } // get min in [a, b) int query(int a, int b) { return query(a, b, 0, 0, n); } };
- 蟻本の関数をclassで書いただけ
- 半開区間の最小値を求めることができる
- min()をSegmentTreeに載せている。単位元はINF
- update, query共にO(logN)
- 簡単のため構築時は全ての値がINFなので、初期化にO(NlogN)かかる。最初から数列を与えるようにすれば初期化はO(N)
INT_MAXは実装依存とのこと INT_MAX - cpprefjp C++日本語リファレンス