#include <bits/stdc++.h> using namespace std; using uint = unsigned int; template<class T> using V = vector<T>; template<class D, class OP> struct SegTree { OP op; //f(data, data) -> data D e; //単位元 int n, sz, lg; //サイズ, 2^lgに拡張後のサイズ, lg V<D> seg; SegTree(V<D> first, OP _op, D _e) : op(_op), e(_e) { n = int(first.size()); lg = 1; while ((1<<lg) < n) lg++; sz = 1<<lg; seg = V<D>(2*sz, e); for (int i = 0; i < n; i++) seg[sz + i] = first[i]; for (int i = sz-1; i >= 0; i--) { update(i); } } void update(int k) { seg[k] = op(seg[2*k], seg[2*k+1]); } D sum(int a, int b) { D sm_l = e, sm_r = e; a += sz; b += sz; while (a < b) { if (a & 1) sm_l = op(sm_l, seg[a++]); if (b & 1) sm_r = op(seg[--b], sm_r); a >>= 1; b >>= 1; } return op(sm_l, sm_r); } void single_set(int k, D x) { k += sz; seg[k] = x; for (int i = 1; i <= lg; i++) update(k>>i); } }; //helper for c++11, 14 template<class D, class OP> SegTree<D, OP> make_segtree(V<D> first, OP op, D e) { return SegTree<D, OP>(first, op, e); }
使い方
RMQ
const int INF = 1000000007; auto seg = SegTree(V<int>(n, INF), [&](int a, int b){ return min(a, b); }, INF); (since c++1z) auto seg = make_segtree(V<int>(n, INF), [&](int a, int b){ return min(a, b); }, INF);
コード例
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3079917#1
速度
そこそこ
