链接 multiset失效了,我不得不去学习平衡树了,但是我偶然接触到了FHQ 平衡树,发现还不错,代码简单好理解 与AVL不同,FHQ实现的是分裂与合并操作,插入撤除都很方便,而且一般不会被特殊数据给卡住 重点函数是split和merge,split将要分裂的函数按val分裂为x和y两个部分(两棵树),merge则相反,将两棵树合并起来 这样插入操作就只需要将root按val拆开,在合并x和单独的val,接着全部一起合并即可 删除操作则将root按val-1,val拆成x,y,z三部分,这样我们只需要删除y的一个节点再全部合并就好了 至于获取排名,将root按val-1拆成x,y两部分,这样...