RBST
Randomized Binary Search Tree
ABC170 E Commentary on.
Ordered multisets can be processed quickly by using C++ multisets, etc.
and therefore, what is the equivalent of multiset in C++ in Python? and the topic was raised
multiset in Python There are many cases where you can get by with heapq.
Python does not have equilibrium binary tree in the standard library
I felt like it would be a good idea to have it as my own library...
Implementations that make nodes as objects are generally bad.
Because of the high cost of generating objects.
Implement in arrays and make with the policy to compile in numba.
AC on ABC170E
--- Development
C++ implementation ported to Python
Summary of data structures that can retrieve the kth value fast - such as BIT upper binary search and equilibrium binary search tree - Qiita, ported naively from
https://github.com/nishio/atcoder/blob/master/memo/rbst_normal.py
Replace ABC170 E implementation in Fennic tree with RBST and verify AC in all test codes
Implementation in phoenix tree 4.83sec
Implementation in RBST 105.47sec
20 times slower
Remove class
67.01sec
About 60% faster.
Remove recurrence call and compile with [numba
10.13sec
Sequential addition in list changed to batch allocation in np.array
4.60sec
---
This page is auto-translated from /nishio/RBST using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.