To get the parent of n, you can also find it by calculating n & (n-1) which is a little simpler than the 3 step process described in the video (2s complement, AND with original, then subtract from original)
@Tushar Hey Tushar, it will be good if it is mentioned why 5 is expressed as 2^2 + 2^0 and not 2^0 + 2^2. The idea here is to go to the parent and then next x number of elements. I got confused when i saw the video. Then later i figured it out that it is expressed as parent index + some power of 2.
In this case, 2^2 will be the dad node and 2^0 is the rightmost bit 1. For example: 11 = 1011= 2^3 + 2^1 + 2^0 which is 2^3 + 2^1 will be its dad node(1010 = 10) and 2^0 is the value of rightmost bit 1 of the node (0001).
Its nice that you actually focus on analysis and also point out the petty things that form the basis of the code eg. the next hop and the examples. This is in contrast to other algo preachers who just mutter out the process without specifications as if it were imminent. Thanks, and please don't stop making videos.
After watching a couple of BIT explanations from some good channels, I lost the hope of COMPLETELY understanding it. But you made it so easy and clear in 20min!! Legend you are! ❤
Thank you so much for this and thank you for breaking everything down to a level that makes it easy to understand a binary indexed tree. Awesome explanation!
we can find parent also by first subtracting number by 1 and then do bitwise and of this number with original number eg :- 10 is 1010 subtract 1 1001 now do bitwise and it with 10 1010 & 1001 = 1000(8), which is the result.
@Tushar you should also explain how to get range sum for lower bound > 0. Eg. RangeSum(2, 6) Here is the snippets for finding range sum: int findSum(int low, int high) { if (low > high) throw new Error("Invalid range"); int index = high+1; int upperBoundSum = 0; while (index > 0) { upperBoundSum += tree[index]; index = getParent(index); } int lowerBoundSum = 0; if (low != high) { index = low; while (index > 0) { lowerBoundSum += tree[index]; index = getParent(index); } } return upperBoundSum - lowerBoundSum; }
FT creation takes linear time but not linearithmic time. This is the way to do in linear time : -- fill original array values at indices [0, n-1] into FT array indices [1, n]. FT is created of size n+1, and FT[0] is n/a -- Propagate values up in a cascading approach. 1 is 0001. 1+lsb(1)=1+1=2 (lsb: least significant bit, obtained as x & - x). So, 2 is responsible for 1. In other words, 2 stores the prefix sum of 2 array indices -- itself and 1 below. How? 2 is 0010. lsb(2)=2. lsb(x) represents the prefix sum of how many array indices it is responsible for. So, add FT[1] to FT[2]. Next, handle 2. 2+lsb(2)=2+2=4. Add FT[2] to FT[4]. 3+lsb(3)=3+1=4. Add FT[3] to FT[4]. 4+lsb(4)=4+4=8. Add FT[4] to FT[8]. -- Thus we don't propagate a number all over the FT in O(log2(n)) time. Instead we propagate only to the immediate higher number who is responsible for current number (example: 4 is 8's responsibility. 5 is 6's responsibility, etc) -- Thus we construct the FT from i/p array in O(n) linear time
Because of your videos, my Data Structures concepts are getting clear and strong...... Thank you very much... please also post videos about how to apply data structure logic for any given problem. I don't know about others but sometimes I fail to understand which data structure I should use to solve a problem.
You amazing man... When I saw some hackerearth notes..i just ignored it coz it was quite long and reading becomes useless..and here i saw ur video and i dun knw how just time passed and finally understood it...thnx and will go thru every video of urs coz these are the hottest topics in competitive coding world
gotcha bro , u are the best one on the youtube , there are tons of creators who tried to explain same topic , i couldnt understand , u are the best. thank u so much
Also for range other than 0,y let say we need to get range from x,y then just we gotta do is (0,y)-(0,x-1) :p I hope many may thought abt it so likhdiya ;p
I'm certain you can create the tree in O(n) if you use a faster algorithm. I think I found a way to calculate the values one by one where they take O(1) time amortized.
what I figured out from the above video is. if you want to find the sum of the ith element, then go to its parent and from there take the smallest 2^power element present in I and take the sum of that much element. For example ,{ () represent power} for 1 = 2(0) parent is 0 take 2(0) elements from there that is (0,0) for 2 = 2(1) parent is 0 take 2(1) elements from there that is (0,1) for 3 = 2(1)+2(0) parent is 2 take 2(0) elements from there that is (2,2) for 4 = 2(2) parent is 0 take 2(2) elements from there that is (0,3) for 5 = 2(2)+2(0) parent is 4 take 2(0) elements from there that is (4,4) for 6 = 2(2)+2(1) parent is 4 take 2(1) elements from there that is (4,5)
Get next element explanation is intuitive. If current element is represented as parent index + next x elements (as power of 2), we need to increase the range of next x element by power of 2. Example: 6 = 2^2+2^1 then next element=2^2+2^2=8
It is the best explanation i think....every information is so clear and simply explained.....Do you have any tutorial regarding how to perform range updates in fenwick tree
What I figured out is that for all the powers of 2 (2,4,8), he started from 0. Else he started in the descending order of powers of two. Just a rough guess.
Great video again. What are your thoughts on using Binary Indexed trees vs segment trees? I can use BIT for solving all problems which segment trees can? I find segment trees hard to implement in interviews..
I dont understand the part of index value evaluation, based on what? I mean the evaluation of each index in the fenwick tree for 1, 2, 3, .... and so on you started with 0 with some and 2 with others. also I can see that as an example the index 6 may have more than representation , the one you mentioned 3 = 2ofpower1+2ofpower0 not started by 0 as the 1 and 2, please can you make it clear more to me?
I got it. It depends on the binary bits count representation of the number in other words the number 4 represents by 100 in binary which has one active bit at position 3 with power 2 which equal 2 of power 2 then its value will start by 0 followed by the 4[2 of power 2] and for number 6 it represents by 110 which has more than one active bit at positions 2 and 3 or power of 1 and 2 respectively which equals to [2 of power 2] + [2 of power 1] and need to start from 0 for that number.
heyy!! i must say that you are doing a great job!! i just wanted to confirm that if the number is a power of two then we take the summation from starting(ie index 0) to the number and in rest of the cases we are dividing the number in the decreasing power of 2s ?
/** * To get parent * 1) 2's complement to get minus of index * 2) AND this with index * 3) Subtract that from index */ private int getParent(int index){ return index - (index & -index); } /** * To get next * 1) 2's complement of get minus of index * 2) AND this with index * 3) Add it to index */ private int getNext(int index){ return index + (index & -index); } Can you explain reason behind this? I can see it works but dont get why? BTW you are awesome.
To get the parent of n, you can also find it by calculating n & (n-1) which is a little simpler than the 3 step process described in the video (2s complement, AND with original, then subtract from original)
it is simpler but at the end of the day they're both 1 liners
@@Marzex1xbeing a one liner literally doesn't mean anything, use the one that's widely better understood
@@SergioS-ji1hv doesn't really matter at the end of the day it comes down to personal preference
@Tushar Hey Tushar, it will be good if it is mentioned why 5 is expressed as 2^2 + 2^0 and not 2^0 + 2^2. The idea here is to go to the parent and then next x number of elements. I got confused when i saw the video. Then later i figured it out that it is expressed as parent index + some power of 2.
Precisely,I was wondering about the exact same thing until i came across your comment.Thanks a ton! :)
initially confused ....how updating a index i to index j some time 2^x + 0 and some time 0+2^x.....But you made it clear thanx
You need to go up.
I was also surprised unless I read your comment
In this case, 2^2 will be the dad node and 2^0 is the rightmost bit 1. For example: 11 = 1011= 2^3 + 2^1 + 2^0 which is 2^3 + 2^1 will be its dad node(1010 = 10) and 2^0 is the value of rightmost bit 1 of the node (0001).
Nice and short videos. Another simple way to obtain the parent of index x is x & (x -1)
Yes, I was thinking the same...! More info: www.techiedelight.com/brian-kernighans-algorithm-count-set-bits-integer/
Is the any cool trick to find the next number in fenwick tree ??
Well said. A more detailed explanation could be found in another tutorial: ruclips.net/video/uSFzHCZ4E-8/видео.html
@@PrateekRathore the next of i will be i+ (i&(-i) ).
@@ishanraj5961 that is what tushar said
One of the best explanations I've ever come across for Fenwick Tree!
Its nice that you actually focus on analysis and also point out the petty things that form the basis of the code eg. the next hop and the examples.
This is in contrast to other algo preachers who just mutter out the process without specifications as if it were imminent. Thanks, and please don't stop making videos.
Aman Garg agreed!
After watching a couple of BIT explanations from some good channels, I lost the hope of COMPLETELY understanding it. But you made it so easy and clear in 20min!! Legend you are! ❤
finally i found a real expert on Fenwick Tree, I actually implemented it in Java using this lecture. Thank you very much!
Thank you so much for this and thank you for breaking everything down to a level that makes it easy to understand a binary indexed tree. Awesome explanation!
This video is just too good! Thank you so much!!!!!!
Very good explanation on the fenwick tree concept and how to create and update the tree.
Perfect brother, if one wants to learns can learn from this lecture or cannot learn at all..... All concept perfectly covered in 20 min.
One of the best explanations on Fenwick Tree on the internet. Well worth the 22 mins I spent on watching.
For filling up the tree, we can create a cummulative sum array and using that we can fill the nodes...it will take O(n) time to fill the entire tree.
Wow, This is a really useful content! Thank you for the value you create!
we can find parent also by first subtracting number by 1 and then do bitwise and of this number with original number
eg :- 10 is 1010 subtract 1
1001 now do bitwise and it with 10
1010 & 1001 = 1000(8), which is the result.
Only some people have the talent to explain such complex concepts in such an easy manner. And Tushar is one of them.
you can get parent in a bit easier way:
Parent = n&(n-1)
n refers to what ?
@Tushar you should also explain how to get range sum for lower bound > 0. Eg. RangeSum(2, 6)
Here is the snippets for finding range sum:
int findSum(int low, int high) {
if (low > high) throw new Error("Invalid range");
int index = high+1;
int upperBoundSum = 0;
while (index > 0) {
upperBoundSum += tree[index];
index = getParent(index);
}
int lowerBoundSum = 0;
if (low != high) {
index = low;
while (index > 0) {
lowerBoundSum += tree[index];
index = getParent(index);
}
}
return upperBoundSum - lowerBoundSum;
}
Hi, thanks very much for the instruction. I am now fully understand the algorithm and can implement myself during interview.
That's your second video that I watched and it was very helpful. Just came here to say thank you.
Never seen him smiling, I guess he is Robot
I have heard a lot that this topic is very tough but you really made it easy for me . Thanks a lot.
FT creation takes linear time but not linearithmic time.
This is the way to do in linear time :
-- fill original array values at indices [0, n-1] into FT array indices [1, n]. FT is created of size n+1, and FT[0] is n/a
-- Propagate values up in a cascading approach. 1 is 0001. 1+lsb(1)=1+1=2 (lsb: least significant bit, obtained as x & - x). So, 2 is responsible for 1. In other words, 2 stores the prefix sum of 2 array indices -- itself and 1 below. How? 2 is 0010. lsb(2)=2. lsb(x) represents the prefix sum of how many array indices it is responsible for. So, add FT[1] to FT[2]. Next, handle 2. 2+lsb(2)=2+2=4. Add FT[2] to FT[4]. 3+lsb(3)=3+1=4. Add FT[3] to FT[4]. 4+lsb(4)=4+4=8. Add FT[4] to FT[8].
-- Thus we don't propagate a number all over the FT in O(log2(n)) time. Instead we propagate only to the immediate higher number who is responsible for current number (example: 4 is 8's responsibility. 5 is 6's responsibility, etc)
-- Thus we construct the FT from i/p array in O(n) linear time
Excellent.... Excellent....Excellent ...Thank you very much
Good expln.
those who are still confused, please read some article and then again refer the vdo
Thanks, @Tushar. You don't know how great&helpful your videos&tutorials are to me!
Because of your videos, my Data Structures concepts are getting clear and strong...... Thank you very much... please also post videos about how to apply data structure logic for any given problem. I don't know about others but sometimes I fail to understand which data structure I should use to solve a problem.
You amazing man... When I saw some hackerearth notes..i just ignored it coz it was quite long and reading becomes useless..and here i saw ur video and i dun knw how just time passed and finally understood it...thnx and will go thru every video of urs coz these are the hottest topics in competitive coding world
Thank you so much for an amazing explanation of a complex data structure. :)
You are awesome as usual. I was struggling with Fenwick Tree for a long time and now it is clear. Thank You for your efforts. :) ^_^
gotcha bro , u are the best one on the youtube , there are tons of creators who tried to explain same topic , i couldnt understand , u are the best.
thank u so much
In order to do a range query [x,y], should we need to get prefix sum [0,y] and [0,x) and subtract them?
well yes.. because BIT is just a prefix sum that can also be updated
why asking, you already know the answer lmao
Thanks for the visualization and the explanation! I think Fenwick Tree is beautiful :)
Big fan of your video blogs.. Best explanation ever.
One of the best videos on Fenwick Tree!!!
It would be great if some problems can be solved using BIT from competitive programming challenge.
+Prasenjit Mondal
codeforces.com/problemset/problem/597/C
have fun
Thank you for putting this up. Aap infi machate ho.......infi respect
Best Explanation. Simply Amazing. Thanks a lot! :D
Also for range other than 0,y let say we need to get range from x,y then just we gotta do is (0,y)-(0,x-1) :p I hope many may thought abt it so likhdiya ;p
Thanks 😁
Thanks for the video, would be nice if you could explain more about how was the rules you mentioned generated, it helps memorizing the rule.
Thank you sir it is very helpful video
I'm certain you can create the tree in O(n) if you use a faster algorithm. I think I found a way to calculate the values one by one where they take O(1) time amortized.
yes creating the initial tree can be done in O(n) this is quite well known.
Just for heads-up, 15:04 he means add 1, not 2, to the original number.
Amazing! You just remove my fear about fenwick tree.
Thanks
lovely stuff. thanks for explaining it so patiently. much appreciated.
Thank you very much for such a nice and lucid explanation.!!!
This is technically not a binary tree, because one node can have multiple child nodes. But other than that, it's smart. Thanks for the explanation!
Awesome work! Thanks a lot and keep up the good work.
what I figured out from the above video is.
if you want to find the sum of the ith element, then go to its parent and from there take the smallest 2^power element present in I and take the sum of that much element.
For example ,{ () represent power}
for 1 = 2(0) parent is 0 take 2(0) elements from there that is (0,0)
for 2 = 2(1) parent is 0 take 2(1) elements from there that is (0,1)
for 3 = 2(1)+2(0) parent is 2 take 2(0) elements from there that is (2,2)
for 4 = 2(2) parent is 0 take 2(2) elements from there that is (0,3)
for 5 = 2(2)+2(0) parent is 4 take 2(0) elements from there that is (4,4)
for 6 = 2(2)+2(1) parent is 4 take 2(1) elements from there that is (4,5)
Get next element explanation is intuitive. If current element is represented as parent index + next x elements (as power of 2), we need to increase the range of next x element by power of 2. Example: 6 = 2^2+2^1 then next element=2^2+2^2=8
Great work Tushar :)
Nicely explained. Thank you :)
Great explanation
Very clear explanation! Thanks for pulling this up!
It is the best explanation i think....every information is so clear and simply explained.....Do you have any tutorial regarding how to perform range updates in fenwick tree
***** Yes updating all elements in given range
you sir are a legend
awesome explanation sir ji ...
u r great ...
one of the best explanations of Fenwick Tree out there!
Great work,
Why would a segment tree take 4n space in the worst case? A tree with n nodes, has, n/2 leaf nodes, so shouldn't the worst case be 2n?
Thanks a lot sir
Thank you so much for this work! It really helped me to understand the BIT!
Very Nice Explanation.
Thank You for this amazing tutorial!
Thanks, Tushar ... Your videos r well-presented and a great help :) !!!!
Thank you for this great job.
Keep going Helped me so much
in filling up the tree, why didn't you say that 3 = 0 + 2^1 + 2^0 and start from index 0 just like you did in 2?
What I figured out is that for all the powers of 2 (2,4,8), he started from 0. Else he started in the descending order of powers of two. Just a rough guess.
Thanks for the awesome explanation!
Basic formula for get next : next(i) = 2*i - (i & (i-1))
Great video again. What are your thoughts on using Binary Indexed trees vs segment trees? I can use BIT for solving all problems which segment trees can? I find segment trees hard to implement in interviews..
Thank you ,master
Thank you very much, Tushar. This helps a ton!
I dont understand the part of index value evaluation, based on what? I mean the evaluation of each index in the fenwick tree for 1, 2, 3, .... and so on you started with 0 with some and 2 with others. also I can see that as an example the index 6 may have more than representation , the one you mentioned 3 = 2ofpower1+2ofpower0 not started by 0 as the 1 and 2, please can you make it clear more to me?
I got it. It depends on the binary bits count representation of the number in other words the number 4 represents by 100 in binary which has one active bit at position 3 with power 2 which equal 2 of power 2 then its value will start by 0 followed by the 4[2 of power 2] and for number 6 it represents by 110 which has more than one active bit at positions 2 and 3 or power of 1 and 2 respectively which equals to [2 of power 2] + [2 of power 1] and need to start from 0 for that number.
In the video, you said the TC of building the BIT is O(nlogn). If we use a prefix sum array just for making the tree, we can reduce it to O(n) right?
convoluted explanation !
Realy It was very helpful to me. Thanks boss.
superb explanation in a much simple way. :)
I learnt lot of things from you man thanks.
I think getParent for index i can be simply i&(i-1)..
I was thinking the same , CTCI had a question involving this i guess.
Correct.. that would be much simpler.
b'coz of ur explanations..... i'm able to code way better for competitve prog......thankx!
wow! awesome, very didactic!
heyy!! i must say that you are doing a great job!! i just wanted to confirm that if the number is a power of two then we take the summation from starting(ie index 0) to the number and in rest of the cases we are dividing the number in the decreasing power of 2s ?
great and clear explanation, thanks!
You are an inspiration.
It was really useful. (If you have time and patience could you upload the efficient way of filling the tree up. I am really intrested in that.)
Better ways:
1. To get the parent of i: binary AND i with (i - 1).
2. To get next of i: binary OR i with (i - 1) and add 1 to it.
great explanation sir !!
sir, wotever u r doing is awesome .. respect !! you always save my time with better explaination.. :)
explained completely fine. Stupid people gonna be stupid. You have to think for yourselves a little people.
much love brother
Excellent tutorial!! Will u please make a video on fenwick tree with range updates and range queries.
For sure you should go to MIT or any great place your are one of the best
Yusuf Awad he is placed in apple
He works at apple
/**
* To get parent
* 1) 2's complement to get minus of index
* 2) AND this with index
* 3) Subtract that from index
*/
private int getParent(int index){
return index - (index & -index);
}
/**
* To get next
* 1) 2's complement of get minus of index
* 2) AND this with index
* 3) Add it to index
*/
private int getNext(int index){
return index + (index & -index);
}
Can you explain reason behind this? I can see it works but dont get why?
BTW you are awesome.
Refer my ans to @Chris Z above :)
to get the rightmost bit flipped, just do x=(n&n-1)
e.g. :
7-> 7&6 = 6
9-> 9&8 = 8
I signed into my account to say thanks.
Sorry previously I was wrong so i removed it to avoid confusion.
while updating only difference should be passed as val to that method.
very clear! thank you !
Some Indian guy on RUclips! 😎
Hey, Nice work, although most efficient way to find parent is N AND N-1... Correct me if i am wrong.
Thank you so much. Keep up the good works :)
Excellent tutorial!! Keep it up bro
this is the best video