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