在Python中的有序统计红黑二叉树

Question

是否有实现顺序统计红黑二叉树的python库？到目前为止，我还没有找到。在

我要解决的问题是：

给定一个序列：1,2,3,4,1,4,2,3：标签->1,2,3,4

将第一次出现的标签i称为L\U i，将第二次出现的标签i称为U\i

我想计算j的个数，这样索引（L_I）<；index（L_j）而index（U U I）<；index（U uj）代表所有I

Input : 1,2,3,4,1,4,2,3 
Output :  4 

因为| j |=3，因为索引（L_1）<；索引（L{2,3,4}）和索引（U|1）

这可以在theta(n^2)中通过对每个点的数组进行线性搜索来完成，但是使用平衡顺序统计RBTree可以帮助在theta(n*log(n))中完成这一任务。在

我的想法是：

^{pr2}$

搜索时，如果找不到标签，请插入标签并返回0:O（logn）

搜索时，如果找到标签，则删除它并计算大于该值的节点数并返回该数字