Recently discovered your channel and was pleasantly surprised at the quality of the content. videos are concise, have great animations and your explanations are great. Hope your channel propspers!
Thank you kindly! It's good to remember binary index trees/segment trees in case off some odd problem that seems to be totally unsolvable by "normal" means (hash tables/trees/arrays).
Thanks for the compliment. To answer your question, I am not sure how lazy propagation would help. But, please do let me know if you come up with a different solution. Seriously, I'd love to know if there is a different way of solving this problem!
@@stablesort I just coded it, so there might be tiny errors here and here, but overall this is the main idea. Feel free to ask if you don't understand any part. int st[4*100000+5],lazy[4*100000+5]; void push(int pos) { if(lazy[pos]==1) { lazy[2*pos+1]=1-lazy[2*pos+1]; lazy[2*pos+2]=1-lazy[2*pos+2]; } lazy[pos]=0; } void build(int arr[],int ss,int se,int pos) { if(ss==se) { st=arr[ss]; return; } int mid=(ss+se)/2; build(arr,ss,mid,2*pos+1); build(arr,mid+1,se,2*pos+2); ` st[pos]=st[2*pos+1]+st[2*pos+2]; } void update(int l,int r,int ss,int se,int pos) { if(l>se||rn; int arr[n]; for(int i=0;i>arr[i]; build(arr,0,n-1,0); int No_of_queries; cin>>No_of_queries; for(int i=0;i>type; if(type==1) { int l,r; cin>>l>>r; update(l,r,0,n-1,0); } else { int ind; cin>>ind; cout
Thanks for your question. Lazy propagation is a topic that I have not yet covered. But several people have asked for it so I am set on making a video on this topic in the near future.
Thanks, that's a great suggestion and the topic would fit perfectly with some of the other content on this channel! By the way, apparently there is an O(n) construction (en.wikipedia.org/wiki/Suffix_array#CITEREFLiLiHuo2016) - I'd need to study it a little to fully understand it. Cheers!
Indeed, a nice trick =) That and remembering to use either a Fenwick Tree or a Segment Tree. That's been my lesson for the future - in an interview situation, if nothing else helps, check if a Fenwich Tree/Segment Tree could come in for a rescue!
Fenwick tree is great, but would bst also work? What do you think of this? 0. initialize a TreeMap 1. toggle(i, j) treeMap.put(i, 1), treeMap.put(j + 1, -1) 2. isO(i), query floor key of treeMap, if null or value of key corresponds to -1, return False, otherwise true if key corresponds to a 1 O(logn) per operation as well space is O(min(2*toggle, n)) as opposed to O(n)
That's an interesting idea. So what happens when you call toggle using the same i and j twice? For example toggle(5, 10) and then again toggle(5, 10). Unless I misunderstood something, the treeMap will not change back to the initial state... Besides, the whole point of this video is to get people to learn about Fenwick Tree =)
@@yuandali9488 Thanks for the compliment! By the way, recently I came across a neat problem where your idea of using a TreeMap and then call floor() ceiling() is very helpful. I think you'll find this one easy to solve with that idea in mind: leetcode.com/problems/contains-duplicate-iii
best new data structure and algorithm channel ive come across. Clear explanations, good animations, calm presentation. Keep it up!
Thanks for the compliment! A new episode is a bit overdue, but it's in the works =)
Recently discovered your channel and was pleasantly surprised at the quality of the content. videos are concise, have great animations and your explanations are great. Hope your channel propspers!
Thanks for a wonderful compliment! By the way, comments like these do help it prosper 👍
great video sir! incredibly topical and cordial!
Thank you kindly! It's good to remember binary index trees/segment trees in case off some odd problem that seems to be totally unsolvable by "normal" means (hash tables/trees/arrays).
as soon as i saw range updates i knew its segment tree!!
Awesome! This is not an easy problem!
Good quality video. Looks like lots of effort went in the editing and dialogue. Nice! Can we use lazy propagation to solve this question though?
Thanks for the compliment. To answer your question, I am not sure how lazy propagation would help. But, please do let me know if you come up with a different solution. Seriously, I'd love to know if there is a different way of solving this problem!
Yes, lazy propogation works perfectly. I've solved this before using lazy propogation in a coding contest
@@abhijeetnarang1791 Wow, cool! Would you please share the code? We are all learning here =)
@@stablesort
I just coded it, so there might be tiny errors here and here, but overall this is the main idea.
Feel free to ask if you don't understand any part.
int st[4*100000+5],lazy[4*100000+5];
void push(int pos)
{
if(lazy[pos]==1)
{
lazy[2*pos+1]=1-lazy[2*pos+1];
lazy[2*pos+2]=1-lazy[2*pos+2];
}
lazy[pos]=0;
}
void build(int arr[],int ss,int se,int pos)
{
if(ss==se)
{
st=arr[ss];
return;
}
int mid=(ss+se)/2;
build(arr,ss,mid,2*pos+1);
build(arr,mid+1,se,2*pos+2);
` st[pos]=st[2*pos+1]+st[2*pos+2];
}
void update(int l,int r,int ss,int se,int pos)
{
if(l>se||rn;
int arr[n];
for(int i=0;i>arr[i];
build(arr,0,n-1,0);
int No_of_queries;
cin>>No_of_queries;
for(int i=0;i>type;
if(type==1)
{
int l,r;
cin>>l>>r;
update(l,r,0,n-1,0);
}
else
{
int ind;
cin>>ind;
cout
@@abhijeetnarang1791 Oh, nice, I think I get it - a seg. tree with lazy propagation does reduce the overall cost of update operations. Thanks!
Your videos about segment trees are really good, thanks. By any chance, do you have one about lazy propagation in segment trees?
Thanks for your question. Lazy propagation is a topic that I have not yet covered. But several people have asked for it so I am set on making a video on this topic in the near future.
Amazing content Andre! could you make a video on suffix arrays .(construction in nlogn and its applications) .
Thanks, that's a great suggestion and the topic would fit perfectly with some of the other content on this channel! By the way, apparently there is an O(n) construction (en.wikipedia.org/wiki/Suffix_array#CITEREFLiLiHuo2016) - I'd need to study it a little to fully understand it. Cheers!
Storing ranges... nice trick
Indeed, a nice trick =) That and remembering to use either a Fenwick Tree or a Segment Tree. That's been my lesson for the future - in an interview situation, if nothing else helps, check if a Fenwich Tree/Segment Tree could come in for a rescue!
My solution involved bitmasks. I think that can bring it down to constant time, but I may be overlooking something
Fenwick tree is great, but would bst also work? What do you think of this?
0. initialize a TreeMap
1. toggle(i, j) treeMap.put(i, 1), treeMap.put(j + 1, -1)
2. isO(i), query floor key of treeMap, if null or value of key corresponds to -1, return False, otherwise true if key corresponds to a 1
O(logn) per operation as well
space is O(min(2*toggle, n)) as opposed to O(n)
That's an interesting idea. So what happens when you call toggle using the same i and j twice? For example toggle(5, 10) and then again toggle(5, 10). Unless I misunderstood something, the treeMap will not change back to the initial state... Besides, the whole point of this video is to get people to learn about Fenwick Tree =)
@@stablesort Ahh good point, forgot that you can keep toggling on and OFF. Great video!
@@yuandali9488 Thanks for the compliment! By the way, recently I came across a neat problem where your idea of using a TreeMap and then call floor() ceiling() is very helpful. I think you'll find this one easy to solve with that idea in mind:
leetcode.com/problems/contains-duplicate-iii
@@stablesort Nice!
the youtube algorithm does not treat videos about elections and math very favorably fyi
Haha, good point =) I'll stick with comp sci going forward!
hey stable sort please make a video on floyd's algorithm hair and tortoise with its proof why it works
Duly noted. Thank you, those are great suggestions!
@@stablesort thank you for taking time to reply and for uploading great videos