前々回ではセグ木に載せる演算を別途書くような形で抽象化しました。具体的には、前々回の実装例だと

template <typename T>
T segment_tree::op(T lhs, T rhs){
    // f は入れたい演算に相当
    return f(lhs, rhs);
}

を別途書く必要があるということです。

しかし、最近これは自分の好みではない気がしてきました。より良さそうな方法としては次のようなものが思い浮かびます。

型の情報を渡すのと同じ気持ちで、モノイドの情報をテンプレートパラメータに書いて渡す
- segment_tree<int, std::plus<int>, 0> st(N); のようにして使いたい
- T がリテラル型でないと使えなさそう
- 演算が $+$ ではない場合は自分で構造体か何か書くことになりそう
- だめそう
単位元や演算の情報も持ったモノイドの構造体を作って渡す
- segment_tree<monoid> st(N); のようにして使うことになりそう
- いちいちモノイドの情報を詰めた構造体を作るの、微妙な気がしませんか
  - 好みではないが、良い方法だとは思う
コンストラクタに演算と単位元の情報を渡す
- segment_tree<int> st([](auto x, auto y){ return x+y; }, 0, N); のようにして使いたい
- どのように渡した情報（特に演算）を保持しておくかは要検討

今の私には 3. が本命に見えます。以下 3. について詳細

持ち方

コンストラクタで渡したからにはメンバ変数として持つことになるのですが、問題はどの型を指定するかです。単位元の方は値と同じ T が迷わず使えますが、演算の方は検討の余地がありそうです。

あたりは満たして欲しいです。

候補

とりあえず思い浮かんだものだけ

auto func = [](T x, T y){ return f(x, y); };
segment_tree<T, decltype(func)> st(func, e, N);

のように書く必要がある。 2. と 3. なら

segment_tree<T> st([](T x, T y){ return f(x, y); }, e, N);

のように書ける。

とりあえず以下の 2 通りで評価しました。

3 通りでセグ木を作って AOJの問題に投げてみる
演算部だけ抜き出したクラスを作って演算処理の所要時間を比較する
- 演算として適当なラムダ式を渡す
- 符号なし 64 bit 整数で $2N=2\times 10^7$ 個の乱数を前もって生成
- 2 つずつ、計 $N$ 回演算を呼ぶ。結果は適当な変数に足し上げておく

結果は以下の通り。

実行速度は 1. > 3. > 2. の順に速いっぽい。std::functionのコドフォでの遅さが気になる。

decltype(hoge)を書くのも面倒なので、気が変わるまでは関数ポインタを使うことになりそうです。