What is this data structure?!

I saw this solution of a 7* coder from japan

and this code of a 6* coder from india

Since both of them use the exact same class LST. I am assuming its something very common. But i dont undrerstand the code its too high level for me. I already have solution ready that uses red-black trees. I am going through the codes of the best programmers out there so that i may learn something new. Can anyone please help me out?


I too would like to know :thinking:

its seems to be some kind of a B tree implementation… but i’m only 30% sure.
Its has to do something about bit manipulation that’s all i am getting.

Better tag them

LST(Long Set Tree) originates from me. Somtimes It is called as “fastset” in Japan.
It is fast implementaion of “previous, next, on and off” for a bit array. Expected number of steps is log_{64} n, and can store 10^9 elements in 128MB.

While similar function can be implemented by Fenwick Tree, van-emde boas tree and etc., LST runs much faster than them because of small number of steps and memory efficiency.

The structure is very simple.
In layer 0, a raw bit array(length n).
In layer 1, a bit array(length n/64), 1 when corresponding 64bit in layer 0 is non-zero, 0 otherwise.
In layer 2, a bit array(length n/64/64), …

In each operation, we check/update layers upward and downward once.

I believe it is not a B-tree because nodes are fixed in the constructor.


Thank you so much!

The credits of this DS is to @uwi. I should have mentioned it.

In context of this problem, it is being used to support following queries on a boolean array of size N

  • set/unset a position
  • set/unset a prefix range
  • Find previous/next set position from position p

So in my solution, I’m iterating over elements in increasing order and setting its position in original array to true and making previous/next queries.

The same operations can be performed using TreeSet also, but LST implementation is working faster.