Fenwick Tree range queries

today I want to talk about the 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 boasts efficiency and it's really really simple to code so let's Dive Right In so things I'm going covering in the Fenwick tree uh video series just some standard stuff so go over some motivation why this data structure exists and its time complexity and then going 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 F Tree in linear time you can also do things like uh 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 uh the fwi tree so suppose we have an array of integer values and we want to query a uh range and find the sum of that range well one thing we can do would be to uh 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 uh 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 a then we can do queries in constant time which is really really good so if we set the array P at index 0 to B 0 and then we go in our array a and add that element to the current prefix sum we get five and then 5 + -3 give us 2 and then 6 + 2 is 8 and so on so this is an elementary form of dynamic programming right here calculating all the prefix sums and then if we want to find the sum from say 2 to 7 non-inclusive then we can get the difference between uh those two indices in the uh P array and that's a constant time thing to compute the sum of the values between 2 and seven non-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 a say we want to update inex 4 to be three well now we have to recompute all the prefix sums so this is really bad because recalculating all those prefix sums can take up to linear time this is why the fen CH was essentially created so what is the fen tree the F tree is a data structure that supports um Range queries on arrays and also Point updates also range queries but we won't be covering that in in this video so its construction is linear time Point updates or logarithmic um 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 a Fen 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 represent presentation so on the left I have a one based array Fenwick trees are one based a SP important and I 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 index 12 it's binary representation is 1 0 0 so the least significant bit is that leftmost 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 one one0 and the least sign least significant bit is that position two so it's responsible for two cells below itself and 11 has a least significant bit position one so it's only responsible for one self itself so here I've outlined uh the least sign least significant bits it's getting really hard to say uh for all the odd numbers which are just responsible for themselves so so that's what the blue bar indicates the blue bars don't represent value they represent range of responsibility and that's really important for you to keep in mind so now all the cells which have a range of responsibility of two now the cells have a range of responsibility of four notice that all these ranges of responsibilities are powers of two um e is responsible for eight cells and I guess 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 uh 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's what's eventually going to allow us to do rrange queries so let's figure out how to do prefix sums just like we did for a regular array but on this fwk tree so the idea is we're going to start at some index and uh Cascade downwards until we reach zero you'll soon see what I mean so for example let's find the prefix sum up to index 7 so we're calculating the prefix sum from index 1 to 7 inclusive but usually everything in a f Tre 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're like hopping down so we start at seven and then we move down to six and then from six we go down two levels because six has a range of responsibility of two and then we're at four and four is a range responsibility of four so 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 7 plus the array index 6 Plus aray index 4 all 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 then 10 is a range of responsibil of two so we're going go down two 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 start at four four is a range of responsibility of exactly four that's 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 sum between say 11 and 15 so the idea is we're we going to calculate the prefix sum of 15 and 11 so we're going to calculate the prefix sum of 15 and then we're going to calculate the prefix sum up to 11 but notice that we're not going to calculate up to 11 uh 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 a range of responsibility of one sub subtract one from 15 then we get to 14 and 14 has a range of responsibility of two because the least significant bit on 14 is two okay now we go to 12 and then keep cascading down so the prefix sum for 15 is the array at index 15 plus the array at 14 + 12 + 8 all right now the prefix sum for up to 11 non-inclusive so we're going to start at 10 now we want to Cascade down until we hit zero so 10 has a range of responsib of two so substract two from 10 get to eight now from eight has a range of responsibility of eight so Cascade down so 8 - 8 zero so now the range sum is the sum of all the indices of 15 minus those uh of uh 10 and that's how we would calculate the range sum um 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 of the form like 2 the N minus one so a power of two minus one so a power of two um has uh one bit set and all zeros but when you subtract one then you get a 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 um 15 and 7 both of which have a lot of ones in them so we're doing about two log based two event operations 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 the range query for my to J we have a Fenwick tree of size n so I'm going to define a function callede fix sum which does that Cascade cascading down uh operation so we start at I and while I is not equal to zero we're going to sum up the uh values in our fck 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 the sum so the range query then is just a difference between those prefixed sums so really neat little uh algorithm all right thanks for watching this guys uh and in the next video we're going to be doing Point updates on aen tree so stay tuned for that it's actually super cool and it works in just the opposite way so it's almost the same algorithm and if you want some source code for the Fenwick tree make sure to check out the GitHub repository uh below it should also be in the description guys thanks for watching hit the like button and I will catch you in the next video