Today I want to talk about Fenwick tree, also sometimes called the binary index tree. And you'll see why very soon. This is one of my personal favorites because it's such a powerful data structure. And it boosts efficiency. And it's really, really simple to code. So let's dive right in.

So things my covering the federal tree, video series, and just some standard stuff. So go over some motivation why this data structure exists, analyze time complexity, and then go into some implementation details. So in this video, we'll get to the range query, and later videos, how to do point updates and how to construct the final tree in linear time. You can also do things like range updates, but I'm not going to be covering that in this series. At least not yet. Okay, so what is the motivation behind the Fenwick tree.

So suppose we have an array of integer values, and we want to query a range and find the sum of that range. Well, one thing we can do would be to start at the position and scan up to where we want to stop, and then sum all the individual values between that range. That's fine. We can do this. However, it'll soon get pretty slow because we're doing linear queries, which is really bad. However, if we do something like compute all the prefix sums for the array, then we can do queries in constant time, which is really, really good.

So if we set the array p at index 00, and then we go on our array Add that element to the current prefix sum, we get five and then five plus minus three, give us two, and then six plus two is eight, and so on. So this is an elementary form of dynamic programming right here, check out prefer Excel sums. And then if we want to find the sum from say two to seven, nine inclusive, then we can get the difference between those two indices in the P array. And that's a constant time thing to compute the sum of the values between two and seven out inclusive, so that's really great. However, there's a slight flaw in this, which is what happens when we want to update a value in our original array. Say, we want update in text four, to be three.

Well now we have to recompute All the prefix sums. So this is really bad because recalculate all those prefix sums can take up to linear time. This is why the February ci was essentially created. So what is the fennel trees the family tree is a data structure that supports range queries on arrays and also point updates. Also range queries, but we won't be covering that in this video. So it's construction is linear time.

Point updates are logarithmic. range, some queries also logarithmic range updates logarithmic but you can't say add elements to the array. You can't make the array bigger or entirely remove elements. Okay, so let's look at how we can Do range queries on this thing. First thing you need to know is that unlike a regular array of Fenwick tree, each cell is not responsible for itself, but rather for a range of other cells as well. So we're going to say that a cell is responsible for other cells, depending on what the value of its least significant bit is, and its binary representation.

So on the left, I have a one based array. Fenwick trees are one base. That's very important. And I've on the side of that, I also put the binary representation of each of the numbers so you can clearly see what they look like in binary. So if we have say, the indexed Well, it's binary representation is 1100. So the least thing that can get is that left To most bit, so that is at position three in the binary representation.

So that index is responsible for, we're going to say two to the power of the position minus one, so four cells below itself. Similarly 10 has a binary representation of 1010. And the least least significant bit is at position two. So it's responsible for two cells below itself. And 11 has a leasing fee in their position one, so it's only responsible for oneself itself. So here, I've outlined the least, least significant bits, I've seen really hard to say, for all the odd numbers, which are just responsible for themselves, so that's what blue bar indicates the blue bars don't represent value, they represent a range of responsibility.

And that's really important for you to keep in mind. So, now, all the cells which have a range responsibility to now the cells have arranged responsibility for missile all these ranges of responsibilities or powers of two, eight is responsible for itself and is 16 for 16 cells. So now how do we do a range query on this now that we're not really working in a standard array, but rather this weird type of range of responsibilities? And the answer is we're going to calculate the prefix sum up to a certain index and that was eventually going to allow us to do range queries. So let's figure out how to do prefix sums, just like we did for a regular array. But on this factory.

So the idea is we're going to start at some index and cascade downwards until we reach zero, you'll see what I mean. So for example, let's find the prefix sum up to index seven. So when calculating the prefix sum from index, one to seven, inclusive, usually everything in a Fennec tree is inclusive. So if we look at where we are at seven, so we can get the value in the array at position seven, and then we want to cascade downwards. So the next guy below us is six, and then four. Notice that we were like hopping down.

So we start at seven and then we move down to six. And then from six, we go down to levels because six has a range of responsibility to, and then we're at four and four as a range responsibility of force that brings us all the way down to zero. And we're always going to be able to go from where we are all the way down to zero. So the prefix sum for seven is the array index seven plus the array index six plus the array index for right now to find the prefix sum for index 11. So we always start at where we are, so that's 11. And then we're going to cascade down.

So the cell directly below us, is 10. And 10, is arranges possible to so we're gonna go down to, so that's eight and then eight brings us all the way down directly to zero. Okay, cool. And one Last one, let's find the prefix sum up to index four. So four, we searched for four as arranger responsibility of exactly four sets already. We're back down to zero so we can stop.

Okay, let's pull this all together and try to do an interval sum between i and j. So let's calculate the interval song between, say 11 and 15. So the idea is we're going to calculate the prefix sum of 15 and 11. So we're going to calculate prefix sum of 15. And then we're going to calculate the prefix sum up to 11. But notice that we're now going to calculate up to 11. inclusive, but exclusive because we want the value at 11.

Okay, so if we start at 15, then we cascade down until we hit zero So 15 has arranger responsibility of one subsystem, subtract one from 15. Now we get to 14 and 14 has arranger responsibility of two, because the least significant bit on 14 is till now we go to 12 and then keep cascading down. So the prefix sum to 15 is the array index 15 plus 14 plus 12 plus eight. All right, now, the prefix sum for up to 11 non inclusive, so, we're going to start at 10. We like cascade down until we hit zero. So, 10 is arranger responsible to substract two from 10.

We get to eight. Now from eight has arranger responsibility of eight so cascade down, so eight minus eight zero. So now, the range sum is the sum of all the indices of 15 Minus those of 10, then that's how we would calculate the range sum. So notice that in the worst case, we're querying a cell which has a binary representation, which is all ones. And these are the numbers. So the form like to the n minus one, so a power of two, a minus one.

So a power of two has one bit set and all zeros, but when you subtract one, then your whole bunch of ones. So if you look at like 15, almost all of its bits are ones. And those are the worst cases. So in the worst case, we might be asked to query say 15 and seven, both of which have a lot of ones in them. So we're doing about to log base two of N up But in the average case, this actually pretty good. And we're going to implement this in such a way that it's just going to be a bit manipulation.

So this is like super fast. So the range query algorithm is pretty much this. You see, it's like literally no code range query from itj. We have a Fenwick tree of size. And so I'm going to define a function called prefix sum, which does that cascade cascading down operation. So So I in a while is not equal to zero.

We're going to sum up the values in our Fenwick tree. And we're going to remove the value of the least significant bit. And we're all we're going to keep doing this until our value is zero and then we can return sum to the range query. And it's just a difference between those prefix sums. So really neat little algorithm. Alright, thanks for watching this guys.

And in the next video, we're going to be doing point updates on affinity tree. So stay tuned for that. It's actually super cool and it works and just the opposite way. So it's almost the same algorithm. And if you want some source code for the Fenwick tree, make sure you check out the GitHub repository below should also be in description guys, thanks for watching. Hit the like button and I will catch you in the next video.