CCD*_*CCD 6 c++ algorithm data-structures
我有一个排序数组,我在其中使用二进制搜索(std::upper_bound)O(logn)及时找到小于特定值的项目数.
现在我想在保持排序的同时插入和删除此数组.我希望整体的复杂性O(logn).
我知道,使用二叉搜索树或者std::multiset我可以做的插入,删除和UPPER_BOUND的O(logn),但我不能够做得到的距离/指数(std::distance是O(n)用于集)在对数时间.
那么有没有办法实现我想做的事情？
您可以通过在每个节点中包含"子树大小"数据成员(以及标准"左子","右子"和""来扩充任何平衡二元搜索树数据结构(例如红黑树)价值"成员".然后,当您从根向下导航到该元素时,可以计算小于给定元素的元素数.
它增加了相当多的簿记,当然这意味着你需要使用自己的平衡二元搜索树实现而不是标准库中的实现; 但它非常可行,并且它不会影响任何操作的渐近复杂性.