Because sqrt decomposition can solve a wider range of problems. Have a look at Shil and Magic Arrays from HackerEarth. The low constant factor of operations and easy coding are also reasons it could be used over segment trees when feasible.
As a non computer science student, i didnt understand the concepts completely. But I got to know how different algorithms are used and hot it makes a program more efficient. Thanks.
oh my god ,, shikhar sir , i just wana tell you that now you have leaved the college ,, you have become a hero in college. Super talented seniour. Hats off. Practicing to be somewhat you are !!
The code for query function should include the condition when both L and R are in the same block , it fails otherwise , please do look into it. **Lines to add inside the Query function int sum = 0; if(start_block == end_block) { for(int i= L; i
No worries. Just thought of pointing it out. BTW your videos are really great. I am learning a lot of new things through them. Thank you for making them and keep up the good work.!
i have question in query operation, isn't the formula of start block is incorrect as when you have parameter (left,right) will be (1,0) then start block will be zero and their will be problem in first loop
Nice work, Thanks for the explanation, but doesn't work if the range is in the same block, Ex: { 1, 2, 6, 7, 9, 3, 1, 9 } Range 0 - 1 gives 12 instead of 3 Range 3 - 5 gives 38 instead of 19 Range 8 -8 gives 10 instead 9
@@gkcs I ran the code available in your github page, github.com/gkcs/Competitive-Programming/blob/master/src/main/java/main/java/videos/SqrtDecomposition.java And a correction in the last test case its Range 7-7 gives 19 instead of 9
True that subsequent queries will take O(✓n) but whay about first query to find the sum of all the blocks. It will take O(n), so will it ever go below O(n)
I found the issue ,if you are in the same block then you don't need to calculate the previous blocks ,only want to calculate within same block , so i have done like this . if(startBlockIndex==endIBlockIndex) { for (int i = startIndex; i
What are the applications of this? Range query sum has better solution like Fenwick and suffix tree? BTW, the sqrt decomposition is made very simple here.
@@depression_plusplus6120 I am saying that every question that can be solved with segment trees can also be solved using sqrt decomposition. But sqrt decomposition offer slower queries than segment trees.
@@gkcs so segment tree and sqrt decomposition can be used interchangeably? I mean, if a question can be solved using segtree, it can be solved using sqrt decomposition and vice-versa?
They are techniques to solve different problems, with trade-offs on performance and solvability. Here is a good comparison of the two: www.quora.com/What-is-the-difference-between-Sqrt-decomposition-and-Segment-tree
We find the ranges at which the update falls. Usually this is like adding X to all elements in range. We then take the blocks which completely fall in range, and add BLOCK_SIZE*X to their result. For the blocks partially falling in range (At most 2 such blocks), we traverse them and add X to each index in range. Number of blocks completely falling in range are at most sqrt(N), and the 2 blocks are of size sqrt(N). So overall complexity of update is O(sqrt(N)).
can you plz explain this question..www.hackerrank.com/contests/w30/challenges/range-modular-queries this is similar to what u have explained in this video
Why to use sqrt decomposition when we have segment trees....which r better in complexity and does the same 2 operations??
Because sqrt decomposition can solve a wider range of problems. Have a look at Shil and Magic Arrays from HackerEarth.
The low constant factor of operations and easy coding are also reasons it could be used over segment trees when feasible.
As a non computer science student, i didnt understand the concepts completely. But I got to know how different algorithms are used and hot it makes a program more efficient. Thanks.
top tier explaination 🤩
sir , this is the first video i have seen of your's..the explanation was really nice and great...U r really a great person
oh my god ,, shikhar sir , i just wana tell you that now you have leaved the college ,, you have become a hero in college. Super talented seniour. Hats off. Practicing to be somewhat you are !!
1st Face Reveal Video ❤😂
btw Congratulations ❤️❤️
in the query function the first for loop should go from left to ((start_block+1)*Block_Size)-1 nice work
Thanks!
The code for query function should include the condition when both L and R are in the same block , it fails otherwise , please do look into it.
**Lines to add inside the Query function
int sum = 0;
if(start_block == end_block)
{
for(int i= L; i
Very nice explanation,now its look easy,keep posting such videos
Thanks!
Amazing work,but I have I doubt here is dart decomposition better or Fenwick trees better for range query?🤨
Nice work. Cheers !!!
Also If you could list some practice problems based on this technique, that would be nice too.
Thanks Kshitij! You could have a look at the codechef list of algorithms. They mention example problems for each technique.
Great explanation. Thanks!
superb video (Y) really appreciate it!! want more from you
Thanks Neel!
Thank you for the videos. Looking forward for more.
Thanks Vivek!
Thankyou. Great Explanation. Loved it
Square root of 10^9 is 10^4.5 and not 10^3.!! as mentioned by you at 7:10 .
Thanks Harsh! I chose the 10^9 with the purpose of getting an easy root. Cube rooted it :-p
No worries. Just thought of pointing it out.
BTW your videos are really great. I am learning a lot of new things through them. Thank you for making them and keep up the good work.!
It will give the wrong answer if both end_block and start_block are the same because it will add value from both sides. we can use if condition here.
You are awesome dude!
i have question in query operation, isn't the formula of start block is incorrect as when you have parameter (left,right) will be (1,0) then start block will be zero and their will be problem in first loop
Gaurav bhaiya..what was the mathematical analysis at the left side of the board when u were explaining??
Check out the Mo's algorithm video 😊
Can someone point out the difference between segment trees and sort decomposition? and when to use which one.
Nice work, Thanks for the explanation, but doesn't work if the range is in the same block,
Ex: { 1, 2, 6, 7, 9, 3, 1, 9 }
Range 0 - 1 gives 12 instead of 3
Range 3 - 5 gives 38 instead of 19
Range 8 -8 gives 10 instead 9
No it doesn't. You should check out the code on my GitHub page.
@@gkcs
I ran the code available in your github page,
github.com/gkcs/Competitive-Programming/blob/master/src/main/java/main/java/videos/SqrtDecomposition.java
And a correction in the last test case its Range 7-7 gives 19 instead of 9
Awesome job !!
learnt a lot from you :D :D
Thanks Baidhar!
didn't cover the case start_block == end_block
True that subsequent queries will take O(✓n) but whay about first query to find the sum of all the blocks. It will take O(n), so will it ever go below O(n)
Nope. To get the sum of numbers the first time you need to read all the values. Which is at least O(n).
Code Fails : When you query same block like for query (1,2) or query(6,8) .
I found the issue ,if you are in the same block then you don't need to calculate the previous blocks ,only want to calculate within same block , so i have done like this .
if(startBlockIndex==endIBlockIndex) {
for (int i = startIndex; i
Excellent :)
GREAT Work
What are the applications of this? Range query sum has better solution like Fenwick and suffix tree? BTW, the sqrt decomposition is made very simple here.
Temp Jeffry Hey temp, I have answered this in the comment at the top.
is there a situation where sqrt decomposition fails but segment tree not?
In terms of speed, yes. In terms of capability to solve the question, no.
@@gkcs so you're saying, every problem that can be solved using sqrt decomposition can also be solved using seg trees
@@depression_plusplus6120 I am saying that every question that can be solved with segment trees can also be solved using sqrt decomposition.
But sqrt decomposition offer slower queries than segment trees.
@@gkcs so segment tree and sqrt decomposition can be used interchangeably? I mean, if a question can be solved using segtree, it can be solved using sqrt decomposition and vice-versa?
what is better segment tree or Square Root Decomposition
They are techniques to solve different problems, with trade-offs on performance and solvability.
Here is a good comparison of the two: www.quora.com/What-is-the-difference-between-Sqrt-decomposition-and-Segment-tree
camera itna hil kyu raha hai?
Thank you :)
also make a video on sparse tree method
Where do we use that?
I mean sparse table not sparse tree, my mistake.
Sparse table can do look up in O(1) .
if we have query for range updates then how will we proceed?
We find the ranges at which the update falls. Usually this is like adding X to all elements in range. We then take the blocks which completely fall in range, and add BLOCK_SIZE*X to their result.
For the blocks partially falling in range (At most 2 such blocks), we traverse them and add X to each index in range.
Number of blocks completely falling in range are at most sqrt(N), and the 2 blocks are of size sqrt(N). So overall complexity of update is O(sqrt(N)).
Nice Vedioes :)
Thanks Sandeep!
5:08
23+46 = 69 😏
can you plz explain this question..www.hackerrank.com/contests/w30/challenges/range-modular-queries
this is similar to what u have explained in this video
Hi Rajat! Will look into this :-)