なんかのデータ構造の紹介(実はWavelet Treeだった)

名前のよくわからないデータ構造について紹介します。
そのデータ構造は、ある順列を受け取り、

• 深さ0ではその順列をそのまま配列にして、深さ1では中央mdで深さ0のときの配列を分け、ｍｄより小さいものはmdより小さいindex、mdより大きいものはmdより大きいindex、となり、mdで分けた二つは深さ0のときの配列の順番が維持されるように、深さ1の配列を作ります。以下、再帰的に、要素が1になるまで繰り返します。

• また、nxt,nxt2という2次元配列を用意し、それぞれの深さで、それぞれの要素をどちらに入れるかに入った段階で、右、左の次の深さの配列がどれだけ埋まっているかを保存したものです。（nxt、nxt2はどちらかさえあればもう片方を求められますが、両方作ったほうが実装が楽です）

これを作ると、例えば長さNの配列aの[b,c]で、K番目に大きい数を見つけたいとき（蟻本にも同じ問題があります）、深さ0では、a[i]が{a}で何番目に大きいか（同じ要素があったら適当に順番つける）を保存し、再帰的に構築。
見つけたい要素が、{a}内で何番目に大きいかは、
まず深さ0からスタートし、[b,c]内で、mdより小さい左に行った要素の数が分かります。
それがk以上なら、次はmdより小さい方を、そうでないならmdより大きい方に、次の深さで調べます。
これを、範囲が1になるまでやります。[b,c]の範囲の更新がちょっと大変なことを除けばあまり難しくないです。
これで、さっきのクエリーにO(logN)で答えられます。（蟻本に載ってるのはO(log^3N)とかです）
K番目の値が求められるので、もちろんRMQの代わりにもなります。
（で空間もNlogNのRMQなんて誰が使うか！！）
nxtは値が連続的でないので、境界とかがちょっとめんどうですね

たぶんコード見た方がはやいです

typedef pair<int,int> pi;
struct SBT{
	int n;
	int val[20][200010];
	int nxt[20][200010],nxt2[20][200010];
	void build(int l,int r,int dep){
		int p=l,md=(l+r)>>1,p2=md;
		for(int i=l;i<r;++i){
			if(val[dep][i]<md){
				val[dep+1][p++]=val[dep][i];
			}else val[dep+1][p2++]=val[dep][i];
			nxt[dep][i]=p;
			nxt2[dep][i]=p2;
		}
		if(r-l>1){
			build(l,md,dep+1);
			build(md,r,dep+1);
		}
	}

	void init(int len,pi* seq){//seq[i]=(要素、もともとの場所)としてソートしたもの
		n=1;
		while(n<len) n<<=1;//2^kになるようにする（しなくても動くけど・・・）
		for(int i=0;i<len;++i) val[0][seq[i].second]=i;
		for(int i=len;i<n;++i) val[0][i]=i;
		build(0,n,0);
	}
	int find(int a,int b,int l,int r,int dep,int k){
//[a,b]でK番目の要素は元の配列内で何番目に大きいか、を求める
//答えは[l,r)の中にあることが保証される
//再帰一つなので、ループ使って書き直せます
		if(r-l==1) return l;
		int md=(l+r)>>1;
		int suma=a==l?l:nxt[dep][a-1],sumb=nxt[dep][b],toleft=sumb-suma;
		if(toleft>=k) return find(a==l?l:nxt[dep][a-1],nxt[dep][b]-1,l,md,dep+1,k);
		else return find(a==l?md:nxt2[dep][a-1],nxt2[dep][b]-1,md,r,dep+1,k-toleft);
	}
};
int n,m;
SBT tree;
pi seq[100005];	
int main(){
	scanf("%d%d",&n,&m);//n:=配列の長さ　m:=クエリー数
	REP(i,n) scanf("%d",&seq[i].first),seq[i].second=i;
	sort(seq,seq+n);
	tree.init(n,seq);
	REP(hoge,m){
		int a,b,k;scanf("%d%d%d",&a,&b,&k);--a;--b;//[a,b]でK番目の数を求めよ
		printf("%d\n",seq[tree.find(a,b,0,tree.n,0,k)].first);
	}

	return 0;
}

他の応用例とかももしかしたらあるかもしれません。

実はWavelet Treeでした(1年経ってから気づいた・・・・)
たぶんこういう問題は他の平行二分探索木でも解ける気がします
僕の実装はWavelet Treeということは間違いなさそうですが適当なサイトからコード拾ってきたので
もしかすると一般的なものとは違うかもしれません