比如平衡树维护正整数集,线段树做法就让根节点表示区间[1,inf]内有多少个数,一开始线段树是空的,每次插入一个数的时候把需要的节点建出来,每次至多新增O(log范围)的节点。节点上要记录左右儿子是谁,以及区间内的数的个数。然后查询k大、查询rank都和平衡树一样。但是这样做内存O(nlog范围),如果题目允许离线那么可以离散化再线段树,空间就是O(n)了。
如果是平衡树维护实数集,就必须先离散化在做;如果是平衡树维护序列类型的需要提取区间的问题,就做不动了。
如果是平衡树维护实数集,就必须先离散化在做;如果是平衡树维护序列类型的需要提取区间的问题,就做不动了。