Hi Striver ☺ , There are errors in LINE NO : 68 and 69 : in the rangeUpdate() function , it should be : if(low != high){ lazy[2*ind+1] += val ; lazy[2*ind+2] += val ; } This can be verified by taking the following test case : say we have 2 queries , 1st query (update query) : l = 0, r = 2, val = 1 so the array becomes -> 3 4 2 4 2 5 2 3 1 5 2nd query (range sum query) : l = 0, r = 1 correct output should be 3 + 4 = 7 , BUT the code shown will give the sum as 5 I.e (2 + 3) The reason for that error is because if you notice in the function rangeUpdate() , first we check if there is lazy[ind] > 0 , if it is we update the segment[ind] and then carry forward the lazy[ind] to left and right nodes and THEN set the lazy[ind] = 0 . So every time we enter the rangeUpdate() function, we make sure lazy[ind] becomes 0 Now suppose we have met the condition that the interval(low and high) entirely lies within l and r, so we update the segment[ind] as in line no 66 , BUT THEN while we are setting the lazy[left_ind] and lazy[right_ind] we set it to lazy[ind[ , which is ALWAYS 0, hence not updating the lazy[left] and lazy[right] So we make lazy[left_ind] += val and lazy[right_ind] += val ; BTW thank you so much for your crystal clear explanation !!
Hii I guess There is a slight error at 18:37 in rangeUpdate when segment completely lies inside range it shuold be lazy[2*ind+1] += val lazy[2*ind+2] += val
hye striver?? could u plz make some vdos in xor properties?? like:-- 1. all pair xor sum in binary sequence / any sequence 2. all subarray xor sum in any sequence 3.prefix xor/and/or... plzzzzzz,,
Hey ,Ur videos are amazing.. they are helping a lot .. keep posting such videos..is it possible for u to make video on DSU on trees and HL decomposition on trees... that would be a great help... Thanks
Hello bhaiya I wanted to ask that are questions in coding round and interview of same type or different because in every site we get questions as interview questions and no site give questions as coding round questions. Pls reply and clear this doubt
Hello Bhaiya, I'm an SYBCA student but am determined to work at a big product based company. Will DSA and CP along with a few projects be enough?? Please guide.
C++ Working Code #include using namespace std; // TC: O(NlogN); // SC: 2*(4*N) ~ O(N); // Segement Trees : Point Update & Range Update int n; // size of the array... vector arr, segment, lazy; void buildSegementTree(int ind, int left, int right){ // Base Case if(left == right){ segment[ind] = arr[left]; return ; } int mid = (left + right) / 2; buildSegementTree(2*ind+1, left, mid); buildSegementTree(2*ind+2, mid+1, right); segment[ind] = segment[2*ind+1] + segment[2*ind+2]; } void pointUpdate(int ind, int left, int right, int node, int val){ if(left == right){ arr[left] += val; segment[ind] += val; }else{ int mid = (left + right)/2; if(left =l && right right) return 0; // If range is completely inside... if(left >= l && right
Hi Striver ,
There is an error in line no : 30 at 3:08 timestamp of video which should be seg[segInd] += val;
Oops yes.. thanks! Typo :(
and a[low] += val;
@@takeUforward Bhaiya , is there any need to add a condition of low>high since if we go out of range then r
Aren't all same? Low=high=ind?
@@arten8281 No
Thank you for the constant support ! :)
Yo👍
Aap itna keh diye . Chaati chauda ho gaya hamara
are you going to give codeforces div2?
🤟🤟🤟
waiting from yesterday, for your live
Hi Striver ☺ , There are errors in LINE NO : 68 and 69 :
in the rangeUpdate() function , it should be :
if(low != high){
lazy[2*ind+1] += val ;
lazy[2*ind+2] += val ;
}
This can be verified by taking the following test case :
say we have 2 queries ,
1st query (update query) :
l = 0, r = 2, val = 1
so the array becomes -> 3 4 2 4 2 5 2 3 1 5
2nd query (range sum query) :
l = 0, r = 1
correct output should be 3 + 4 = 7 , BUT the code shown will give the sum as 5 I.e (2 + 3)
The reason for that error is because if you notice in the function rangeUpdate() , first we check if there is lazy[ind] > 0 , if it is we update the segment[ind] and then carry forward the lazy[ind] to left and right nodes and THEN set the lazy[ind] = 0 . So every time we enter the rangeUpdate() function, we make sure lazy[ind] becomes 0
Now suppose we have met the condition that the interval(low and high) entirely lies within l and r, so we update the segment[ind] as in line no 66 , BUT THEN while we are setting the lazy[left_ind] and lazy[right_ind] we set it to lazy[ind[ , which is ALWAYS 0, hence not updating the lazy[left] and lazy[right]
So we make lazy[left_ind] += val and lazy[right_ind] += val ;
BTW thank you so much for your crystal clear explanation !!
Instead of +=val shouldn't it be += (range of left node) * val?
Hii I guess There is a slight error at 18:37 in rangeUpdate when segment completely lies inside range it shuold be lazy[2*ind+1] += val lazy[2*ind+2] += val
yes you are right but he hasn't read your comment yet ?
yeah, correct.
he should update this, i think he hasn't read this comment yet!
He consider 0-based indexing of segTree and LazyTree and thats why he done this :)
@@manaskumarpanda3343 No read the comment carefully at the second step it should add val not the previous lazy value which already added above.
This channel is my Constant motivation source!!
in the querysum upadte, the val parameter passed in the function, was of no use
on line no. 68 & 69 it should be +=val not +=lazy[indx] in range update
Correct
hye striver?? could u plz make some vdos in xor properties?? like:--
1. all pair xor sum in binary sequence / any sequence
2. all subarray xor sum in any sequence
3.prefix xor/and/or...
plzzzzzz,,
Thank you so much Striver, Its the best explanation on the internet!
The video started flashing green colour around 10:55 and it made me unwell.
Hey ,Ur videos are amazing.. they are helping a lot .. keep posting such videos..is it possible for u to make video on DSU on trees and HL decomposition on trees... that would be a great help... Thanks
Slight error in updatepoint code
if(low==high)
Update arr[node]+=val and seg[ind]+=val
After working whole day your video give me a hope for a future where I will be happy. Thanks a lot
finally samaj aagya ....
not need to watch another video
thnx for concise and great content
:)))
Bhaiya there is a slight mistake
In point update code in the first if condition it should be seg[ind]+=val, not seg[low]+=val;
for storing lazy update info ,we require extra space O(n),right?
Sir, I am from Bangladesh, your video is very helpful to me.....
In querySumLazy function I believe we don't need the int val parameter
yes i was thinking the same it should by only lazysum(ind, low, high, L, R)
if we have to update constant value from l to r then??
Where does the index 3 lies on the left or on the right 😂
That rhyme
Amazing Explanation striver sir! Thank you so much!
Loved your Accent bhai
please make a video on - "how to optimize the JAVA code for Competitive Programming"
didn't understood when 21 minutes were over. thank you so much
Hello bhaiya I wanted to ask that are questions in coding round and interview of same type or different because in every site we get questions as interview questions and no site give questions as coding round questions. Pls reply and clear this doubt
Thanks for your explaination . it helps me a lot
If different nodes have different update values, like updating the value { 2,4,1,6,3,5} for the range [5 - 10], is it possible to use lazy update?
Very well explained. Understood
Can u plz explain how to perform lazy propagation on segment tree ITERATIVELY
Hello Bhaiya, I'm an SYBCA student but am determined to work at a big product based company. Will DSA and CP along with a few projects be enough?? Please guide.
bro did you get into a product based company?
Hi bro, please try to upload the atcoder dp series'.
Hey bro please make a video on vscode setup... for competitive programming...
Bhaiya Can you make video on timing of HackerRank Contests Through which Product Based Comp
Hire
Please tell the function call statements
Bhai aapki video private kyon ho gayi.. QNA wali ek ghante pahele aayi thi??
Understood
There is no code link?
It is similar to the one at gfg !
0:00 - 1:15
6:29 -
Sir when will we get the update of cp 5 gfg live classes.
Cp5 has started, thanks!
Code link bro
Please don't drag the words
bro QnA video public kardo, i joined in late
How to use segmented tree in 10^9 range
Coordinate compression
Plz give some link about coordination compression for segment sieve
@@Fictional_universe ua-cam.com/video/s9oXy-fZUzg/v-deo.html
Thank uu
@@Fictional_universe you can use implicit segment tree instead of it
Awesome Video😀😀
Bhaiya tcs digital par koi banao
Yes...I'm preparing for tcs codevita
@@anirudhsinhrajput9238 i am also preparing for tcs codevita
@@gamingwitheng1459 when is the date of tcs codevita??
vo sab to thik hai lekin ye bol kese raha hai so funny lol
BINGO
bhai accent mei mt bol
Abe yaar ye kese bolta hai, chu
C++ Working Code
#include
using namespace std;
// TC: O(NlogN);
// SC: 2*(4*N) ~ O(N);
// Segement Trees : Point Update & Range Update
int n; // size of the array...
vector arr, segment, lazy;
void buildSegementTree(int ind, int left, int right){
// Base Case
if(left == right){
segment[ind] = arr[left];
return ;
}
int mid = (left + right) / 2;
buildSegementTree(2*ind+1, left, mid);
buildSegementTree(2*ind+2, mid+1, right);
segment[ind] = segment[2*ind+1] + segment[2*ind+2];
}
void pointUpdate(int ind, int left, int right, int node, int val){
if(left == right){
arr[left] += val;
segment[ind] += val;
}else{
int mid = (left + right)/2;
if(left =l && right right) return 0;
// If range is completely inside...
if(left >= l && right
can you pls explain why the arr[left]+=x part in pointupdate..is it necessary ? i mean we are not using the array anywhere except in the building part