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