Dual Segment Tree
(datastructure/dual_segtree.hpp)

• View this file on GitHub
• Last update: 2023-03-05 19:05:08+09:00
• Include: #include "datastructure/dual_segtree.hpp"

概要

• 区間更新・一点取得ができるデータ構造。

使い方

• dual_segtree<F, composition, id>(n, is_commutative = false): 長さ n の数列 a を作る。F は作用の型。composition は $f \circ g$ を計算する関数。id は $id$ を返す関数。$\cdot$ が可換である場合は commutative = true にするとよい。
• apply(l, r, x): a_l, ..., a_r に x を作用させる。
• get(p): a_p を求める。

Verified with

• test/library-checker/range_affine_point_get.test.cpp

Code

#include <vector>
template <class F, F (*composition)(F, F), F (*id)()>
struct dual_segtree {
public:
    dual_segtree() {
    }
    dual_segtree(int n, bool is_commutative = false)
        : is_commutative(is_commutative) {
        size = 1;
        height = 0;
        while (size < n) size <<= 1, height++;
        lz.assign(2 * size, id());
    }
    void apply(int l, int r, const F &f) {
        l += size;
        r += size - 1;
        if (!is_commutative) thrust(l);
        if (!is_commutative) thrust(r);
        r++;
        while (l < r) {
            if (l & 1) lz[l] = composition(f, lz[l]), ++l;
            if (r & 1) --r, lz[r] = composition(f, lz[r]);
            l >>= 1, r >>= 1;
        }
    }
    F get(int p) {
        if (is_commutative) {
            F ret = id();
            p += size;
            while (p > 0) {
                ret = composition(lz[p], ret);
                p >>= 1;
            }
            return ret;
        } else {
            thrust(p += size);
            return lz[p];
        }
    }

private:
    int size, height;
    std::vector<F> lz;
    bool is_commutative;
    inline void propagate(int k) {
        lz[2 * k + 0] = composition(lz[k], lz[2 * k + 0]);
        lz[2 * k + 1] = composition(lz[k], lz[2 * k + 1]);
        lz[k] = id();
    }
    inline void thrust(int k) {
        for (int i = height; i > 0; i--) propagate(k >> i);
    }
};

#line 1 "datastructure/dual_segtree.hpp"
#include <vector>
template <class F, F (*composition)(F, F), F (*id)()>
struct dual_segtree {
public:
    dual_segtree() {
    }
    dual_segtree(int n, bool is_commutative = false)
        : is_commutative(is_commutative) {
        size = 1;
        height = 0;
        while (size < n) size <<= 1, height++;
        lz.assign(2 * size, id());
    }
    void apply(int l, int r, const F &f) {
        l += size;
        r += size - 1;
        if (!is_commutative) thrust(l);
        if (!is_commutative) thrust(r);
        r++;
        while (l < r) {
            if (l & 1) lz[l] = composition(f, lz[l]), ++l;
            if (r & 1) --r, lz[r] = composition(f, lz[r]);
            l >>= 1, r >>= 1;
        }
    }
    F get(int p) {
        if (is_commutative) {
            F ret = id();
            p += size;
            while (p > 0) {
                ret = composition(lz[p], ret);
                p >>= 1;
            }
            return ret;
        } else {
            thrust(p += size);
            return lz[p];
        }
    }

private:
    int size, height;
    std::vector<F> lz;
    bool is_commutative;
    inline void propagate(int k) {
        lz[2 * k + 0] = composition(lz[k], lz[2 * k + 0]);
        lz[2 * k + 1] = composition(lz[k], lz[2 * k + 1]);
        lz[k] = id();
    }
    inline void thrust(int k) {
        for (int i = height; i > 0; i--) propagate(k >> i);
    }
};

Back to top page