AlgorithmsThread 3: Segment Trees

Рет қаралды 27,078

Күн бұрын

In this video, I talk about segment trees, lazy propagation, and discuss a hard segment tree problem at the end. Segment trees are a very important technique to understand in competitive programming because they can be used for lots of cool tricks on arrays and trees.
If you have any questions, please ask them here: codeforces.com/blog/entry/79284
(If you just DM me, other people won't be able to see the answers)
This is a bit easier of an episode than usual because the next two episodes will be hard segment tree topics and that way people can go watch this if they aren't comfortable with normal segment trees.
Here is Matt Fontaine's episode on Segment Trees that I mentioned in this video: • Episode 4 - Segment Trees
Timestamps:
0:00 Good Morning
1:10 Segment Tree Intro
4:35 Range Queries
12:40 Point Updates
14:30 Code example
24:00 Range Updates
29:15 Lazy Prop Alternatives
31:03 Lazy Prop Common Mistakes
35:18 Sneetches (Hard Problem Example)

Пікірлер: 40

@nichkecoder7762 3 жыл бұрын

Nice stuff man, keep it up! By far the most valuable CP channel on YT!

@AnuragPandey-om6sp 3 жыл бұрын

This was amazing lecture! I enjoyed the last problem discussion!

@fastio8489 3 жыл бұрын

This is the best explanation I found for Segment Trees on youtube. Thanks a ton.

@ruvxei 2 жыл бұрын

This was a beautiful explanation. Thank you!!!

@ayushgupta6913 3 жыл бұрын

Gr8 man!!!! Haven't seen such a great content, ahead of many.

@pleaseexplain4396 2 жыл бұрын

Fantastic Explanation of this hard concept!

@ronakgupta7492 2 жыл бұрын

Great explanation, David!! Could you please make one informational video on Aho-corasick and A*search ? Thank you :)

@gatoradeee 3 жыл бұрын

Can you provide a link to some template code for seg trees?

@aniketpriyadarshi2801 2 ай бұрын

Amazing video man!

@TheProximator 2 жыл бұрын

Nice video, do you think the segment trees are a good use case for salon appointment booking system? in the sense that we can quickly find calculate available timeslots?

@light_up1029 3 жыл бұрын

Hello i want to know how can we add arithmetic progression , within a range using segment tree ?

@xiquandong1183 3 жыл бұрын

Can you add the link to sneetches problem ? It looks like a standard problem.

@francibon93 3 жыл бұрын

Thanks! This is gold :)

@prajwalchoudhary4824 3 жыл бұрын

the best as always

@kevintyrrell7409 2 жыл бұрын

In the Range Queries section, you describe having the following numbers: { 3, 4, 7, 6, 2, 2, 4, 3 }. But what we all have is an array segments, (e.g. { (2,3), (2, 10), (1, 5) }), so that entire segment doesn't really feel applicable. Am I missing something? How is the tree constructed from a list of segments?

@ChandraShekhar-by3cd 3 жыл бұрын

Thanks a lot for making this topic easy to understand. I have watched numerous video but this is the best Content ever...Request you to keep posting important algorithms video in the upcoming sessions. Thank you!

@deepbiswas6943 2 жыл бұрын

Can u plz show how to do lazy propagation on segment tree iteratively?

@pankajkataria8956 3 жыл бұрын

Great Video, Just a small suggestion The way you calculated mid element is faulty on big inputs it will overflow.

@PrinceGupta-jo8lo 3 жыл бұрын

will it tho? arrays are usually at max 1e5 or 1e6 long, I don't think that can overflow

@Shikharchaudhary007 3 жыл бұрын

binary search padhkr aaya hai, nice.

@denebgarza 2 жыл бұрын

Lol first time I hear someone refer to child nodes as "kids"

@vishalreddy52 3 жыл бұрын

How to implement this type of implementation in c++? Could you provide any link for c++ implementation

@vishalreddy52 3 жыл бұрын

never mind, I did it.It's pretty much the same. If anyone needs it ask me.

@sauravuppoor2409 3 жыл бұрын

Is this SecondThread version of Algorithms Live?

@SecondThread 3 жыл бұрын

Indeed :)

@jpfr012 3 жыл бұрын

To be honest, I prefer this solution using tree nodes, instead the array solution shown by Codeforces EDU. It's just my opinion.

@spiderduckpig 3 жыл бұрын

I think class-based solution are always better conceptually, it's just that they are slower

@amneetsingh3837 3 жыл бұрын

Brother, I am solving Division D problems specially...but i think segment trees comes in E problems, what you think i should practise segment trees problems or not?

@debadiptobiswas5611 3 жыл бұрын

alorithms dead, funny name

@shyamalvaderia269 3 жыл бұрын

is it just me or there is a lag between audio and face cam?

@vtvtify 3 жыл бұрын

Wait r u the owner of the channel Algorithms Live?

@SecondThread 3 жыл бұрын

Nope, that would be Matt Fontaine. If I owned it these videos would be on that channel instead lol

@1732ashish 2 жыл бұрын

@@SecondThread hey , can you tell me why we don't update the array as well when you do point update ?

@atvonguyentien5726 Жыл бұрын

@@1732ashish the array is just to build the tree, after that all values are present in the tree, so you don't need to update the array

@1732ashish Жыл бұрын

Yeah I think I understand.. what I was thinking was if there were point updates and then if we update the array as well.. we can get constant time point queries.. but then we go to range updates, where that will be just not possible .. also if there was only point update and point query .. we can do it on array itself :D thanks for helping out, @@atvonguyentien5726

@watermalone4960 3 жыл бұрын

samresh trooper is in my bathroom!

@sanchitkumawat3803 3 жыл бұрын

Can u make your next videos using C++ pls ?

@hell-o8470 2 жыл бұрын

#include using namespace std; template class segTree { int leftmost, rightmost; segTree *lchild, *rchild; T sum; public: segTree(int leftmost, int rightmost, vector &arr){ this->leftmost = leftmost; this->rightmost = rightmost; if(leftmost == rightmost){ sum = arr[leftmost]; } else { int mid = leftmost + (rightmost - leftmost) / 2; lchild = new segTree(leftmost,mid, arr); rchild = new segTree(mid + 1, rightmost, arr); recalc(); } } void recalc(){ if(leftmost == rightmost) return ; else sum = lchild->sum + rchild->sum; } void pointUpdate(int index, T newVal){ if(index < leftmost or rightmost < index) return; if(leftmost == rightmost) sum = newVal; else { if(index rightmost) lchild->pointUpdate(index, newVal); else rchild->pointUpdate(index, newVal); } recalc(); } T rangeSum(int l, int r){ if(l > rightmost or r < leftmost) return 0; if(l = rightmost) return sum; else return lchild->rangeSum(l,r) + rchild->rangeSum(l,r); } }; int main(){ vectorarr; int N = 1e5; int Mval = 1e5; for(int i = 0; i < N; ++ i) arr.push_back(rand()%10000); segTree saga(0, arr.size() - 1, arr); int Q = 1e4; for(int i = 0; i < Q; ++ i){ if(i&1){ int l = rand()%N; int r = l + rand()%(N - l); int sum = 0; for(int i = l ; i