scapegoat木って実装楽で強くね!?【C++実装あり】

#注意
この先信用するべからず(scapegoat木最近知ってスゲーって人が書いてます)
#はじめに
c++のsetっぽいものを作って行きます
scapegoat木を含む平衡二分木はセグメント木が出来ることとsetが出来ることとmapが出来ること、ランダムアクセスがO(logN)でできます、やばいわよ！
kd木の高速化にも使えます
Scapegoat Tree - 週刊 spaghetti_source - TopCoder部

プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～

を参考にしてます
2つめはtreapですがわかりやすいです
#scapegoat木とは

tree.cpp

template<typename T>
struct search_tree{
    struct node{
        T val;
        int cnt=1;
        node* ch[2]={nullptr,nullptr};
        node(T val):val(val){}
    };
    using np=node*;
    np root=nullptr;
    int count(np t){return t?t->cnt:0;}
    np update(np t){t->cnt=count(t->ch[0])+1+count(t->ch[1]);return t;}

    public:
    void insert(T val){insert(val,root);}
    int lower_bound(T val){return lower_bound(val,root);}

    private:
    void insert(T val,np& t){
        if(!t)t=new node(val);
        else if(val<t->val)insert(val,t->ch[0]);
        else if(val>t->val)insert(val,t->ch[1]);
        update(t);
    }
    int lower_bound(T val,np t){
        if(!t)return 0;
        if(val==t->val)return count(t->ch[0]);
        if(val<t->val)return lower_bound(val,t->ch[0]);
        else return count(t->ch[0])+1+lower_bound(val,t->ch[1]);
    }
};

これは二分探索木です
簡単ですが最悪計算量がO(n)です
なのでこうします

scapegoat_tree.cpp

template<typename T>
struct scapegoat_tree{
    struct node{
        T val;
        int cnt=1;
        int dep=0;
        node* ch[2]={nullptr,nullptr};
        node(T val):val(val){}
    };
    using np=node*;
    np root=nullptr;
    int count(np t){return t?t->cnt:0;}
    int depth(np t){return t?t->dep:0;}
    np update(np& t){
        t->cnt=count(t->ch[0])+1+count(t->ch[1]);
        t->dep=max(depth(t->ch[0]),depth(t->ch[1]))+1;
        if(depth(t)>3*(log2(count(t))+1))rebuild(t,get(t));
        return t;
    }

    public:
    void insert(T val){insert(val,root);}
    int lower_bound(T val){return lower_bound(val,root);}

    private:
    void insert(T val,np& t){
        if(!t)t=new node(val);
        else if(val<t->val)insert(val,t->ch[0]);
        else if(val>t->val)insert(val,t->ch[1]);
        update(t);
    }
    int lower_bound(T val,np t){
        if(!t)return 0;
        if(val==t->val)return count(t->ch[0]);
        if(val<t->val)return lower_bound(val,t->ch[0]);
        else return count(t->ch[0])+1+lower_bound(val,t->ch[1]);
    }
    void rebuild(np& t,vector<T> v){
        if(v.size()==0){t=nullptr;return;}
        int n=v.size();
        int mid=n/2;
        t=new node(v[mid]);
        vector<T> v1(mid),v2(n-mid-1);
        for(int i=0;i<mid;i++)v1[i]=v[i];
        for(int i=mid+1;i<n;i++)v2[i-mid-1]=v[i];
        rebuild(t->ch[0],v1);
        rebuild(t->ch[1],v2);
        update(t);
    }
    vector<T> get(np t){
        if(!t)return vector<T>();
        auto v1=get(t->ch[0]),v2=get(t->ch[1]);
        v1.push_back(t->val);
        v1.insert(v1.end(),all(v2));
        return v1;
    }
};

はいdepthなるものが追加されてupdate内からgetとrebuildが呼ばれてるのがわかります
要するに平衡じゃない部分木があったら小さいところから作り直すだけ
(追記:ちょっとくらい平衡じゃなくても許さないととても遅くなるっぽい。怖い)
小さいところから作り直す関係上nodeのupdateとまとめられるはず(要出典)
getはある要素の子要素をvectorとして格納でO(nlogn)(nは子要素の数)
rebuildはgetした要素をもとに強引に作る
コードそのままで中央値で左右に分けるだけ
これがscapegoat木です！！！
#eraseの追加
eraseされたらremovedというflagをtrueにして
数にはcountしない、恐らくdepthにはcountしたほうがいい
作り直しのときは入れない
でOK
簡単

scapegoat_tree.cpp

template<typename T>
class sset{
    struct node{
        T val;
        int cnt=1;
        int dep=0;
        bool removed=0;
        node* ch[2]={nullptr,nullptr};
        node(T val):val(val){}
    };
    using np=node*;
    np root=nullptr;
    int count(np t){return t?t->cnt:0;}
    int depth(np t){return t?t->dep:0;}
    np update(np& t){
        t->cnt=count(t->ch[0])+(!t->removed)+count(t->ch[1]);
        t->dep=max(depth(t->ch[0]),depth(t->ch[1]))+1;
        if(depth(t)>3*log(count(t))+1)rebuild(t);
        return t;
    }

    public:
    void insert(T val){insert(val,root);}
    void erase(T val){erase(val,root);}
    int lower_bound(T val){return lower_bound(val,root);}

    private:
    void insert(T val,np& t){
        if(!t)t=new node(val);
        else if(val==t->val&&t->removed)t->removed=0;
        else if(val<t->val)insert(val,t->ch[0]);
        else if(val>t->val)insert(val,t->ch[1]);
        update(t);
    }
    void erase(T val,np& t){
        if(!t)return;
        else if(val==t->val)t->removed=1;
        else if(val<t->val)erase(val,t->ch[0]);
        else if(val>t->val)erase(val,t->ch[1]);
        update(t);
    }
    int lower_bound(T val,np t){
        if(!t)return 0;
        if(val==t->val)return count(t->ch[0]);
        if(val<t->val)return lower_bound(val,t->ch[0]);
        else return count(t->ch[0])+1+lower_bound(val,t->ch[1]);
    }
    void rebuild(np& t){
		np v[t->cnt];
		auto Y=[&](auto f){return[&](auto... args){return f(f, args...);};};
		int idx=0;
		auto f=Y([&](auto f,np t)->void{
			if(!t)return;
			f(f,t->ch[0]);
			v[idx++]=t;
			f(f,t->ch[1]);
		});
		f(t);
		auto g=Y([&](auto g,int l,int r)->np{
			if(l>=r)return nullptr;
			v[(l+r)/2]->ch[0]=g(g,l,(l+r)/2);
			v[(l+r)/2]->ch[1]=g(g,(l+r)/2+1,r);
			return update(v[(l+r)/2]);
		});
		t=g(0,t->cnt);
    }
};

#応用

###ランダムアクセス
setにも実装しろ

T get_by_order(int idx){return get_by_order(idx,root);}
T get_by_order(int idx,np t){
    assert(0<=idx&&idx<count(t));
    if(idx==count(t->ch[0]))return t->val;
    else if(idx<count(t->ch[0]))return get_by_order(idx,t->ch[0]);
    else return get_by_order(idx-count(t->ch[0])-1,t->ch[1]);
}

###mapみたいなやつ
update関数を使ってkeyの位置のvalueを更新します
一番下のupd関数は更新方法で、今はaddです
例えば
t.update(1,3);
t.update(1,4);
t.update(1,5);
のとき1は3->7->12と変わっていきます
他にも便利な機能をたくさん入れてますが難しいことはないはずです

scapegoat_tree.cpp

template<typename T,typename E>
class scapegoat_tree{
    struct node{
        T key;E val;
        int cnt=1;
        int dep=0;
        bool removed=0;
        node* ch[2]={nullptr,nullptr};
        node(T key,E val):key(key),val(val){}
    };
    using np=node*;
    np root=nullptr;
    int count(np t){return t?t->cnt:0;}
    int depth(np t){return t?t->dep:0;}
    np update_node(np& t){
        t->cnt=count(t->ch[0])+(!t->removed)+count(t->ch[1]);
        t->dep=max(depth(t->ch[0]),depth(t->ch[1]))+1;
        if(depth(t)>3*(log2(count(t))+1)){
            rebuild(t,get(t));
        }
        return t;
    }

    public:
    void update(T key,E val){update(key,val,root);}
    void erase(T key){erase(key,root);}
    int lower_bound(T key){return lower_bound(key,root);}
    T get_key_by_order(int idx){return get_node_by_order(idx,root)->key;}
    E get_by_order(int idx){return get_node_by_order(idx,root)->val;}
    T get(T key){auto t=get_node_by_key();return t?t->val:T();}

    int count(T key){return get_key_by_order(lower_bound(key))==key;}

    private:
    void update(T key,E val,np& t){
        if(!t)t=new node(key,val);
        else if(key==t->key&&t->removed){
            t->removed=0;
            t=new node(key,val);
        }
        else if(key==t->key){
            t->val=upd(t->val,val);
        }
        else if(key<t->key)update(key,val,t->ch[0]);
        else if(key>t->key)update(key,val,t->ch[1]);
        update_node(t);
    }
    void erase(T key,np& t){
        if(!t)return;
        else if(key==t->key)t->removed=1;
        else if(key<t->key)erase(key,t->ch[0]);
        else if(key>t->key)erase(key,t->ch[1]);
        update_node(t);
    }
    int lower_bound(T key,np t){
        if(!t)return 0;
        if(key==t->key)return count(t->ch[0]);
        if(key<t->key)return lower_bound(key,t->ch[0]);
        else return count(t->ch[0])+1+lower_bound(key,t->ch[1]);
    }
    np get_node_by_key(T key,np t){
        if(!t)return nullptr;
        if(key==t->key)return t;
        if(key<t->key)return get_node_by_key(key,t->ch[0]);
        else return count(t->ch[0])+1+get_node_by_key(key,t->ch[1]);
    }
    np get_node_by_order(int idx,np t){
        assert(0<=idx&&idx<count(t));
        if(idx==count(t->ch[0]))return t;
        else if(idx<count(t->ch[0]))return get_node_by_order(idx,t->ch[0]);
        else return get_node_by_order(idx-count(t->ch[0])-1,t->ch[1]);
    }
    void rebuild(np& t,vector<pair<T,E>> v){
        if(v.size()==0){t=nullptr;return;}
        int n=v.size();
        int mid=n/2;
        t=new node(v[mid].first,v[mid].second);
        vector<pair<T,E>> v1(mid),v2(n-mid-1);
        for(int i=0;i<mid;i++)v1[i]=v[i];
        for(int i=mid+1;i<n;i++)v2[i-mid-1]=v[i];
        rebuild(t->ch[0],v1);
        rebuild(t->ch[1],v2);
        update_node(t);
    }
    vector<pair<T,E>> get(np t){
        vector<pair<T,E>>v;
        get(t,v);
        return v;
    }
    void get(np t,vector<pair<T,E>>& v){
        if(!t)return;
        get(t->ch[0],v);
        if(!t->removed)v.emplace_back(t->key,t->val);
        get(t->ch[1],v);
    }
    E upd(E s,E t){
        return s+t;
    }
};

###multisetみたいなやつ
mapを使おうそうしよう

###半群？が乗るやつ(RMQとかRSQが出来る)

#あとがき
簡単、treapより多分簡単
惜しむらくはあまり詳しい解説がない、これも詳しくない