By SecondThread, history, 17 months ago,

# 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!

• +166

 » 17 months ago, # |   0 Wow thanks I needed this, a little offtopic question,is the name derived from algorithm live, both seems very similar, tools are also similar.
•  » » 17 months ago, # ^ |   +10 yes it is.
 » 17 months ago, # |   +13 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 :)
•  » » 17 months ago, # ^ |   +3 Thanks, I'm glad you enjoy them! :)
•  » » » 17 months ago, # ^ |   0 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!
 » 17 months ago, # |   0 What's ASC?
•  » » 17 months ago, # ^ |   +8 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.
 » 17 months ago, # |   -8 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)
•  » » 17 months ago, # ^ |   -8 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.
 » 17 months ago, # |   +3 Can you also do Persistent Treaps next? I've never found any good resource or implementation for those.
 » 16 months ago, # |   0 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?
•  » » 16 months ago, # ^ |   0 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.
•  » » » 16 months ago, # ^ |   0 Can you also prepare some lectures on Dynamic Segment trees please ?
•  » » » » 16 months ago, # ^ |   0 What's a Dynamic Segment Tree? You mean like a treap/splay tree?
•  » » » » » 16 months ago, # ^ |   0 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 : LogicIt basically is a way to use segment trees when the coordinates/N is huge (10^9 or 10^18) and they work in O(log(MAX)). Also they can do everything that can be done with regular segment trees. The only caveat is that their constant is a bit larger than regular semgent trees so in practice they are ~1.2-1.5 slower which is still fine for most problems.The main idea is that initially you only have the root node and you extend it to the left/right only when there is a query that affects those nodes. This way this problem can be solved in O(log 10^18) online without compression (and probably it will pass). The code looks something Like thisnode* query(int ql, int qr, int l, int r, node *root) { if(ql <= l && r <= qr) { DO SOMETHING return root; } int mid = (l + r) >> 1; if(root->l == NULL) { root->l = new node(); } if(root->r == NULL) { root->r = new node(); } if(ql <= mid) { root->l = query(ql, qr, l, mid, root->l); } if(mid < qr) { root->r = query(ql, qr, mid + 1, r, root->r); } root->pull(); return root; } 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.
•  » » » » » » 16 months ago, # ^ |   0 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.
•  » » » » » » » 16 months ago, # ^ |   0 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 )I could do more buttering as well XD.