Luogu P3369 【模板】普通平衡树 01Tire树解法-526互联

题目传送门

闲话：Luogu总共105篇题解中只有4篇01Tire树解法，虽说是非正解但未免也太少了些（貌似也不少？）……总之01Tire树的效率并不低，这道题用01Tire是很轻松的。

Q：这题为什么可以用01Tire树解？

能否解决一个问题，无非于三个点：可行性，空间，时间。

本题要求维护一个有序数集，能进行元素修改和查询。

而01Tire树通过数字的二进制01串储存，根据这条特性，01Tire树就可以作为维护有序数集的天然容器。

可行性上，01Tire树可解，至于空间和时间，等到代码部分结束后再讨论。

话不多说，接下来就进入01tire树解法详解

首先看到数据范围 $|x| \le 10^7$ ,意识到数据中可能有负数，然而01Tire只能维护非零整数，于是使用最简单粗暴的方法：给所有数字加上 1e7 ，在输出时再减去即可。

这样数据范围就变成了 $ x \le 2 * 10^7 $ ，实际上根据01Tire建树的方法，这样只会增加一层，因此不用担心时空爆炸。

由于01Tire树所需空间比较大，因此我习惯于提前预估一下01Tire的深度，编译 log2(2e7) = 24.2 于是取 25 作为01Tire的深度。

至此，我们可以写出来基本的插入删除操作了。

//插入操作
void insert( int x ){
	int u = 0 , ic ;
	for( reg i = 24 ; i+1 ; i-- ){
		ic = ( x >> i ) % 2;
		if( !tire[u][ic] ) tire[u][ic] = ++tot;
		u = tire[u][ic];
	}
	word[u]++;
}
//删除操作
void delete_( int x ){
	int u = 0 , ic ;
	for( reg i = 24 ; i+1 ; i-- ){
		ic = ( x >> i ) % 2;
		u = tire[u][ic];
	}
	word[u]--;
}

其中 word[i] 表示以 $i$ 结尾的数字个数。

查询 $x$ 在当前数集中的排名

我们将所有儿子按照 0 儿子在左，1 儿子在右画图，最终会发现：对于所有的叶子节点，从左到右，代表的数字依次增大，这也是我在前面说“01Tire树是天然的有序数集容器”的原因。

这下，我们只需要检查 $x$ 数字左边的数字个数就可以了。

注意到，如果有一个数字小于 $x$ ，那么这个数字和 $x$ 路径中一定存在一个公共节点，使得 $x$ 路径向右遍历，这个数字向左遍历。

也可以理解为，倘若 $x$ 在这个节点右转，那么在这个节点左转的所有数字一定比 $x$ 小，因为这个数字必然在 $x$ 的左侧。

于是我们就可以通过这个得到查询排名的方法了：遍历 $x$ 的路径，对于路径中 $1$ 的节点，统计这个 $1$ 节点的兄弟 $0$ 节点下的数字个数
最终加上1得到 $x$ 的排名。

//查询某数的排名
int search_top( int x ){
	int u = 0 , ic ; 
	int tp = 1 ;
	for( reg i = 24 ; i+1 ; i-- ){
		ic = ( x >> i ) % 2 ;
		if( ic ) tp += list[ tire[u][0] ];
		//如果当前儿子是1，那么加上0儿子的数字个数 
		u = tire[u][ic];
	}
	return tp;
}

其中 list[i] 表示 $i$ 节点下的数字个数。

维护 list 数组的方法也很简单，加入操作时在每一个经过的节点上进行 list[u]++ 操作，删除时进行 list[u]-- 操作即可。

查询排名为 $x$ 的数字。

我们从源点开始，带着我们要查询的排名 $x$ ，我们遇到了左儿子 $l$ ，左儿子下有 list[l] 个数字，右儿子 $r$ ，有 list[r] 个数字。

如果有 $ x \le list[l] $ 那么证明我们要查询的数字必然在左子树中，进入左子树即可。

如果有 $ x > list[l] $ 那么我们要查询的数字在右子树中，进入右子树。

然而我们还有两个重要的事情要做：

因为进入了右子树，意味着我们在这一位选择了 $1$ ,所以应该在记录路径的数字上加入 ( 1 << i ) 。
因为接下来我们要在右子树中查询，不考虑左子树，所以应当对排名 $x$ 减去左子树的数字个数，接下来的操作是 “查询右子树的第 x - list[l] 名 ”。

遍历到底，我们就成功获得了排名 $x$ 的数字，不要忘记减去 1e7 。

//查询排名为 x 的某数
int top_search( int x ){
	int u = 0 , lf , rg ;
	int as = 0 ;
	for( reg i = 24 ; i+1 ; i-- ){
		lf = tire[u][0];
		rg = tire[u][1];
		//lf 和 rg是两个子节点的坐标
		if( list[lf] >= x && lf ) u = lf ;
		//左子树直接进入即可 
		else if( rg ){
			x -= list[lf];
			as += ( 1 << i );
			//减去左子树数字个数，记录1 
			u = rg;
		}
	}
	return as-1e7;
	//减去1e7恢复原来的数字 
}

最后两个操作，查询小于（大于） $x$ 的第一个数字。

按照我们之前的画图方法，可以看出来：

小于 $x$ 的第一个数字，实际上就是排名为 $x$ 排名-1 的数字，因此可以有最简单的操作方法：

插入 $x$ → 查询 $x$ 的排名 → 查询排名-1的数字并输出 → 删除 $x$

为了防止 $x$ 不在当前集合中，我们先插入，查询后再删除，保证查询时 $x$ 一定存在。

按照这样的思路，我们也可以做到查询大于 $x$ 的第一个数字了：

插入 $x$ → 查询 $x$ 的排名 → 查询排名+word[x]的数字并输出 → 删除 $x$

为了方便理解，这里word[x]暂时表示 $x$ 这个数字的个数，代码中还是保持此前的定义。

特别的，由于我们需要调用当前数字个数，需要把 insert 函数中的根节点拿出来作为全局变量，或者直接将 insert 函数改成 int 型函数返回根节点。

//查询小于x的第一个数字
void search_before( int x ){
	
	insert(x);
	int top = search_top(x)-1;
	printf("%d\n",top_search(top));
	delete_(x);
	
}
//查询大于x的第一个数字
void search_after( int x ){
	
	insert(x);
	int top = search_top(x) + word[u_];
	printf("%d\n",top_search(top));
	delete_(x);
	
}

其中 u_ 是我们在 insert(x) 操作中维护的根节点。

终于完成了所有操作。