SecondThread's blog

By SecondThread, history, 5 weeks ago, In English,

AlgorithmsThread 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:

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

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

 
 
 
 
  • Vote: I like it
  • +158
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow thanks I needed this, a little offtopic question,is the name derived from algorithm live, both seems very similar, tools are also similar.

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Really appreciate the video, there are not many easy to understand resources available to understand this. Also grateful for all the videos you are making of these hard topics. Keep up the goo work :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks, I'm glad you enjoy them! :)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you ever find free time please make a video on how to solve spoj DQuery ( I could not understand how offline programming is done with segment trees) Thank you!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's ASC?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It stands for Andrew Stankevitch Contest (contests written by the coach of the ITMO ICPC team). Problem G of ASC 37 is the problem about Persistent Queues that I mentioned in the video.

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

thanks @secondThread when u mentionned binary lifting, do u have to precompute all kth ancestors of all nodes in the tree?(where k is a power of two)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Yes, you do. This is pretty easy to implement, since lifting 2^i from node n is the same as lifting 2^(i-1) twice.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you also do Persistent Treaps next? I've never found any good resource or implementation for those.