セグ木

はじめに

この記事はあくまで自分のためのメモです.他人が読むことは想定していません.

セグ木とは

区間に対する操作を高速に行うデータ構造.
完全二分木で区間をまとめて,操作する要素を減らす.

セグ木で管理できる構造

扱いたい集合Sと演算\otimesが「モノイド」であることが必要.具体的には,以下のことを満たさなければいけない.

  1. 結合法則を満たす.つまり,任意の要素a,b,c\in Sについて,a\otimes (b\otimes c)=(a\otimes b)\otimes cが成立する.
  2. 単位元が存在する.つまり,ある要素e\in Sについて,任意の要素a \in Sa\otimes e=e\otimes a=aが成立する.

もっと砕けた表現をすると,

  1. 計算する順番を入れ替えても結果が変わらない
  2. どんな要素に対して演算しても結果が変わらないものが存在する

ということ.

例えば実数同士の足し算について,

  1. \forall_{a\in S}.\forall_{b\in S}.\forall_{c\in S}. a+(b+c)=(a+b)+c
  2. \forall_{a\in S}.a+0=0+a=a

が成立する.つまり,集合\mathbb{R}と演算+は0を単位元とするモノイドであるといえる.

一点更新区間取得

いわゆる普通のやつ.

概要

集合Sと演算\otimesについて,

  • update(a,x):kxを変更
  • query(l,r):[l,r]\otimesした値を返す

の2つを処理する.
0-indexedで,区間を閉区間で扱うとして考えていく.また,要素数n=2^kに調整する.
ちなみに実装は半開区間が楽らしいけど,普段はライブラリなので実装が重くても別にいいし,わかりやすいからこのようにしてる.
0-indexedにおいて,根を0とすると,子はx\times 2+1,x\times 2+2,親はx/2-1になる.また,要素xx+n-1に格納されている.
updateは葉を変更し,根まで登りながら更新していき,
queryは引数に(a,b,k,l,r)をもって「[a,b]のクエリを処理していて,[l,r]を格納しているkを見ている」のようにして再帰していくとよい.

実装

template<typename Monoid>
struct SegTree{
    //0-indexed
    using F=function<Monoid(Monoid,Monoid)>;
    int size;       //要素数
    vector<Monoid> dat;
    const F func;   //二項演算
    const Monoid Mdef;  //初期値
    SegTree(int sz,const F func,const Monoid &Mdef):func(func),Mdef(Mdef)
    {
        size=1;
        while(size<sz){
            size*=2;
        }
        dat.assign(size*2,Mdef);
    }
    void set(int k,const Monoid&x){
        //k番目の要素をxで初期化
        //あとでbuildが必要
        dat[k+size-1]=x;
    }
    void build(){
        //構築 O(N)
        for(int k=size-2;k>=0;k--){
            dat[k]=func(dat[k*2+1],dat[k*2+2]);
        }
    }
    void update(int k,const Monoid& x){
        //k番目の要素をxに変更 O(log N)
        int now=k+size-1;
        dat[now]=x;
        while(now){
            now=(now-1)/2;
            dat[now]=func(dat[now*2+1],dat[now*2+2]);
        }
    }
    Monoid _query(int a,int b,int k,int l,int r){
        if(r<a||b<l){
            return Mdef;
        }
        if(a<=l&&b>=r){
            return dat[k];
        }
        auto tl=_query(a,b,k*2+1,l,(l+r)/2);
        auto tr=_query(a,b,k*2+2,(l+r)/2+1,r);
        return func(tl,tr);
    }
    Monoid query(int l,int r){
        //[l,r]に対する演算funcの結果を返す O(log N)
        return _query(l,r,0,0,size-1);
    }
    Monoid operator[](const int &k)const{
        return dat[k+size-1];
    }
};

テンプレートで型を,コンストラクタの引数でサイズ,演算,単位元を与える.

問題を解く

上のソースを貼ればあとは演算と単位元を決めるだけであるから,実質モノイド作成コンテスト(ほんまか
なので,各問題について二項演算f単位元eだけ書いていく.

DSL2-1 Range Minimum Query(RMQ)

Aizu Online Judge
f(x,y)=min(x,y)
e=2^{31}-1

DSL2-2 Range Sum Query

Aizu Online Judge
f(x,y)=x+y
e=0

この記事はここで途切れている…(数式とかが辛いのじゃあ~~~