Python set can manage a set, but since the element does not have an index, the operation "output the xth element from the smallest" can be performed only with $ O (N) $ for the number of elements N. not.
Ah, it's too late.
In conclusion, Binary Indexed Tree and binary search yield $ O ((logN) ^ 2) $. I'm not sure if it can be made faster.
Thank you for pointing out Mr. Salmonize and Mr. joe. Although it is $ O ((logN) ^ 2) $, by applying the binary search on BIT, the binary search part does not need the query processing of BIT, and it is accelerated to $ O (logN) $.
Prepare a Binary Indexed Tree (BIT). What? Don't know BIT? https://ja.wikipedia.org/wiki/フェニック木
If we add x to the set, let's say we add +1 to the xth element of BIT. For example, I want to make a set of {3, 1, 4}! If you think
+1 to the third element of the BIT array +1 to the first element of the BIT array +1 to the 4th element of the BIT array
This is OK.
Now let's consider lower_bound. Binary search. When you want the xth element from the smallest
When a binary search is performed using the judgment "Is there x or more elements less than or equal to y?", The number of elements less than or equal to y can be found by $ O (logN) $ in BIT.
Furthermore, the binary search itself costs $ O (logN) $, so
The total is $ O ((logN) ^ 2) $. I see.
If you want to handle floats and strs, you need to devise. If it is float, you can multiply the original number by a constant, and str can use the character code, but it does not look practical.
It may also be vulnerable to online queries as it is not as strong as you might think for dynamic changes. Even when storing a large number, it will not work unless coordinate compression is performed.
Well, it's faster than thinking about an ordered set with set ... Equilibrium binary search tree seems more convenient (end)
By the way, I didn't write the code.
Recommended Posts