Rajveer_100's blog

By Rajveer_100, history, 2 years ago, In English

Hey Guys! =========

I am really so happy to share my custom Order-Statistic Tree using Red Black trees, with the Select(x, i) and Rank(x)...which allow in finding the order statistic and the rank of the key element in log(n) time...

Now I do know that PBDS in C++ does exist, but as a challenge I built this..with great hardwork..and also took reference from CLRS which helped me in understanding the working of this data structure...

At first I actually encountered this problem in CSES named Josephus Problem, and that could be solved using Circular Doubly Linked Lists (in O(N) time) as well, but even O(NlogN) would suffice so I thought of doing so...A pretty fun experience in building own custom stuff, apart from the STL...

Also wanted the opinion of you guys, on how can I improve my work or further make some new functionalities to it in the future, or even build more such data structures allowing iterators like begin() and end() for the same..As far as the debugging part I have submitted the code as well just to be sure of any errors..

CSES Josephus Problem 2 -> Accepted Code

Thank You So Much!

Have a great day ahead!!!

Here is my Code in C++ :

Spoiler

Full text and comments »

  • Vote: I like it
  • +79
  • Vote: I do not like it