Here is something you might want to ask yourself after watching this video: What if the initial array given to us is not filled with 0s, would this technique still work? If not, how will you modify it so that it still works.
Just take an array filled with all 0 initially, perform the queries, and you will get the prefix array. After that, add ith value of prefix array to the ith index of the initial array
Hi priyansh, few days ago you posted questions on Time & space complexity on twitter & I was not able to find the right answer. Probably a detailed video on time & space complexity would really help everyone. Also, how to analyse which algorithm would be suitable based on the inputs & constraints. Some standard TC of the loops, how to go about finding the TC & SC etc.
I don't know that this trick is called difference array trick I got to know about this when I solved a CF 1500 rated problem btw it's a beautiful technique and Bhaiya u explained it very well👍
if the initial array given to us is not filled with 0s we will have a problem because when we create the prefix array we will unnecessarily add or subtract numbers , to avoid this we should already take the difference of the initial adjacent elements . informative video
Answer of the pinned comment. If the initial array is not full of zeroes, there are two things we can do :- 1. Just create a new array with full of zeroes and do whatever updates we have to do, then atlast when you create its prefix sum array, add the original array values. 2. But we had to create a new array which is not cool 🙁 So the other way is to convert that array into the difference array by replacing all values from index 1 to n - 1 by a[i] - a[i-1] and enjoy 🍻.
this trick gave me a nightmare for a few hours. i couldn't understand how someone used this to solve a question in a linear time complexity which is did in O(n * m)
Here is something you might want to ask yourself after watching this video: What if the initial array given to us is not filled with 0s, would this technique still work? If not, how will you modify it so that it still works.
@@nakshatrasharma7183why not add it because it was initially given to us??
We need to modify the array like this:
for(int i=n-1;i>0;i--){
arr[i]=arr[i]-arr[i-1];
}
Just take an array filled with all 0 initially, perform the queries, and you will get the prefix array. After that, add ith value of prefix array to the ith index of the initial array
@@Mkhuss sweet
the bullet example was great i immediately got why we are doing the process after that example
Such a mind-blowing technique. Thanks for such a nice explanation ❤
Very Helpful, Small video but very efficient..
Please keep bringing similar small videos!!!!
Yes, a lot of such content is coming up. Stay tuned.
You are growing in your teaching experience
Very informative priyansh, keep posting such videos
Hi priyansh, few days ago you posted questions on Time & space complexity on twitter & I was not able to find the right answer. Probably a detailed video on time & space complexity would really help everyone. Also, how to analyse which algorithm would be suitable based on the inputs & constraints. Some standard TC of the loops, how to go about finding the TC & SC etc.
Big fan of you and your work towards indian cp community
Hats off to you man✨️ You explained this technique in a very simple manner✨️
nice concept stored in the tool box.
Good work! Keep the work going. It helps me a lot since I didn't get a place in the tle batch, I study from your youtube videos
Bdhiya priyansh bhai, good explanation
This is a wonderful technique 😍
Want more contents like this❤
Surely, we have planned a series of 5-7 such videos that would be coming up very very soon. Stay tuned.
@@TLE_Eliminators when will the videos be uploaded?
Thx bro !! for this , please post more content like this
I don't know that this trick is called difference array trick I got to know about this when I solved a CF 1500 rated problem btw it's a beautiful technique and Bhaiya u explained it very well👍
Super bro very useful for us ,we are exict to see these types of videos more ,😍
if the initial array given to us is not filled with 0s we will have a problem because when we create the prefix array we will unnecessarily add or subtract numbers , to avoid this we should already take the difference of the initial adjacent elements . informative video
Very good explanation
useful we need more like this
THANK YOU !!!
loved it! keep bringing more and thanks
Really very helpful video ❤❤❤😊
Please make these type of amazing content of CP. This will help to many students which are beginner in CP.
Surely. A lot more is coming. Stay tuned.
1 0 1 array and do -1 in l = 0 to r = 2; as per this r+1 does not exist
Great video thanks 👍 got at the right time..
Good job 🎉🎉
its parital prefix sum technique
Answer of the pinned comment.
If the initial array is not full of zeroes, there are two things we can do :-
1. Just create a new array with full of zeroes and do whatever updates we have to do, then atlast when you create its prefix sum array, add the original array values.
2. But we had to create a new array which is not cool 🙁
So the other way is to convert that array into the difference array by replacing all values from index 1 to n - 1 by a[i] - a[i-1] and enjoy 🍻.
Perfect. Both will work.
can you make more clear second approach please ?
i guess you should do a[i] = a[i] - a[i-1] starting from i=n-1 to i=1 doing i-- ??
@@amarsharma8582 at the end we are just going to replace a[i] by a[i-1] + a[i], so to reverse it, you can replace it by a[i] by a[i] - a[i - 1]
@@itzzRaghav check this code: is it correct ?
#include
#include
using namespace std;
int main()
{
int n;
cout > n;
vector elements(n, 0);
vector diff(n, 0);
cout > elements[i];
}
int updateValue;
int l, r;
cout > updateValue;
cout > l >> r;
diff[l] += updateValue;
if (r + 1 < n)
diff[r + 1] -= updateValue;
for (int i = 1; i < n; i++)
{
diff[i] += diff[i - 1];
elements[i] += diff[i];
}
cout
interesting trick .............
In 1st problem what exactly we have to do in k queries..
I am not getting the statement .
Same, I was excited to know the technique but didn't get the statement of the 1st question which is in description 😢
successfully wasted my 10 minutes. I think everyone knows this technique except beginners
Who told you to watch it ??
Lol, you watched it despite knowing the technique? The joke is on you then.
why you are wasting your time to comment as well no one cares and no one forcing you to watch.
Amazing content, we need more of this🔥🫡
this trick gave me a nightmare for a few hours. i couldn't understand how someone used this to solve a question in a linear time complexity which is did in O(n * m)