一般化(抽象化？)Segtree

#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

速度

そこそこ