Disclaimer: We are talking about data structures, not physics. This specific type of data structure allows for retroactively updating and querying the past. We walk through an example of a retroactive queue and its incredible ability to view and change the past in O(log(N)) time.
Timestamps:
0:00 Intro
1:08 Analogy at the bar
8:48 Example and Explanation
19:00 Order-Statistic Trees
22:33 The Consistency Problem
Thanks to Ivan Mastev for filming the video!
Animations created using Manim Community.
Filmed using Sony A7III in 4K.
Lens used: Samyang 14mm f/2.8.
Edited in Davinci Resolve 18.
References:
Retroactive Data Structures, Erik Demaine:
https://erikdemaine.org/papers/Retroa...
Frequently Asked Questions:
https://github.com/mitkonikov/competi...
Collection of Algorithms and Data Structures:
https://github.com/mitkonikov/atlas
Code for the animations:
https://github.com/mitkonikov/animations