双対セグ木 (dual_segment_tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-01-23 03:30:08+09:00
• Include: #include "dual_segment_tree.hpp"

双対セグ木。

コンストラクタ

1. DualSegmentTree<F, composition, id>(int n)
2. DualSegmentTree<F, composition, id>(vector<F> f)

• 作用素の型 F
• 作用素の合成 $f\circ g$ を返す関数 F composition(F f, F g)
• 作用素の単位元を返す関数 F id()

を受け取り、

1. 長さ n 、初期値 id() で構築。
2. f で構築。

計算量

• $O(n)$

get

F get(int p)

p 番目の作用素を取得。

計算量

• $O(\log n)$

apply

void apply(int l, int r, F f)

$k\in[l, r)$ に対して、$k$ 番目の作用素に f を合成。

計算量

• $O(\log n)$

Verified with

• test/aoj_dsl_d_range_update_query.cpp
• test/aoj_dsl_e_range_add_query_2.cpp
• test/lc_range_affine_point_get.cpp

Code

template <class F, auto composition, auto id>
class DualSegmentTree {
    static_assert(is_convertible_v<decltype(composition), function<F(F, F)>>, "composition must work as F(F, F)");
    static_assert(is_convertible_v<decltype(id), function<F()>>, "id must work as F()");

   public:
    DualSegmentTree() : DualSegmentTree(0) {}
    explicit DualSegmentTree(int n) : DualSegmentTree(vector<F>(n, id())) {}
    explicit DualSegmentTree(vector<F> f) : n(int(f.size())) {
        h = ceil_log2(n);
        siz = (1 << h);
        act = vector<F>(2 * siz, id());
        copy(f.begin(), f.end(), act.begin() + siz);
    }

    F get(int p) {
        assert(0 <= p && p <= n);
        F f = id();
        p += siz;
        for (int i = 0; i <= h; ++i) f = composition(act[p >> i], f);
        return f;
    }

    void apply(int k, F f) { apply(k, k + 1, f); }

    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return;
        l += siz;
        r += siz;

        for (int i = h; i >= 1; --i) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        while (l < r) {
            if (l & 1) apply_inner(l++, f);
            if (r & 1) apply_inner(--r, f);
            l >>= 1;
            r >>= 1;
        }
    }

   private:
    int n, h, siz;
    vector<F> act;

    void apply_inner(int k, F f) { act[k] = composition(f, act[k]); }
    void push(int k) {
        apply_inner(2 * k, act[k]);
        apply_inner(2 * k + 1, act[k]);
        act[k] = id();
    }

    int ceil_log2(int x) {
        int res = 0;
        while ((1 << res) < x) ++res;
        return res;
    }
};

#line 1 "dual_segment_tree.hpp"
template <class F, auto composition, auto id>
class DualSegmentTree {
    static_assert(is_convertible_v<decltype(composition), function<F(F, F)>>, "composition must work as F(F, F)");
    static_assert(is_convertible_v<decltype(id), function<F()>>, "id must work as F()");

   public:
    DualSegmentTree() : DualSegmentTree(0) {}
    explicit DualSegmentTree(int n) : DualSegmentTree(vector<F>(n, id())) {}
    explicit DualSegmentTree(vector<F> f) : n(int(f.size())) {
        h = ceil_log2(n);
        siz = (1 << h);
        act = vector<F>(2 * siz, id());
        copy(f.begin(), f.end(), act.begin() + siz);
    }

    F get(int p) {
        assert(0 <= p && p <= n);
        F f = id();
        p += siz;
        for (int i = 0; i <= h; ++i) f = composition(act[p >> i], f);
        return f;
    }

    void apply(int k, F f) { apply(k, k + 1, f); }

    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return;
        l += siz;
        r += siz;

        for (int i = h; i >= 1; --i) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        while (l < r) {
            if (l & 1) apply_inner(l++, f);
            if (r & 1) apply_inner(--r, f);
            l >>= 1;
            r >>= 1;
        }
    }

   private:
    int n, h, siz;
    vector<F> act;

    void apply_inner(int k, F f) { act[k] = composition(f, act[k]); }
    void push(int k) {
        apply_inner(2 * k, act[k]);
        apply_inner(2 * k + 1, act[k]);
        act[k] = id();
    }

    int ceil_log2(int x) {
        int res = 0;
        while ((1 << res) < x) ++res;
        return res;
    }
};

Back to top page