SecondThread's blog

AlgorithmsThread 5: Persistent Data Structures
By SecondThread, history, 4 years 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
  • +166
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
4 years 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.

→ Reply
»
4 years 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 :)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's ASC?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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)

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi @history,

How do you suggest one should read these lectures? I am currently a Div. 2 are these good for me or just for absolute beginners?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi: The easiest lectures so far are 1. Segment Trees, and 2. Tree Basics. I'd start with those first. Persistent STs require knowing Segment Trees already.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you also prepare some lectures on Dynamic Segment trees please ?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What's a Dynamic Segment Tree? You mean like a treap/splay tree?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't know much about it either, and have to learn it myself, but I will copy paste to what I got to know from someone :

          Logic
          The code looks something Like this

          I have to learn the concept myself, and I would be very glad if you accept to prepare a video lecture to this topic ( As I feel its a bit advanced for some maybe blue coders to make it ).

          Thank you.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh, those are usually called implicit segment trees, not dynamic segment trees. The idea is just that every time you do a query, you hit log(n) segtree nodes. If you only create the nodes that you ever actually use, rather than all nodes, then you only actually use q*log(MAX_N) memory. This means that it is okay to use them without coordinate compressing even if MAX_N is huge, since you probably will only have ~2*10^5 queries, so your runtime will still be modest.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks for the reply and for the correct naming. However, I tried searching youtube ( now with the name you provided ), if I find some good videos on it, but I couldn't find one.

              Could you please make some lecture on the technique ?

              The technique looks interesting, and pretty useful ( particularly as it will allow a problem to be solved in online setting and not switching to offline solution ).

              And obviously your explanations are always awesome. So, could be please...

              In case you don't agree to making the lecture ( WARNING : Open with caution )
              → Reply