LazySegtree
(Data_structure/LazySegtree.hpp)

• View this file on GitHub
• Last update: 2023-07-23 08:43:35+00:00
• Include: #include "Data_structure/LazySegtree.hpp"

モノイド$(S, +, e)$と、それに対する作用素モノイド$(F, \circ, id)$ であり、

• $\forall a \in S ~~ id(a) = a$
• $\forall a, b \in S, \forall f \in F ~~ f(a + b) = f(a) + f(b)$
• $\forall a \in S, \forall f, g \in F ~~ f(g(a)) = (f \circ g)(a)$ を乗せる。

$a_0, a_1, \ldots, a_{N-1} \in S$ について、

• $a_l + \cdots + a_{r-1}$ を返す(prod)
• $a_l + \cdots + a_{r-1}$ に $f$ を作用させる(apply) がともに $O(\log N)$ でできる。

たとえば区間加算区間最小取得なら、

struct M {
    using T = long long;
    static T op(T a, T b) { return min(a, b); }
    static T e() { return INF; }
};
struct O {
    using T = long long;
    static T op(T a, T b) { return a + b; }
    static T e() { return 0; }
};
M::T fn(O::T f, M::T x) { return x + f; }

とする。

ACLと、

• S -> M::T
• op -> M::op
• e -> M::e
• F -> O::T
• mapping -> fn
• composition -> O::op
• id -> O::e

と対応している。

コンストラクタ

(1) LazySegtree<M, O, fn> seg(int N)
(2) LazySegtree<M, O, fn> seg(vector<M::T> v)

• (1) 長さNですべてM::e()の数列で初期化
• (2) vの内容で初期化

計算量

• $O(N)$

set

void seg.set(int p, M::T x)

a[p]にxを代入する。

制約

• $0 \leq p < N$

計算量

• $O(\log N)$

get

M::T seg.get(int p)

a[p]の値を取得する。

制約

• $0 \leq p < N$

計算量

• $O(\log N)$

prod

M::T seg.prod(int l, int r)

a[l],...,a[r-1]の和を返す。

制約

• $0 \leq l \leq r \leq N$

計算量

• $O(\log N)$

all_prod

M::T seg.all_prod()

a[0],...,a[N-1]の和を返す。

計算量

• $O(1)$

apply

(1) void seg.prod(int p, O::T f)
(2) void seg.prod(int l, int r, O::T f)

• (1) a[p]にfを作用させる
• (2) a[l],...,a[r-1]にfを作用させる

制約

• (1) $0 \leq p < N$
• (2) $0 \leq l \leq r \leq N$

計算量

• $O(\log N)$

Verified with

• Test/aoj-DSL-2-H.test.cpp
• Test/aoj-DSL-2-I.test.cpp

Code

template <class M, class O, auto fn> struct LazySegtree {
    using S = typename M::T;
    using F = typename O::T;
    static_assert(is_convertible_v<decltype(fn), std::function<S(F, S)>>);

  public:
    LazySegtree() : LazySegtree(0) {}
    LazySegtree(int n) : LazySegtree(std::vector<S>(n, M::e())) {}
    LazySegtree(const std::vector<S>& v) : n(int(v.size())) {
        while ((1 << log) < n) log++;
        size = 1 << log;
        d = vector<S>(2 * size, M::e());
        lz = vector<F>(size, O::e());
        for (int i = 0; i < n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) update(i);
    }

    void set(int p, S x) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return M::e();
        l += size; r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }
        S sml = M::e(), smr = M::e();
        while (l < r) {
            if (l & 1) sml = M::op(sml, d[l++]);
            if (r & 1) smr = M::op(d[--r], smr);
            l >>= 1; r >>= 1;
        }
        return M::op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = fn(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return;
        l += size; r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1; r >>= 1;
            }
            l = l2; r = r2;
        }
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

  private:
    int n, size, log = 0;
    vector<S> d;
    vector<F> lz;

    void update(int k) { d[k] = M::op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = fn(f, d[k]);
        if (k < size) lz[k] = O::op(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = O::e();
    }
};

#line 1 "Data_structure/LazySegtree.hpp"
template <class M, class O, auto fn> struct LazySegtree {
    using S = typename M::T;
    using F = typename O::T;
    static_assert(is_convertible_v<decltype(fn), std::function<S(F, S)>>);

  public:
    LazySegtree() : LazySegtree(0) {}
    LazySegtree(int n) : LazySegtree(std::vector<S>(n, M::e())) {}
    LazySegtree(const std::vector<S>& v) : n(int(v.size())) {
        while ((1 << log) < n) log++;
        size = 1 << log;
        d = vector<S>(2 * size, M::e());
        lz = vector<F>(size, O::e());
        for (int i = 0; i < n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) update(i);
    }

    void set(int p, S x) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return M::e();
        l += size; r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }
        S sml = M::e(), smr = M::e();
        while (l < r) {
            if (l & 1) sml = M::op(sml, d[l++]);
            if (r & 1) smr = M::op(d[--r], smr);
            l >>= 1; r >>= 1;
        }
        return M::op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = fn(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return;
        l += size; r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1; r >>= 1;
            }
            l = l2; r = r2;
        }
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

  private:
    int n, size, log = 0;
    vector<S> d;
    vector<F> lz;

    void update(int k) { d[k] = M::op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = fn(f, d[k]);
        if (k < size) lz[k] = O::op(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = O::e();
    }
};

Back to top page