Simplest Explanation of Square Root Decomposition | Developing Intuition
Vložit
- čas přidán 5. 01. 2024
- If this video gets 500 likes or 100 comments, I will record a video talking about different variations and example problems of the technique explained in the video.
If you found this useful, like and comment on the video, that is very encouraging for me to make more such educational videos.
Subscribe for more such content.
Problem to try to test your implementation - cses.fi/problemset/task/1648
Code for the problem explained for the curious ones (I will strongly advise to first try writing yourself, it's not long but a tricky implementation) - github.com/Abhishek-Saini/edu...
I will add more harder problems here later.
Mouse I use - shorturl.at/hloAX
Keyboard I use - shorturl.at/elFHX
Microphone I use - shorturl.at/hpT13
The second query - changing a value should really be constant time by the SQRD. You can get the block from the index of the element you want to change by constant time. Then you just add the difference of the new and old element (being careful ofc) to the already cached sum of that block. So it’s really constant time.
Thanks for explaining this. Would be very helpful if you can discuss problems regarding this concept.
Amazingly explained bro. Keep doing more
Sir more videos please
Nice explanation. Would love to see more videos on this technique application, and maybe some questions solving in the video itself. Also would like to see videos on advanced topics like this from your side
Awesome Content Abhishek Sir! 🔥👌🏻
Good explanation.
Great explaination. Explained the concept really well. It would really be helpfull if you could follow this up with some set of questions that show how to apply this in various cases.
Thank you for the simple explanation😊
Cool explanation ✨✨
Loved the Explanation !!
Explained well
Great video.
amazing content sir
Helpful.Thanks for the video
Very good explanation ❤
Nicely explained.. pls make video on problems which can be solved with these
Yes Please bring a video on problems based on SRD
Great explanation, you delivered as you had promised. I have a doubt tough, while solving problems, can't we use segment trees to perform the task of updates and queries? Segment trees can do them in O(logn), then why square root decomposition for it? Just for better memory optimization or something else?
P.S. do make more videos continuing this topic, along with its implementation and use in problem solving.
Nice👍
good explanation! but i think you should also show some glance of implementation quickly to end .
Sure, will try to do that whenever needed. Generally I am thinking of focussing on making algorithm understand, as once one understand that it's easier to get the code just by reading. Perhaps will try to show implementation for the harder ones.
For this problem you can find the code here on my github github.com/Abhishek-Saini/educational/blob/main/youtube/square_root_decomposition_explanation_problem.cpp
Thank you sir ❤❤
Please explain solutions for contest problems. Thanks alot for your videos.
Problems with all variations really needed🥲
Sir can you refer some resources for web development where should we learn those.
❤❤
nice
Bhaiya ajj leetcode context ka question 3,4 ka ek bana do please 🥺 .
Great idea!!
But this problem can be easily solved using segment trees.
Can you please give a question link where this technique can be handy (I mean which cannot be solved using segment trees or any other known easy algorithms)?
You can try this atcoder.jp/contests/abc335/tasks/abc335_f
Problem picked is intentionally simpler so that folks can develop intuition better. There are many problems where some sort of square root decomposition idea is used.
yep, using Fenwick tree complexity can be q*log(n)
Bro pulled me with his ratting 😅
Haha, Hope the video was helpful though :)
OPOPOP