Randomized binary search tree

いつか貼ろうと思ってました。始めて学べた頃は可読性の高いソースコード見当たらなくて（中国人のコードはもう。。）、理解に色々と苦労しましたOrz、もちろん自分のがわかりやすいとも言えませんが、もし分からない部分があれば是非コメントして下さい、知ってる限り答えます。

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

www.slideshare.net
Treapをまだよく知らない方は iwiさんのスライドを見てください、すごくわかりやすいです。
セグメント木が使えない場合は多いですよね、区間の分解、マージ、反転、挿入、削除などなど、変化はたくさんあります。
こういう場合は平衡二分探索木を使うことになります。その中でも実装量が一番少ないのはTreapです（相対に遅い方だが、そんなに遅くもない）。
挿入と削除は分解とマージができれば軽々とできますので、分解&マージを中心とする二分木を僕は使います。
RBST( Randomized Binary Search Tree )　とTreap はどちらもランダムを用いて平衡を保ちます。Treapはノードが新しく作成するたび、priorityをランダムでそのノードの上に記録させます。しかしRBSTはそれを記録せず、マージの時にサイズで左か右が上にいるべきかを判断します。僕にはTreapが何故速いのかは証明できないけど、もしTreapが言う ( a->pri > b->pri ) で aをb の上に置くのが合ってるとしたら、二つの木をマージする場合、根のpri にだけ注目します、それぞれのpri は必ずその木の中で一番大きいので、「aとb の中にも一番大きいpri はどっちにいるか」と言うことを判断することになります。当たり前にも、サイズが大きい方がその一番大きいpri を持つノードを含む可能性が高いですよね。 数式に変えるとつまり「a->size / ( a->size + b->size ) 」の確率でa が上にあるべきだと、Treap の精神が伝わります。なので、pri を記録しなくてもTreap のように動けるRBST です。何故pri をそんなに無くしたいのかと言うと永続データ構造する時それがかなり問題になるからです、いつかそれも説明してみます。
3580 -- SuperMemo
POJ 3580 SuperMemo

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXINT = ~( 1 << 31 );

struct Rbst{
    int val, minv, size, add, rev; // treapだとおまけにpri を記録する
    Rbst *lc, *rc;
    Rbst(int _v):val(_v),minv(_v),size(1),add(0),rev(0),lc(NULL),rc(NULL){}
    void push(){
        if( add ){
            val += add;
            minv += add;
            if( lc ) lc->add += add;
            if( rc ) rc->add += add;
            add = 0;
        }   
        if( rev ){
            swap( lc, rc );
            if( lc ) lc->rev ^= 1;
            if( rc ) rc->rev ^= 1;
            rev = false;
        }
    }
    void pull(){
        size = 1;
        minv = val;
        if( lc ){
            lc->push();
            size += lc->size, minv = min( minv, lc->minv );
        }
        if( rc ){
            rc->push();
            size += rc->size, minv = min( minv, rc->minv );
        }
    }
} *root;
int size(Rbst *t){ return t ? t->size : 0; }
// split k elements from t to a, t->size - k elements to b
void split(Rbst *t, int k, Rbst *&a, Rbst *&b){
    if( !t ) a = b = NULL;
    else{
        t->push();
        if( size( t->lc ) >= k ){
            b = t; // can gurantee *b will not take more than enough
            split( t->lc, k, a, b->lc );
            b->pull();
        } else{
            a = t;
            split( t->rc, k - size( t->lc ) - 1, a->rc, b );
            a->pull();
        }
    }
}
int rnd(){ // ライブラリのランダムは範囲が小さい、でもこれを使ってもそんなに速くもならない、ハハ
    static int rand_seed = 20160207; // すごく大きい素数と掛け算して勝手にオーバーフローさせる
    return rand_seed = ( rand_seed * 0xdefaced + 1 ) & MAXINT;
}
Rbst* merge(Rbst *a, Rbst *b){
    if( !a || !b ) return a ? a : b;
    if( rnd() % ( a->size + b->size ) < a->size ){ // Treapだと a->pri > b->pri
        a->push();
        a->rc = merge( a->rc, b );
        a->pull();
        return a;
    } else{
        b->push();
        b->lc = merge( a, b->lc );
        b->pull();
        return b;
    }
}

void ADD(Rbst *&t, int x, int y, int D){
    Rbst *tl, *tr;
    split( t, x - 1, tl, t );
    split( t, y - x + 1, t, tr );
    t->add += D;
    t = merge( tl, merge( t, tr ) );
}

void REVERSE(Rbst *&t, int x, int y){
    Rbst *tl, *tr;
    split( t, x - 1, tl, t );
    split( t, y - x + 1, t, tr );
    t->rev ^= 1;
    t = merge( tl, merge( t, tr ) );
}

void REVOLVE(Rbst *&t, int x, int y, int T){
    T %= y - x + 1;
    Rbst *tl, *tr;
    split( t, x - 1, tl, t );
    split( t, y - x + 1, t, tr );
    
    Rbst *tt;
    split( t, t->size - T, t, tt );
    t = merge( tt, t );

    t = merge( tl, merge( t, tr ) );
}

void INSERT(Rbst *&t, int x, int P){
    Rbst *tt;
    split( t, x, tt, t );
    t = merge( tt, merge( new Rbst( P ), t ) );
}

void DELETE(Rbst *&t, int x){
    Rbst *tl, *tr;
    split( t, x - 1, tl, t );
    split( t, 1, t, tr );
    t = merge( tl, tr );
}

int MIN(Rbst *&t, int x, int y){
    Rbst *tl, *tr;
    split( t, x - 1, tl, t );
    split( t, y - x + 1, t, tr );

    int res = t->minv;

    t = merge( tl, merge( t, tr ) );
    return res;
}

char op[21];
int main(){
    int n; scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        int v; scanf("%d", &v);
        root = merge( root, new Rbst( v ) );
    }
    int m; scanf("%d", &m);
    for(int i = 0; i < m; ++i){
        scanf("%s", op);
        if( strcmp( op, "ADD" ) == 0 ){
            int x, y, D; scanf("%d %d %d", &x, &y, &D);
            ADD( root, x, y, D );
        } if( strcmp( op, "REVERSE" ) == 0 ){
            int x, y; scanf("%d %d", &x, &y);
            REVERSE( root, x, y );
        } if( strcmp( op, "REVOLVE" ) == 0 ){
            int x, y, T; scanf("%d %d %d", &x, &y, &T);
            REVOLVE( root, x, y, T );
        } if( strcmp( op, "INSERT" ) == 0 ){
            int x, P; scanf("%d %d", &x, &P);
            INSERT( root, x, P );
        } if( strcmp( op, "DELETE" ) == 0 ){
            int x; scanf("%d", &x);
            DELETE( root, x );
        } if( strcmp( op, "MIN" ) == 0 ){
            int x, y; scanf("%d %d", &x, &y);
            printf("%d\n", MIN( root, x, y ));
        }
    }
    return 0;
}