# What is this data structure?!

I saw this solution of a 7* coder from japan
https://www.codechef.com/viewsolution/37088356

and this code of a 6* coder from india
https://www.codechef.com/viewsolution/37100058

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?
@uwi
@taran_1407

2 Likes

I too would like to know

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.

8 Likes

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.

3 Likes