AlgorithmsThread 9: Treaps!

[@carbon13]

The mirroring portion outside was an extremely nice touch.

[@randomdude-kr4in]

What a day to be alive. Can't wait to watch!

[@rohangarg5473]

Thank you David for all the effort you put in making solution videos, screencast and lectures. Just a small suggestion or I should say Request, Kindly do lectures on not so advanced stuff with questions. Just like what you did for tree algorithms(problems on gym + explanation later), that was really helpfull. It would be really great if you could do for other topics as well(not so advanced topics) which can be helpfull and at the same time, frequently used in cf contests. Topics like:- Dp with bitmask Dp on segments Some dp problems which can be solved with recur + memo Graphs Tree dp Array problems increasing decreasing subsequence types. Etc Some gym questions + explanation later would be Great, just the way you did for tree algorithms. Thank you so much

[@maximilianoredigonda8645]

Had this resource be available in my good ol' ICPC times 🔥 hahaha nice job!

[@askdf]

Great video SecondThread! Really looking forward to using treaps in my upcoming contests! :^)

[@LeoLeo-nx5gi]

Ohh Holy, I was wandering everywhere to understand this topic since months, pls do take some problems and pls let us walk through the code step by step ❤️

[@igorlukyanov7434]

Your videos are both funny and interesting. I absolutely love them!

[@joacarrilloco]

Looking for a good treap tuto long ago. Nice video and gonna check out the problems! Thanks

[@rivaille8867]

Thanks for this great tutorial and codeforces problem set , appreciate what you are doing

[@imranfarid8186]

Tbh, I was kind of scared when you brought that axe!:)

[@1732ashish]

I have been waiting to learn one of the balanced search trees and treap seems like a good starting point, I will be thankful if you can mention that case you talked about where you might explicitly need splay trees ?

[@jonathanharmeyer2255]

"Host" David Harmeyer. Woooaahhhh, hold up

[@BleedingKnight]

Great tutorial David. I had two questions though. 1) Since treaps are randomized, what would be some safe constraints in contest problems for which treaps won't reach a height much worse than log(N) and timeout due to that? 2) Since the left to right order is preserved, I guess the relative order of any split up treaps of a larger treap cannot be changed while merging as it won't remain a BST. So I was wondering is there any efficient way to shuffle the order of the elements in a segment (like cyclically shift the segment right by 1) and do range queries on the modified order of elements? EDIT: Nvm about 2. To cyclically shift l...r to one right, we can just mirror l..r and then mirror l+1...r

[@SecondThread]

You don't need to maintain the BST property either. The left to right order is only based on how you merge things, the example in the beginning was just to explain why it was randomized. As for constraints, you're probably safe up to about 2*10^5 but you might need a big time limit depending on how costly your internal operations are.

[@BleedingKnight]

​@@SecondThread Oh okay. But now if we don't maintain the relative order, isn't it possible that the height of the tree changes from logn to something much worse over a lot of queries? For example, if we have n updates where we split treap T at first n - 1 positions getting T1 and T2 as the new treaps and then merge in the order T2 and T1 to form T again, wouldn't this become much worse than logn height eventually? EDIT: Solved the gym contest's A problem. I guess it doesn't.

[@mehulgoel5875]

wow, I'm amazed at your intelligence, the speed you have in solving codeforces problems is wow too, it doesn't even seem you need to think hard about them at all

[@martonnemeth236]

Nice explanation! :)

[@weirongwu4964]

Awesome video! Thanks David! What laptop do you use? Is this the surface pro? Love how you can draw ideas and diagrams out to help you visualize difficult concepts.

[@SecondThread]

I actually use a desktop and have a cheap drawing tablet on from Amazon. It doesn't have a screen or anything, so I'm looking at my monitor, but my hand is just on my desk

[@weirongwu4964]

@@SecondThread Interesting. Thanks David!

[@nuni_boyka7869]

Loved the video awesome!

[@tanishqgupta1071]

He haven't uploaded yet 😂

[@nuni_boyka7869]

@@tanishqgupta1071 doesn't matter my comment would have been same.

[@erray7546]

@@nuni_boyka7869 SecondThread orz

[@dontony7071]

Sir please attend the Div 2 round🥺.Missing your post contest explanations now a lot.

[@YASH_KHICHARIYA]

8:43 Why will it get splitted into 1/3 and 2/3 on average?

[@ДимаАртюхов-э6щ]

Hey, what's up! Are planning to do solutions for last Techno Cup round 2021? If so, I can't wait to see that)

[@nallasivakrishna5693]

The video is awesome.Clearly understood the concept. @second thread could you please provide solutions for codeforces 678 div2 round. It would be really helpful.Thanks in advance.

[@jitendrapandey176]

Come on David ..come on 🔥🔥

[@mikerega7724]

You're the best I hope and one day compete with you why I know what will happen Nothing is impossible

[@fuadalhasan1784]

Hey good morning.. 😊

[@dhairyapurohit8065]

Hey brother if possible please make video on codeforces round 679(tecnicup once) specifically problem C div2 Perform Easily Kind of hard to understand from Tutorial part✌️ thank you

[@shzaizzhang4465]

Thanks.

[@thallium54]

In C++, using a vector to store the nodes is faster than pointers.

[@thallium54]

My implementation: github.com/thallium/acm-algorithm-template/blob/master/code/DataStructure/Treap_split.cpp

[@SecondThread]

That's pretty clean. I like the pass-by-reference so you don't forget to update your treap root

[@xinyuan127]

Wow, thank you :3

[@shubhampokhriyal8491]

Goood morning everybody 😻😻although night is going on

[@satishshingade8514]

very nice

[@RifatulIslam__]

C++ code was helpful

[@hadva2]

Just a general guestion about Java: why do you, while doing competitive programming, put all methods to static? Wouldn't be simpler to just run an instance of the class in the main method and then not need to set everything to static (or is the execution faster with everything on static?).

[@SecondThread]

Yeah, it might be shorter to code. Conceptually I like to save objects for when they are actually in an object of something though; it just makes more sense to me.

[@nicktohzyu]

can treap do stabbing queries like segment tree? which is the problem that requires splay and not treap? why have the two children as `vector` rather than `Treap *left, *right` ?

[@SecondThread]

1) What's a stabbing query? You can do a range query of width 1 if that's what you mean 2) Nothing with a splay tree is *impossible* with a treap, but some things are a log factor slower. An example of this is implementing a Link Cut Tree. That's like the main and only one I know of. 3) So that you can flip left and right really easily. If you access your kids as kids[0^flip], this will always access the *left* kid even when you need to propogate a flip still.

[@mikaoj317]

is it possible to get ur scanner class?

[@puedoamarte]

Do more algorithms please

[@satishshingade8514]

good everybody

[@namitaa]

sir u are fine

[@tsyetsye7689]

Please be my sensei David....orz....!!!!!

[@ritwizsinha1261]

YAYYAYYAYA

[@akashchandra2223]

how did you get so smart, are you naturally inclined

[@mehulgoel5875]

I think he is. Even I find him mind boggling quick in seeing through the problem to the solution. And watching him in action inspires me to atleast try to emulate it. Feels similar to how I felt after watching the movie and tv series "Limitless".

[@karanb2067]

I thought the video said "meap"...whatever tho, good usage of time!

[@ishanpatni2684]

Please share your java template

[@tabletalenovo9695]

Bruh how tf do u do that palindrome problem

[@iprakhar22]

"Finding daddy" hmm ok

[@MohitYadav-yv2rw]

Yummy!!!

[@sathvikkuthuru7804]

orz

[@madhukiranattivilli2321]

I'm sorry! Ur MERGE explanation wasn't understandable at all! U shud've used names to the nodes, or some other style to narrate. U were talking about priorities but u didn't assign any priorities to the nodes while explaining the concept (as an illustration). I hope I'll understand better while watching ur code section.