Python3 I don't know the balanced binary search tree, but I wish I had a sorted set.

Introduction conclusion

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.

(4.13 postscript)

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) $.

What kind of reason?

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.

Constraint

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.

Conclusion

Well, it's faster than thinking about an ordered set with set ... Equilibrium binary search tree seems more convenient (end)

Every article has an end

By the way, I didn't write the code.

Recommended Posts

Python3 I don't know the balanced binary search tree, but I wish I had a sorted set.
I use python but I don't know the class well, so I will do a tutorial
I tried LeetCode every day 108. Convert Sorted Array to Binary Search Tree (Python, Go)
I tried LeetCode every day 110. Balanced Binary Tree (Python, Go)
Write a binary search in Python
I don't know the value error
[Emacs] I had a problem installing the Python auto-completion package jedi (mac)
Search the maze with the python A * algorithm
I didn't know the basics of Python
python I don't know how to get the printer name that I usually use.
[Introduction] I tried to implement it by myself while explaining the binary search tree.
I don't know what HEIC is. But for the time being, let's use PNG!
I investigated the calculation time of "X in list" (linear search / binary search) and "X in set"