@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).
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)
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!
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
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
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.
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.
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
@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; }
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.
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)
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.
Wow!!!!!! Amazing, I love u, Tushar!!!! From now on, every time I meet a new question or a new knowledge that I want to learn, I will come to your videos first!
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
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
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..
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
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 ?
