let's say I have a huge set of non-overlapping rectangle with integer coordinates, who are fixed once and for all
I have another rectangle A with integer coordinates whose coordinates are moving (but you can assume that its size is constant)
What is the most efficient way to find which rectangles are intersecting (or inside) A? I cannot simply loop through my set as it is too big. Thanks
edit : the rectangles are all parallel to the axis
Use an R+ tree, which is most likely precisely the specific tree structure you are looking for. R+ trees explicitly do not allow overlapping in the internal (non-leaf) structure in exchange for speed. As long as no object exists in multiple leaves at once, there is no overlap. In your implementation, rather than support overlap, whenever an object needs to be added to multiple leaves, just return true instead.
Here is a detailed description of the data structure, including how to manage rectangles: The R+-tree: A dynamic index for multi-dimensional objects