Hello Codeforces,
This is my first constructive blog on this platform.
Introduction
ordered_set is a PBDS(Policy Based Data Structure) that provides all the functionalities of a set, such as logarithmic time complexity for insertion, deletion, and searching. However, it also allows additional operations, including finding the k-th smallest/largest element and finding the order statistics. (more about PBDS could be found on this blog)
An ordered_multiset is an ordered_set which allows duplicates.
After experimenting with the ordered_multiset, I discovered that the find and erase functions were not functioning as expected. Consequently, I took it upon myself to create my own implementation of an ordered_multiset and decided to share it with you.
Lets call it COS Custom Ordered Set :)
The whole idea is to efficiently maintain a sorted array like structure so that we can answer all of the required queries efficiently.
Here we will be using the idea of insertion-sort algorithm with some improvements.
In the insertion sort algorithm, the process of inserting an element from the unsorted array into its correct position within the sorted subarray can be viewed as a two-step process.
- we find the appropriate position in the sorted array where we can insert our new element.
- we shift some elements in the sorted array in order to make space for the new element.
step 1: is an O(log n) time operation using a binary search technique.
step 2: is a linear time operation if we use ordinary arrays and it needs to be optimized.
Now since we can successfully insert an element at its required position in O(log n) time complexity we can move forward with our tutorial.
One way to solve this problem is to represent each element as an array index.
Let us denote [i]: number of occurences of i in our treap
we store this information in Fenwick Tree so that we can efficiently calculate prefix sums.
So fenwickTree.prefixSum(v) : number of elements less or equal to v present in our treap.
Now the position where the element E is inserted will be prefixSum(E - 1) {Assuming 0-based indexing}.
insert(int v) {
idx = fenwickTree.prefixSum(v - 1);
treap.insert(idx, v);
fenwickTree.update(v, 1);
}
Data Structures like Fenwick Tree or Segment Tree could be maintained for getting the range Sum.
So far we are maintaining 2 data structures (Fenwick Tree & Treap) to insert an element in a sorted array in O(log n) time complexity.
Deletion from this could also be done in similar fashion.
- We get the element position by taking the prefix sum from our fenwick tree.
- We erase the element from our treap and decrease the value at that particular index in fenwick tree.
erase(int v) {
idx = fenwickTree.prefixSum(v - 1);
treap.erase(idx);
fenwickTree.update(v, -1);
}
Now lets implement the order_of_key() function.
order_of_key(int v) {
return fenwickTree.prefixSum(v - 1);
}
Our next function is find_by_order()
find_by_order(int idx) {
return treap.get_element_at(idx);
}
Now we will be using order_of_key() and find_by_order() to implement lower_bound() and upper_bound() functions.
lower_bound(int v) {
idx = order_of_key(v);
return find_by_order(idx);
}
upper_bound(int v) {
return lower_bound(v + 1);
}
One small optimization
Problem:
Here as you can see that the representation of elements is done through array indexes which brings a limitation to its maximum value.
Solution:
We can use a coordinate compression technique to solve this problem. See the final code for more clarity.
Finally here is the code that summarizes all of the techniques mentioned above.
A small Problem solved using this template:
Problem: 847D - Dog Show
Solution: 209667978
That is all for this tutorial. Thank you for investing your time on reading this blog. If you find anything wrong or want to suggest any improvement then feel free to comment below.
