双対セグメント木(Dual Segment Tree)
(datastructure/segmenttree/dualsegtree.cpp)

• View this file on GitHub
• Last update: 2026-03-22 19:39:35+09:00

説明

区間更新・一点取得を扱う双対セグメント木である。 演算は結合則を満たせばよく、各操作は $O(log N)$。

できること

• DualSegmentTree<M> seg(n) 長さ n、初期値がすべて M::e() の双対セグメント木を作る
• void update(int l, int r, T x) 半開区間 [l, r) に作用 x を適用する
• T operator[](int k) 位置 k にかかっている作用の合成結果を返す

使い方

M に using T、static T f(T, T)、static T e() を定義して使う。 f(a, b) は「先に a、後に b を適用した合成」を返すようにする。

struct Monoid {
    using T = long long;
    static T f(T a, T b) { return a + b; }
    static T e() { return 0; }
};

DualSegmentTree<Monoid> seg(n);
seg.update(l, r, x);
long long v = seg[p];

初期配列 a が別にあるときは、seg[p] で得た作用を a[p] に適用して答えを作る。

実装上の補足

この実装は update(l, r, x) が半開区間である。 eval で単位元判定をするため、T には == が必要である。

Verified with

• test/yosupo_range_affine_point_get_dualsegtree.test.cpp

Code

template <class M>
struct DualSegmentTree{
    using T = typename M::T;
    int sz, height{};
    vector<T> lazy;
    explicit DualSegmentTree(int n) {
        sz = 1; while(sz < n) sz <<= 1, height++;
        lazy.assign(2*sz, M::e());
    }

    void eval(int k){
        if(lazy[k] == M::e()) return;
        lazy[(k<<1)|0] = M::f(lazy[(k<<1)|0], lazy[k]);
        lazy[(k<<1)|1] = M::f(lazy[(k<<1)|1], lazy[k]);
        lazy[k] = M::e();
    }
    void thrust(int k){ for (int i = height; i; --i) eval(k>>i); }
    void update(int a, int b, const T &x){
        thrust(a += sz); thrust(b += sz-1);
        for (int l = a, r = b+1;l < r; l >>=1, r >>= 1) {
            if(l&1) lazy[l] = M::f(lazy[l], x), l++;
            if(r&1) --r, lazy[r] = M::f(lazy[r], x);
        }
    }

    T operator[](int k){
        thrust(k += sz);
        return lazy[k];
    }
};
/*
struct Monoid{
    using T = ll;
    static T f(T a, T b) { return a+b; }
    static T e() { return 0; }
};
*/

/**
 * @brief 双対セグメント木(Dual Segment Tree)
 */

#line 1 "datastructure/segmenttree/dualsegtree.cpp"
template <class M>
struct DualSegmentTree{
    using T = typename M::T;
    int sz, height{};
    vector<T> lazy;
    explicit DualSegmentTree(int n) {
        sz = 1; while(sz < n) sz <<= 1, height++;
        lazy.assign(2*sz, M::e());
    }

    void eval(int k){
        if(lazy[k] == M::e()) return;
        lazy[(k<<1)|0] = M::f(lazy[(k<<1)|0], lazy[k]);
        lazy[(k<<1)|1] = M::f(lazy[(k<<1)|1], lazy[k]);
        lazy[k] = M::e();
    }
    void thrust(int k){ for (int i = height; i; --i) eval(k>>i); }
    void update(int a, int b, const T &x){
        thrust(a += sz); thrust(b += sz-1);
        for (int l = a, r = b+1;l < r; l >>=1, r >>= 1) {
            if(l&1) lazy[l] = M::f(lazy[l], x), l++;
            if(r&1) --r, lazy[r] = M::f(lazy[r], x);
        }
    }

    T operator[](int k){
        thrust(k += sz);
        return lazy[k];
    }
};
/*
struct Monoid{
    using T = ll;
    static T f(T a, T b) { return a+b; }
    static T e() { return 0; }
};
*/

/**
 * @brief 双対セグメント木(Dual Segment Tree)
 */

Back to top page