I don't see anyone mentioning here is that properly implemented persistent data structures where the increase in space is low and predictable can be used to eff

I don't see anyone mentioning here is that properly implemented persistent data structures where the increase in space is low and predictable can be used to efficiently store and query the history of data structure's state. One example is querying which polygon from known set contains a point. If all the points are known it can be done using regular sweep line algorithm. Using a persistent ordered tree instead of normal one allows storing it's state over the sweeping process, that removes requirement of knowing all the points at the start. After performing sweeping using persistent data structure query any point can be answered in O(log(n)) time. Similar technique can be applied to convert other offline algorithms that rely on sorting all the data to partially online (queries can be answered one by one without knowing all of them).