Covering the unit square by smaller squares of variable sizes
I'd suggest a 2-dimensional k-d tree storing one point for each corner of each rectangle returned.  A quadtree or 2-dimensional interval tree might also work.  More generally, you might consider a 2-dimensional binary space partitioning tree, where you partition based on one of the edges of one of the squares returned (extended horizontally or vertically out to infinity in both directions).

How would you partition, in a binary space partitioning tree?  Each square gives you two horizontal lines and two vertical lines (obtained by extending each edge of the square out to the full unit square).  For instance, imagine sorting all of those vertical lines from left-to-right, and picking the median line, and using that to partition.  Continue splitting recursively.  This gives you a nested tree of regions.  Then, associate each square with the lowest (deepest) node/region that fully contains it.  When you are picking a split for a particular region of space, you use all of the lines that fall within that region (from all squares that have any overlap with that region).