大嘘昔話

実は「segtreeというのはモノイドを載せられて、lazysegtreeはそれにいい感じの作用が行えて…」のようにsegtreeが抽象化されたのは割と最近です。昔はなんかsegtreeって大体実装一緒だな…と思いながら、みな自分のstarryskytree.cppを毎回コピペして適当に書き直して使っていました。

もちろん適切にクラス等を使って最強のsegtreeを作れば勝ちまくりモテまくりであることには皆薄々気づいており、私もそのような夢を追い求める若者の一人でした。その名残がこちらです。

2023年

時は2023年、昔はC++11の機能は新しいといわれていましたが、今ではC++20がどこのジャッジでも使えます(正確には使えないジャッジは引退しました)。C++20と言えばconcept、今回は昔を思いながら、conceptの勉強がてら抽象化segtreeに挑戦してみました。

上の遅延SegTree / 遅延Segtree2にあるように、大体実装方法は

structを自分で定義してそれをsegtreeに渡す
lambda/関数を演算の個数だけ用意して一気にsegtreeに渡す

の2種類だと思うんですが、今回は両方できるようにしてみました。2018年ならいざ知らず同様の実装がそこら中にあると思う。

コード

こちらです。

#include <vector>
#include <iostream>
#include <numeric>

template <class T>
concept monoid = requires (T& x, typename T::S s) {
    { x.op(s, s) } -> std::same_as<typename T::S>;
    { x.e() } -> std::same_as<typename T::S>;
};

template <monoid M>
struct SegTree {
    using S = M::S;

    M m;
    std::vector<S> v;

    SegTree(M _m, std::vector<S> _v) : m(_m), v(_v) {
    }

    S all_prod() {
        // TODO optimize :)
        S val = m.e();
        for (auto x : v) {
            val = m.op(val, x);
        }
        return val;
    }
};

template <class T, class OP, class E>
struct LambdaMonoid {
    using S = T;
    S op(S a, S b) { return _op(a, b); }
    S e() { return _e(); }

    LambdaMonoid(OP op, E e) : _op(op), _e(e) {}
  private:
    OP _op;
    E _e;
};
template <class OP, class E>
LambdaMonoid(OP op2, E e2)->LambdaMonoid<decltype(e2()), OP, E>;

// --- ここまでライブラリ ---

struct AddInt {
    using S = int;
    S op(S a, S b) { return a + b; }
    S e() { return S(0); }
};

int main() {
    std::vector<int> v(10);
    std::iota(v.begin(), v.end(), 0);
    SegTree seg0(AddInt(), v);

    SegTree seg1(
        LambdaMonoid([&](int a, int b) { return a + b; }, [&]() { return 0; }),
        v);

    std::cout << "sum(1..10) = " << seg0.all_prod() << std::endl;
    std::cout << "sum(1..10) = " << seg1.all_prod() << std::endl;

    return 0;
}

タイトルに遅延segtreeとありますが、シンプルに詐欺です。普通のsegtreeしか試してみていません。

解説

まず、最初の数行がいきなり重要です

template <class T>
concept monoid = requires (T& x, typename T::S s) {
    { x.op(s, s) } -> std::same_as<typename T::S>;
    { x.e() } -> std::same_as<typename T::S>;
};

template <monoid M>
struct SegTree {
    using S = M::S;

    M m;
    :

これは、monoid conceptを定義し、struct SegTreeがこのmonoid conceptを満たすMしか受け取れないようにしています。Mがmonoid conceptを満たすとは、

using S = hoge として値の型が定義されている
op(S, S) -> Sをメンバとして持つ
e() -> Sをメンバとして持つ

という、大体atcoder libraryと同じ定義です。例えば下のほうにあるstruct AddIntがmonoid conceptを満たします。

struct AddInt {
    using S = int;
    S op(S a, S b) { return a + b; }
    S e() { return S(0); }
};

なので、こういうAddInt構造体を用意して、main関数の最初で行われているように

    std::vector<int> v(10);
    std::iota(v.begin(), v.end(), 0);
    SegTree seg0(AddInt(), v);

と書けば[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]の格納されたsegtreeが出来ます。

また、わざわざstruct AddIntのようにstructを定義しなくても、ラムダ式を書き並べるだけでsegtreeを使うこともできます。

    SegTree seg1(
        LambdaMonoid([&](int a, int b) { return a + b; }, [&]() { return 0; }),
        v);

これがどういう仕組みかというと、ラムダ式を受け取ってmonoid structのようにふるまうLambdaMonoidもライブラリ側に用意しておきました。

template <class T, class OP, class E>
struct LambdaMonoid {
    using S = T;
    S op(S a, S b) { return _op(a, b); }
    S e() { return _e(); }

    LambdaMonoid(OP op, E e) : _op(op), _e(e) {}
  private:
    OP _op;
    E _e;
};
template <class OP, class E>
LambdaMonoid(OP op2, E e2)->LambdaMonoid<decltype(e2()), OP, E>;

応用編として、「pair<S, S>を使うことで一般のモノイドをReverse可能なモノイドに変換するやつ」とかが実現できると思っています。なんのこっちゃという話ですが、平衡二分木でこういうのが欲しくなります。

template <monoid M> struct AttachReverse {
    using S = std::pair<M::S, M::S>;
    S op(S a, S b) { return {m.op(a, b), m.op(b, a)}; }
    S e() { return {m.e(), m.e()}; }

    S rev(S a) { return {a.second, a.first}; }

    AttachReverse(M _m) : m(_m) {}

  private:
    M m;
};

結論

全てが懐古

よすぽの日記

遅延Segtree3

大嘘昔話

2023年

コード

解説

結論