Algorithms Dead 5: Persistent Data Structures

Hello everyone! I just uploaded Episode 5 of Algorithms Dead in which I talk about persistent data structures. I talk about the ASC problem involving a persistent queue, describe how persistent segment trees work, and provide some interesting problems that can be solved and then optimized with persistent segment trees.

Some problems discussed in this video if you are interested in solving them yourself:

• kth min on an l-r segment on an array in log(n)

• kth min on a path in a tree in log(n)

Harder PST problems (not covered in the episode but good practice):

• Literally just dijkstra's algorithm, but weights can be absolutely massive powers of 2

Let me know if you have any questions of suggestions for how I can improve the series!