Programming

Great answer!!

After thinking about all this for a while, I've gone with the basic binary tree (leaning towards AVL tree as I expect my use case to be read heavy).

In my use case, multiple 'intervals' can merge together without major penalty (and should be merged together). It looks like a lot of these interval trees (including ph trees) are best when the intervals need to be kept separate.

There is a part of my algorithm where ph trees might be useful though. I'll have to give it some though.

I'm kind of shocked that a basic binary tree ended up being so usable. Its a classic for a reason, lol. I guess I saw the intervals and got confused and overcomplicated things....

I have not used it for 1 dimension

Querying for all intervals (x’, y’) that overlap with an interval (x, y) is a two dimensional range query that selects the upper left quadrant of the x-y plane that satisfies x < y’ && x’ < y

And typical RAM speeds are 100GB/second for CPUs and 500GB/second on GPUs, meaning 512MB operations are literally on the order of 5 miliseconds for CPU and 1ms on GPU.

Below certain sizes, the 'billions of intervals' is larger than the damn Bitmask. Seriously, 8 bytes per interval (aka one pointer and 0 data) and that's 8GB for the data structure.

Instead of a billion 32-bit intervals to store (4GB of RAM at the minimum) it's obviously a better move to store 500-million byte Bitmasks. And modern GPUs can crush that in parallel with like 3 lines of CUDA anyway.