Fenwick Tree construction

Key Takeaways

all right welcome back everyone let's talk about Fenwick tree construction we've already seen how to do range queries and point updates in the last two videos but we haven't even seen how to construct the Fenwick tree yet and the reason I've kept this for last is you can't understand the Fenwick tree construction without having previously understood how uh Point updates work all right so let's dive right in so we could do the naive construction of a Fenwick tree so if we're given an array of values a and we want to transform this into a Fenwick tree what we could do is initialize our Fenwick tree to be an array containing all zeros and add the values into the Fenwick tree one at a time using Point updates to get a total time complexity of order n log n however we can do better we can actually do this in linear time so why bother with n log n all right so in the linear construction we're going to be given an array of values we wish to convert into the Fenwick tree a legitimate Fenwick tree not just uh the array of values themselves and the idea is we're going to propagate the values through throughout our Fenwick Tree in place and we're going to do this by updating the immediate cell that is responsible for us eventually as we passed through the entire tree everyone's going to be updated and we're going to have a fully functional Fen tree at the end of the day so it it kind of relies on this cascading idea so you you propagate some to the parent who's responsible for you and then that parent propagate its value to its parent and so on so it's just kind of like almost delegating the value so let's see how this works oh one more thing before that so if the current position is position I then the immediate cell above us which is responsible for us so our parent let's say that is J and J is given by I plus the least significant bit of I all right so if we start at one well the least significant bit of uh one is one so the parent is at position two so notice that there was a four at position two but we're going to add to four the value at I which is three so now position two has a value of seven now we want a b position two so find out which is responsible for position two so two plus the least significant bit of two is four so four is actually responsible for two or is immediately responsible for two so go to index 4 and add the seven then who's responsible for three well that's four so go to position four and add the value at index three now who's responsible for four well eight is responsible for four so go to position 8 and add the value of four so now in position 8 we have four so now we're at five and then you see how we keep uh doing this just updating our parent the immediate cell responsible for us so now seven is updating eight but now nobody well eight doesn't have a parent because our Fen tree is too small it only has 12 cells but the parent that would be responsible for eight is 16 and 16 is out of bounds so we just ignore it it's not relevant so now we keep going so I is nine 9's least significant bid is one so J is 10 that's where the parent is so keep propagating that value 10's parent is 12 11's parent also 12 and now we have the same sort of situation we had with eight where we have an out of bound situation so we ignore it so the values that are there right now are the values of the Fenwick tree and with these values we can do range queries and point updates not with the original array that we had so let's look at the construction algorithm itself in case you want to implement this we will have a look at some source code in the next video but if you're using another language that I'm not using this could be helpful so given an array of values we want to turn into a Fenwick tree let's get its Val the length which is n and I recommend you actually clone or make a deep copy of the values just so that you don't accidentally manipulate the values array while you're constructing your Fenwick tree um that could be problematic because we're doing all this stuff in place so clone the values array and then start I at one and go up to n and then compute J so the parent so which is I plus the least significant bit of I do an if statement to check if J is less than n that might actually be less than or equal to n actually now I'm thinking about it because everything is one based in in a Fen tree yeah I'm pretty sure that should be less than or equal to n all right so in the next video we'll be going over some source code so guys stay tuned for that and I hope you learn something hit the like button subscribe and I'll catch you in the next video