I want a data-structure which can support two type of operations:
1) Insert an element to it.
2) Find the count of all elements less than K (input).
Help me find the most efficient data-structure for the task.
Please try to explain the implementation of that data-structure as well.
@mishraiit …
This problem can be solved using BIT . (Binary Indexed Tree and Segment tree) with a complexity of O(log(N)) per operation …
If the input is not sorted, I think its a better idea to contruct a BST. Lets say you have first count query for the number (k) and now you have to evaluate it, construct BST at this point of time. If the next query is also of count, use the same BST. If the insertion query comes, using some space, store all the numbers. Till you get the next count query, keep storing numbers. As soon you get the next count query, make bst with all these elements you stored and delete the storage. This will come out to be O(nlogn) in total. This is less complex in understanding also, as compared to segment tree and BST.
You can use BIT and segment tree as said above, for understanding those, refer these:
Also, if the input is sorted, you can just use this segment code code(logarithm in complexity terms):
cin>>n;
for(int i=0;i<n;i++)
{
cin>>ele;
vec.push_back(ele);
}
sort(vec.begin(), vec.end());
it= lower_bound(vec.begin(), vec.end(),5); // returns iterator to first the entry in the vector which will not go before k, which here is 5.
int cnt= it-vec.begin(); // counting the number of elements
cout<<cnt<<endl;
This problem can be solved easily using BIT.
First store all the element in the queries and sort them
Now process query one by one, for addition of element first binary search for the element in array,then update the BIT at that index
For query, again binary search (lower_bound) for the k, and query the BIT at that index
For both of the operation this gives O(log n) complexity
can you please elaborate how do i perform lazy updates in this context.With every insert query, the size of the array increases, so how do we operate on the old intervals?
The input isn’t sorted and I can’t understand how segment tree can be used here.
first of all this approach is not good when we have both operations equally distributed …
yes i was talking about the same but you can also apply coordinate compression initially to reduce the efforts on applying binary search … because we just need to do comparision … so coordinate compression will not cause any harm to us …
Yeah, thats why I mentioned, if the input is “sorted”.
How can segment tree be used here?
To do it with segment tree, you have two options:
1.) Create segment tree every time a count query comes and you have done some insertion after the previous count query.
2.) Just make the segment tree once and use the concept of lazy propagation.