What a way to start the morning. For once I dont mind early morning RU-vid notifications. I literally watched the whole thing in 1 go before I could even get off the bed. Time to implement after breakfast. Thanks a ton for the amazing content Errichto!
there is a whole different vibe studying from you :) honestly....so grateful for people like you who contribute sm to the community after acing a particular skill... _/\_ orz SIR
Thank you, sir. I watched your binary search lecture, now I am able to solve difficult binary search problems. Today I finished your segment tree lecture. I hope I can solve query problems now.
and like everything feels so concrete after you claim a thing :) with other teachers there is still a 1% of doubt left in mind if they claim something which is not that easily acceptable even if its correct..but when you claim something, my mind refuses any intent of not believing it automatically and can so easily accept and trust you
Ah! Should have seen this video first. Learned Fenwick tree first and then this one. Could have avoided it. Nevertheless, no knowledge is ever wasted :) Thanks for the great explanation!
hi errichto can you show how we can count different prime nums in a query or count of all prime nums in a query. Is persistent datastructure required in such cases
Its complexity is a lot worse - sqrt(n) vs log (n). However , it is very useful in some problems. There are lot of problems where writing a segment tree solution is a lot more complex.
I came here in ordered to see why some implementations does tree.resize(4 * n) but he just did tree.resize(2*n) (which makes sense for me) I don't get why 4*n
The 4*n ones are probably doing both range updates and range queries which requires extra space to store both the sum and the overriding update value, I guess.
I've struggled with problems of unique element query(find number of unique elements in [l, r]). Probably the only type of range query that can't be done with segtree. or can it be done? tried with a vector of sets but its too slow
If the array has no updates it can be simply done using a simple segment tree(just store the pos of next duplicate in the current node of segment tree)
Hi Errichto, Thanks for the content..it's really helpful. At 32:51 at line number 45 , the function is calling with attributes 0, n-1. It should be 0, 2*n-1 right?. As n is 8 in the example . Or am I missing something?..
It should be 0, n-1. The first argument (node) represents the sum of the elements form node_low to node_high (both inclusive) . So, the root node (1) will have the sum of elements form 0 to n-1 i.e the total sum of all the array elements.
