Dynamic all-pairs shortest paths - O(1) query
theory results:

exact: 

Jittat Fakcharoenphol, Satish Rao: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5): 868-889 (2006)

approximate:

Ittai Abraham, Shiri Chechik, Cyril Gavoille: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. STOC 2012: 1199-1218

Philip N. Klein, Sairam Subramanian: A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica 22(3): 235-249 (1998)

implementation for road networks:

Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato Fonseca F. Werneck: Customizable Route Planning. SEA 2011: 376-387

(updates only to cost of edges, might be possible to extend to addition and deletion of edges)

comment

none of the methods above achieves O(1) query time

note that if you use lots of space for a data structure, it probably means that you will need significant time to update the data structure in case the graph changes
(low query time at the cost of high update time)

if updates are rare, it might be worth it.
what is the application?