Segment Tree

概要

1点更新・区間演算(※)が1回当たり O(logN) 出来るデータ構造。

作成part

モノイド

• SegTree上に乗せる演算のこと。以下の2つの規則が成り立つ演算の事を言う。

集合 S とその上の二項演算 •: S × S → S が与えられた時、

1. 結合律：S の任意の元 a, b, c に対して、(a • b) • c = a • (b • c)
2. 単位元の存在：S の元 e が存在して、S の任意の元 a に対して e • a = a • e = a

※単位減は演算の前後で値が変化しない元のこと。足し算における0、 掛け算における1。

method

• set(i, x) : i 番目のノードに x を代入する
• prod(l, r) : [l, r) の半開区間において、予め定義した operation を O(logN) で行う
• all_prod() : 全ての区間における operation の結果を O(1) で行う

Program

template<typename S,S(*op)(S,S),S(*e)()>
struct SegTree{
    SegTree() : n(0){}
    explicit SegTree(ll _n){
        n = _n;
        log2 = 0;
        while((1LL << log2) < n)log2++;
        size = 1LL << log2;
        data = vector<S>(2*size,e());
    }

    void set(ll i,S x){
        // dataの葉のidxを参照する為に足す
        i += size;

        // dataの中で更新を反映させるべきnodeを捜査
        // ※完全二分木を書けば分かる
        data[i] = x; // data[i]はupdate()では不可(葉を参照してるから)
        while(i > 1){
            i /= 2;
            update(i);
        }
    }

    void update(ll i){
        data[i] = op(data[2*i],data[2*i+1]);
    }

    S prod(ll l,ll r){
        l += size, r += size;
        S sml = e(),smr = e();
        while(l < r){
            // ここの処理はmemo参照
            if(l & 1)sml = op(sml,data[l++]);
            if(r & 1)smr = op(data[--r],smr);
            l /= 2, r /= 2;
        }
        return op(sml,smr);
    }

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

    private:
        ll size;
        ll log2;
        ll n;
        vector<S> data;
};