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