I'd echo Bram and use a grid and actually just for all objects, static and dynamic (though you might store static objects in a separate grid instance, but same data structure for both). You can tune the crap out of it.
As for the grid, it only has to store a 32-bit index in each cell to the grid nodes, like so:
This means you can even store a 100x100 grid (10,000 cells) in just ~40 kilobytes. When elements move from one cell to the next, all you have to do is manipulate some integers to remove the nodes associated (there could be more than one node for a big element) and then insert nodes to the new cells the element belongs.
To avoid resizing the array (vector, i.e.) of nodes (two integers per node) all the time, you can just return them to the free list when they are removed to be reclaimed as needed on subsequent element insertions. That'll make it so you rarely ever have to allocate memory, just manipulate some integers, to move elements from one cell to another.
Here's how you use the nodes as a free list, making their indices double over as a pointer to the next node in a cell or a pointer to the next free node to reclaim.
I've used these types of grids before to animate millions of particles with collision logic in realtime on CPU with just 2-core machines (did involve a lot of SIMD and multithreading, but the grid was key to the collision detection being fast). You can get a lot out of a plain old grid as long as you don't try to represent it naively as like a collection of 100x100 containers that own memory (ex: 100x100 instances of std::vector -- horrible idea). Do it with each cell being a singly-linked list connected just by 32-bit integers into a big array.