I am looking for a data structure that allows a specific problem to be solved in O(n*log(n)) complexity. It needs to represent a set of integers, in which I can do the following operations : - add an element - check if an element exists in the set - delete every value bigger than a given integer Hopefully with logarithmic complexity.
I looked for linked list since adding an element in the middle and deleting a whole part of the structure is easy, but I don't know how to keep an ordered list or implement a dichotomic search. At first I was considering hash tables but I don't know how to filter the set. I'm looking at balanced binary trees and I do not know if I am looking for something delusional or if it exists somehow and I just can't find it.
For implementing from scratch, I would suggest a Treap.
A Treap is just a binary search tree where every node is given a random priority, and it satisfies the heap condition as a tree. This randomized data structure makes the expected time to find, insert, delete and split the tree be O(log(n)). The first three are fairly straightforward. To split, you just put a node in at the point to split with higher priority than the root. Then one half winds up on one side of that node, and the other half on the other.
Please note, while splitting is O(log(n)), freeing up the deleted bits is O(n).
Please note that you may not have to implement anything. For example in C++ you can just use an std::map. The performance of those operations except the delete are O(log(n)). While deleting a range of length m from a structure of size n is O(m + log(n)). If you consider the comment about freeing memory, that's about ideal.