MIT Open Course
MIT-retroactive-data-structure
Time line
Insert(time, ops); Delete(time, ops); Query(time, query);
How to insert ops into two times? -> BST || linked list
How to deal with side effect? -> save all the ops except delete
Partial Retroactive
Query always done at present => time = $ \infty $
Full Retroactive
Query can done at whatever time
What about formal defination of partial & full
$ query(t,A \cup B) \equiv f(query(t,A),query(t,B)) , f \ is \ O(1)$
Implementation
segment tree : BST on time
Commutative updates => 可交换updates
$ x.y = y.x $
Invertible updates => 可逆updates
$ x.x^{-1} = \emptyset $
Delete(time, ops) === Insert(now, ops^{-1})
Practice
Dynamic hashing
Priority queue
- query will cost $ O(lgn) $
- store in BBST (balanced binary search tree)
- leaves : insert => store by time not value
General Transformation
rollback: change r time in the past will cost $ O(r) $
lower bound: $ \Omega(r) $
More complicated - Non-oblivious Retroactive
which means after one insert or delete ,you can get the query that change
Just a little bit code
retroactive queue: GitHub-Functional.js
Reference: Retroactive Data Structures - ERIK D. DEMAINE, JOHN IACONO, STEFAN LANGERMAN