segment tree(遅延)

何度も部分加算をして、被らなかった場合、最小値の習得の時にまとめて更新できるので処理が速くなる

遅延なしの場合は部分加算ごとに全要素更新する必要があるが、遅延を使うとlognで一旦保留にできる

template< typename Monoid, typename OperatorMonoid = Monoid >
struct LazySegmentTree
{
    using F = function< Monoid(Monoid, Monoid) >;
    using G = function< Monoid(Monoid, OperatorMonoid) >;
    using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;
    using P = function< OperatorMonoid(OperatorMonoid, int) >;

    int sz;
    vector< Monoid > data;
    vector< OperatorMonoid > lazy;
    const F f;
    const G g;
    const H h;
    const P p;
    const Monoid M1;
    const OperatorMonoid OM0;

    //size、 関数、 int_max、0
    LazySegmentTree(int n, const F f, const G g, const H h, const P p,
        const Monoid& M1, const OperatorMonoid OM0)
        : f(f), g(g), h(h), p(p), M1(M1), OM0(OM0)
    {
        sz = 1;
        while (sz < n) sz <<= 1; //一番下の行以外
        data.assign(2 * sz, M1); //INFで初期化
        lazy.assign(2 * sz, OM0);//OM0(0)なら更新不要
                                 //代入された値が入る
    }

    void set(int k, const Monoid& x)//k番目にxを代入
    {
        data[k + sz] = x;
    }

    void build()//値をセットした後準備
    {
        for (int k = sz - 1; k > 0; k--) {
            data[k] = f(data[2 * k + 0], data[2 * k + 1]);
        }
    }

    //遅延があれば実行(kの値)
    void propagate(int k, int len)
    {
        if (lazy[k] != OM0) {//0(変更なし)でないなら

            if (k < sz) {//1つ下を更新(上書きを防ぐため)
                lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
                lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
            }
            data[k] = g(data[k], p(lazy[k], len));
            lazy[k] = OM0;//更新済みにする
        }
    }

    //x:加算する値、  k:基本は1、  [l,r)までxを足す
    Monoid update(int a, int b, const OperatorMonoid& x, int k, int l, int r)//値の範囲加算

    {// k:現在見ているノードの位置  [l,r):data[k]が表している区間

        propagate(k, r - l);//kを更新()
        if (r <= a || b <= l) {//範囲外
            return data[k];
        }
        else if (a <= l && r <= b) {//範囲内
            lazy[k] = h(lazy[k], x);//h:(a+b)
            propagate(k, r - l);//最終決定の部分範囲
            return data[k];
        }
        else {//一部が被る
            return data[k] = f(update(a, b, x, 2 * k + 0, l, (l + r) >> 1),
                update(a, b, x, 2 * k + 1, (l + r) >> 1, r));//下の範囲へ
        }
    }

    Monoid update(int a, int b, const OperatorMonoid& x)
    {
        return update(a, b, x, 1, 0, sz);//全範囲にxを足す
    }

    //最小値を習得
    Monoid query(int a, int b, int k, int l, int r)
    {
        propagate(k, r - l);//kを更新
        if (r <= a || b <= l) {//範囲外
            return M1;
        }
        else if (a <= l && r <= b) {//範囲内
            return data[k];//
        }
        else {
            return f(query(a, b, 2 * k + 0, l, (l + r) >> 1),
                query(a, b, 2 * k + 1, (l + r) >> 1, r));//下の範囲へ
        }
    }

    Monoid query(int a, int b)
    {
        return query(a, b, 1, 0, sz);//全範囲、1から開始
    }

    Monoid operator[](const int& k)
    {
        return query(k, k + 1);
    }
};

//add 区間 min
auto f = [](int a, int b) { return min(a, b); };
auto g = [](int a, int b) { return a + b; };
auto h = [](int a, int b) { return a + b; };
auto p = [](int a, int b) { return a; };
LazySegmentTree< int > seg(N, f, g, h, p, INT_MAX, 0);

auto f = [](int a, int b) { return a + b; };
auto p = [](int a, int b) { return a * b; };
LazySegmentTree< int > seg(N, f, f, f, p, 0, 0);