Efficient Set Operations with Sorted Data Structures

Greetings, aspiring coders! Today, we're going to delve deep into the complexities of data structures, specifically the SortedList, and explore how to handle queries efficiently. This is a common problem, often encountered in numerous data science and algorithmic problems. So let's gear up to unravel the mysteries of SortedList operations, and get our hands dirty with some interactive problem solving!

Before delving into the task, let's understand what a SortedList is and why we would use it. SortedList is a data structure from the sortedcontainers Python module. As the name suggests, it keeps the data sorted in an ascending order after every insertion or deletion.

Advantages of using SortedList:

1. Extracting minimum (sorted_list[0]) or maximum (sorted_list[-1]) values will be a constant time operation, i.e., $O(1)$ as they are always at the start or end of the list.
2. Achieving sorted order after every insertion or deletion is quicker with SortedList (with time complexity $O(log N)$) compared to re-sorting a normal list after every mutation (which has a time complexity $O(N log N)$).

Understanding these operations can help us utilize SortedList efficiently for our problem.

The SortedList data structure includes a useful function called bisect_right.

The bisect_right function finds the insertion point for a given value in the sorted list to maintain sorted order. If the element already exists in the list, the insertion point is after (or to the right of) any existing entries. The method returns an index representing the first element in the list that is greater than the value provided.

For example, if we have a SortedList as [1, 2, 4, 6, 8], bisect_right(4) will return 3, as index 3 is the first element greater than 4, and this is where 4 would be inserted to maintain sorted order if duplicates were allowed in the list.

Similarly, the bisect_left function finds the leftmost insertion point for a given value in the sorted list, which also happens to be the index of the first element that is not less than the value, i.e., equal to or greater than the value.

Both operations are performed quickly, with a time complexity of $O(log N)$.

Here is an example of how you would use bisect_left and bisect_right on a SortedList:

from sortedcontainers import SortedList

sorted_list = SortedList([1, 2, 4, 4, 6])
idx_1 = sorted_list.bisect_left(4)
idx_2 = sorted_list.bisect_right(4)
print(idx_1, idx_2)  # Output: 2 4