用于快速插入和计数的数据结构/算法

Question

我正在寻找一种数据结构/算法，它允许将元素对数插入数据结构，并允许对数据结构中小于给定value的元素进行对数计数。

例如，std::set<int>允许对数插入，对数iter = std::upper_bound(..., value)但distance(iter, set.begin())是线性的。。。

可以使用C++STL容器来完成吗？

Answer 1

有一种方法，不幸的是，只适用于GNU C++。称为Policy based data structure。

我将展示使用的基本知识。

#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update>
indexed_set;
int main() {
indexed_set s;
s.insert(1);
s.insert(5);
s.insert(10);
s.insert(20);
s.insert(21);
cout << s.order_of_key(10) << 'n';
}

order_of_key返回集合中严格小于传递值的值的数目。

进一步信息：https://codeforces.com/blog/entry/11080