小猪的博客

Retroactive Data Structure

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

title

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