One which came to mind which possibly might be interesting would be the Bounding Interval Hierarchy[2], where you partition the space but also keep the min/max intervals of all children in each node. The "Instant ray tracing" paper[3] details some interesting techniques for speeding up construction.
Or perhaps it's a rubbish idea, haven't really thought it through.
[1]: https://en.wikipedia.org/wiki/Binary_space_partitioning
[2]: https://en.wikipedia.org/wiki/Bounding_interval_hierarchy