双対セグメント木

1. 双対セグメント木と呼ばれているらしいもの

まず遅延セグメント木を理解してください
http://tsutaj.hatenablog.com/entry/2017/03/30/224339

発祥
https://kimiyuki.net/blog/2019/02/22/dual-segment-tree/

できること

• 区間作用 / 1点取得 の Segment Tree
• 遅延セグメント木は 区間作用 / 区間取得 だが、機能を落として時間と空間を改善する (2倍くらい)

実装

通常、遅延セグメント木は値の配列と遅延の配列を持つが、ここでは値の配列は最下段だけ、遅延の配列は最下段以外を持つ
このとき、区間加算・区間代入・区間chmin などのクエリの場合、作用 2 つをマージする操作と、値に作用を適用する操作が同じであるため、遅延の配列と値の配列をつなげて 1 つの遅延の配列と思うことができて、うれしい。

using ll = long long;
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }


template<class T>
struct DualSegmentTree{
    virtual void c(T&, const T&) = 0;
    ll size = 1, rank = 0;
    vector<T> lazy;
    const T def_lazy;
    DualSegmentTree(ll n, const T& def_value, const T& def_lazy): def_lazy(def_lazy){
        while(size < n){
            size *= 2;
            rank++;
        }
        lazy.assign(size * 2, def_lazy);
        for(ll i = size; i < size * 2; i++) lazy[i] = def_value;
    }
    DualSegmentTree(const vector<T>& v, const T& def_lazy): def_lazy(def_lazy){
        while(size < v.size()){
            size *= 2;
            rank++;
        }
        lazy.assign(size * 2, def_lazy);
        for(ll i = 0; i < v.size(); i++) lazy[size + i] = v[i];
    }
    void push(ll at){
        if(!at) return;
        ll r = 31 - __builtin_clz(at);
        for(ll i = r; i > 0; i--){
            ll a = at >> i;
            if(lazy[a] != def_lazy){
                c(lazy[a * 2], lazy[a]);
                c(lazy[a * 2 + 1], lazy[a]);
                lazy[a] = def_lazy;
            }
        }
    }
    T operator[](ll at){
        at += size;
        push(at);
        return lazy[at];
    }
    void set(ll at, const T& val){
        at += size;
        push(at);
        lazy[at] = val;
    }
    void query(ll l, ll r, const T& val){
        if(l >= r) return;
        l += size;
        r += size;
        push(l >> __builtin_ctz(l));
        push((r >> __builtin_ctz(r)) - 1);
        for(; l < r; l /= 2, r /= 2){
            if(l & 1) c(lazy[l++], val);
            if(r & 1) c(lazy[--r], val);
        }
    }
};
template<class T>
struct RAQ : DualSegmentTree<T>{
    using Base = DualSegmentTree<T>;
    void c(T& a, const T& b){ a += b; }
    RAQ(ll n, const T& def_value = T(), const T& def_lazy = T()) : Base(n, def_value, def_lazy){}
    RAQ(const vector<T>& v, const T& def_lazy = T()) : Base(v, def_lazy){}
};
template<class T>
struct RUQ : DualSegmentTree<T>{
    using Base = DualSegmentTree<T>;
    void c(T& a, const T& b){ a = b; }
    RUQ(ll n, const T& def_value, const T& def_lazy = numeric_limits<T>::max()) : Base(n, def_value, def_lazy){}
    RUQ(const vector<T>& v, const T& def_lazy = numeric_limits<T>::max()) : Base(v, def_lazy){}
};
template<class T>
struct RchmQ : DualSegmentTree<T>{
    using Base = DualSegmentTree<T>;
    void c(T& a, const T& b){ chmin(a, b); }
    RchmQ(ll n, const T& def_value, const T& def_lazy = numeric_limits<T>::max()) : Base(n, def_value, def_lazy){}
    RchmQ(const vector<T>& v, const T& def_lazy = numeric_limits<T>::max()) : Base(v, def_lazy){}
};

2. 双対セグメント木ってこれじゃない？

できること

• 区間作用 / 1点取得 の Segment Tree
• 半分にした遅延セグメント木も 区間作用 / 1点取得 だが、作用が 区間加算・区間chmin のような 作用させる順番を入れ替えても結果が変わらない 作用のとき、作用側を通常のセグメント木のように処理することができ、若干速い

実装

ここは半分にした遅延セグメント木と同じ

遅延セグメント木は値の配列と遅延の配列を持つが、値の配列は最下段だけ、遅延の配列は最下段以外を持つ
このとき、区間加算・区間代入・区間chmin などのクエリでは、作用 2 つをマージする操作と、値に作用を適用する操作が同一視できるため、遅延の配列と値の配列をつなげて 1 つの遅延の配列と思うことができて、うれしい。

さらに、遅延させたものを下に伝播させる機能を削除する。
その代わり、1 点取得の際に、遅延させたものを上に取りに行く。
こうすると、通常セグ木の区間取得のように区間作用をし、1 点更新のように 1 点取得をするセグ木ができる。
"区間取得のように区間作用をし、1 点更新のように 1 点取得をする" って双対じゃない？

区間代入のやり方

(時間, 代入する値) をペアにして chmax するとできる。