Why Fenwick Trees Work

Added: 2026-05-09

[00:00:00]Okay. So suppose you have an array as shown on the screen and I ask you to do two things again and again. The first one would be to give me the sum from L to R or you change any element from the array.

[00:00:18]So the basic approach which one should think of is they would just run a loop from L to R and initialize a variable sum equal to zero. run a for loop and just update sum plus equal to a of y and just return the sum. Right? This is the naive approach which one would think about us. The second approach is if someone calculates the prefix sum correct. So what would that case be is they would make an array known as prefix let's say and for index zero like till index zero the sum is three or let's take one bas indexing right for index one the sum is three for index two it becomes four for index three it becomes 8 for index four it becomes 9 for index 5 it becomes 14 and for index 6 it becomes 23 three. So if someone asks them that give me the sum from uh index two to index let's say five. So what they would do is just take index five and remove index one.

[00:01:41]Perfect. They would just take everything from here and remove this index. So we would get the sum from L to R. Now the third concept is where F vectorry comes into play. But before that let's discuss the time complexity for both of these.

[00:01:57]For the brute force approach the time complexity to return the sum is big of N. Correct? Because you basically traversing the whole array.

[00:02:08]For prefix sum the time complexity to return the sum is constant.

[00:02:14]But what if I change an element? What if I make this three a two? Well, you'll have to form your entire prefix array again. So to update the time complexity becomes v of and this is where conveyor actually comes into the picture, right?

[00:02:30]It acts as a middle month. Let's analyze its complexity first.

[00:02:36]For range sum it would give that in big of login time.

[00:02:43]Updates it would give that in of login time as well. And it uses memory which is B of N. And all of this is possible with just a single magical equation which is I and this is the and operator can I and minus I correct? So let's decode this magical equation and first understand the basics of binary representation because those form the foundations of fenicray. So let's understand that first. Now let's understand why we aren't going forward with the prefix sum approach right because you might be saying hey I say like we are getting big of one time.

[00:03:32]What's wrong with that? Well, the entire reason you switched from the kn approach to the prefix sum approach was to reduce complexity in some case, right? So the time complexity for naive approach was big of n and we optimized it. We found some way we found the prefix some way and we optimized it to big of one which is constant n. But again here we are facing issue that when we update the element the cost after updating is same as the kn approach. So we are partially still stuck with the kn approach.

[00:04:09]So hence we need something better and we need something which optimizes for both of those things. So here is where fenvic vector actually comes into play. And before we analyze how I and minus I computes the LSB, uh we first need to actually understand what LSB is. And in order to understand what LSB is, we need to understand what basics of binaries are. Let's just brush off the basics of binaries really quickly. So now I have written that 13 is equal to 8 + 4 + 1.

[00:04:42]What am I trying to say? What I'm trying to say is every integer can be written in terms of summation of powers of two.

[00:04:50]So if you just see here this is 2 to 3.

[00:04:55]This is 2 to2 and this is 2 to0 right looks like a 6 2 0.

[00:05:04]If you like take any integer and you will be able to divide it into summation of powers of two. Right? So how do we calculate the binary for 13? Like how do we represent 13 in terms of binary? So it's fairly simple. You just draw this.

[00:05:23]Uh most of you all would be able to do it mentally. But just for the beginners, um you can practice calculating binaries like this, right? 1 2 4 8 16. Uh if you notice these are just when you raise powers of two right correct so for 13 what all am I using which all powers of two am I using I'm using eight I'm using four so 8 becomes 1 four becomes one and I'm using one which is 2 to 0 7 that becomes one and everything else becomes zero so The binary for 13 comes out to be this or you can write it as this. Both of these are exactly the same thing.

[00:06:14]Okay. Uh you can represent it like base two because binary means a yes or no zero or one. Right? So only two options are there. So this is how you represent this in terms of binary. Now I want you to pay attention to one important thing which is binary is always read from right to left. Here also we started raising the powers of two from right hand side. Right? So when we traverse this binary we will traverse it from the right hand side. So which is the first set bit? Set is one of or unset whatever you want to call it is zero. Which is the first set bit? The first set bit I can see is over here. The very first position right and the very first position we got it from here. Correct.

[00:07:11]So the lowest set bit or the least significantly set bit which is the lsb or it is also called as the low bit that for 13 is one.

[00:07:29]Okay because the first time the set bit occurs from the right hand side is at the position one. Got it? Let's calculate this was for 13. Right? Let's do it for 12. For 12, we can represent it as 8 + 4 and other becomes zero. So here when we traverse from right to left, we see is this one? No. Is this set bit? No. This is a set bit. And it is at position four. So if I ask you the low bit of 12, what would that be? Think for a moment. That would be four. So you can calculate low bit for 16 8 um 14 as your homework and see if you get it. And now let's understand why I and minus I actually computes the low bit and gives us the answer in a mathematical way like why is this the mathematical operation?

[00:08:30]What's the derivation behind it? So let's understand that. Now finally needs this low bit very quickly and computers have an exceptional way of calculating it which is using this expression. So let's take an example. If I is12 is binary is 1 1 0 0 and the low bit I'm representing low bit as k over here is oh as we have seen before right. So if we consider 12 as I and minus I as -2. So this is its binary.

[00:09:08]Now how do we get minus2? We just don't flip all the bits. We flip the bits and we add + one to it. Okay. We flip the bits and we add + one to it. So over here if you see only this is the part which is going to yield the result of one, right? because and of everything else is going to be zero. So eventually we are left out with um 1 0 0 which when converted to the normal integer it becomes four. And this is the interesting observation over here that this is actually equal to a k which we calculated visually right that for 12 the low bit is four and how a computer actually calculates it is it takes the end of i and minus i and it would actually give us the low bit. So whatever the value for low bit is that actually becomes the fenic tree block size.

[00:10:19]Yes. So let's move on towards fenvic tree and understand its structure and it forms its own bit array and it's working and where should we use it. So let's go into that now. Here we have this array which I have shown for sample right and we'll understand how does bit of work work over here. Uh what exactly is block size? what exactly do I mean by the block size which low gives us right and what exactly do I mean by bit of y stores the block size right so we'll understand that now first uh let's understand the two points which are array of i actually stores the value at position i fairly simple right for example array of four would give me one array of seven would give me two correct what does bit of i bit of a stores the values of small chunks from array which ends at i. Okay. So what do I mean by this? Let's take an example. Uh let's say our i is 6. Okay. And the binary for six would be 1 0 and low bit or let's not write low bit over here. K I'm representing K as the low bit. Let's say we have a function which gives us low bit. Okay, it returns a low bit and it gave us the low bit for six. For six, the low bit would actually be two correct. So we got two. Now here if I ask you what does array of six which is I store and what does bit of six store?

[00:12:05]Array of six is fairly simple. It stores 9 bit of six stores the values from array of file. So in terms of chunks right what is the size of the chunk. So what is the block size basically that is given to us by the low bit number. So what does low bit actually tells us is store a chunk of size two which ends at six. So that would basically be six and five. Correct? So bit of six would actually store a of five plus a of six.

[00:12:48]Correct? Because the low bits value is two. The chunks size is two and it's storing a value ending at six. Index six. Correct? So the value which bit of six will uh which bit of six will actually hold would be 9 + 5 which is 14.

[00:13:10]For example, let's calculate another value. Let's calculate for i = 3.

[00:13:19]For y is equal to 3. The binary would be 0 1 0 0 1 1.

[00:13:27]And the value for low bit or k would be 1.

[00:13:35]So this means that bit of three will only store a of three because chunk of size one would only be a single element right which ends at three and that will have to be three. So bit of three would be equal to four and it forms the whole array right bit of one bit of two and so on till bit of eight and it stores values inside them in terms of chunks as we just discussed right okay so rather than me filling the entire table and forming the bit array let's form it together right for i is equal to 1 what is the value for k the value for k would be 1 so that means bit of i stores a chunk of size one. So which ends at index one. So that would just be the single element.

[00:14:29]Right? We are here right now. So that would be a of 1. And the value for that would be just three. Correct? Then we come here. For two, the binary is 0 1 0.

[00:14:43]So it would be 2 to 1, which is 2.

[00:14:47]And now this would store a chunk of size 2 which ends at two. So a of 1 plus a of 2. And what will its value be? It will be 3 + 1 which will be four. Now we come at index three. For index three, k would be again one and it would store only a of three because a chunk of size one which ends at index three its value would be just four because at index three it's just four. This is one based index.

[00:15:25]Incorrect. Then at index four the value for this would be 2 to2 which is four.

[00:15:31]So low bit would be four over here. That means it would store a chunk of size four which ends at index four. So that would be a of 1. Let's say a of two let's say a of three let's say a of four and the value for that would be this value which would be 5 6 9.

[00:15:53]Then at index five, at index five, the low bits value would be one and it would store just a of five and its value would be five.

[00:16:07]Then for uh index the value would be 2 and it would store a of 5 plus a of 6 its value would be 5 + 9 which is 14.

[00:16:22]For index 7, it would again be one and it would just store a of 7 which is 2.

[00:16:31]And for index 8, its value is actually 2 to 0 2 1 2 2 3 which is 8. So loit's value over here is 8. That means it would actually store a to 1 + a to2 until a to 8. So the chunk over here is actually the entire array.

[00:16:53]So the array's entire sum that would be 32.

[00:16:59]So this is how the entire working of the bit array, the low bit, the block size and everything connects together. But now you would see that this is called a fan tree, right? Where is the tree?

[00:17:15]there is no relation with the tree or any sort of thing right which we have seen. So the tree is actually constructed from this table over here and let's construct the tree. Now I've just erased the right hand side. So while constructing the tree we have to keep three things in mind. Okay. The value for n which is the current node, the value for a which is the low bit and the value for n minus. Okay, we'll keep on updating this as and when we go forward. So, let's start with the node zero which is currently null. I'll have to make it a little bit bigger which is null. This is connected to node one. How? The value for node here is one. The value for k here is one. And what is the value for n minus k? Zero.

[00:18:09]That means node one is connected to node zero. So here it is node one and node one actually stores bit of one and bit of one is nothing but just a of one I think right? Yeah a of one.

[00:18:32]So this is an node one. Then for node two the value for low bit is 2. That means n minus k is again zero. That means node 2 is also connected here storing bit of two which is a of 1 + a of 2.

[00:18:54]Then node three here the value for k is 1. So the value for n minus k would be two.

[00:19:03]So that means node three would be connected over here uh from two because n minus k is two. So node 3 is connected with two and node three is storing bit of three which has just a of three.

[00:19:22]I'll just do one more for node four and then you can form the entire tree by yourself. Right? It's fairly [snorts] pretty simple. So for node four the value for case four. So we can just see the uh n minus k value comes out to be zero.

[00:19:37]So node four is connected over here with bit of four and it stores a of 1 + a of 2 till a of four and this is node four correct. So this is how actually the tree is formed. Now if suppose I were to ask hypothetically in this tree itself the value for a bit of three right. So what would be the time to traverse the whole tree? Uh that would be the height of the tree. And what is the height of the tree? It is login. Right?

[00:20:13]So that's where the time complexity for tree comes out to be login. Right?

[00:20:18]Because the worst case scenario which you'll be traversing uh that is the very depth of the tree that would come out to be login. Right? Let's write some functions for it now. Right? uh for example if we were to create a add function.

[00:20:35]So how would that work? Suppose we want sum from uh 1 to 7 let's say. So we would actually require a prefix of seven. We would actually require let's see we want seven. We want five and six and we want four as well.

[00:21:00]So that would actually be bit of 7 plus bit of six plus bit of four because bit of seven covers seven, bit of six covers five and six and bit of four covers the first four elements.

[00:21:25]Correct? So if we see then bit of file actually stores from some place to I. Now can this someplace be shown as a mathematical formula? Well, it can be shown. You can write it as I minus low bit + one.

[00:21:56]Let's check for six. Okay, for six it's storing five and six, right? So bit of i stores from five to six. So for six, what is the value for i? It is six minus low bit for 6 is 2 + 1 till 6. Correct? from dash to i. So this comes out to be 7 5 5 to 6. Here you go.

[00:22:23]So when I first time saw this formula, you know, while reading a research paper in I'll add the links to all the papers and references in the description. Um, and it was truly good when I first saw this formula. And I think if you're into film and you really love uh learning the concepts behind all of these things, you would be interested in reading those out too. So what you should actually think about when you are uh building the ad function for fictory is when you're moving left, you're actually collecting the blocks from the left. Right? For seven, we collected seven. Then we collected five and six. And then we can see we collected 1 2 3 and four. So we are moving backwards. That means our I is getting subtracted. So hence the formula and this would come out to be I minus = I and minus for update. I want you to actually think about it yourself. And there's just a small change when you update the formula would become I plus equal to this magical term. But I want you to think about this plus yourself. And I'll just show you how the code looks for finictory how the strct for fry is form.

[00:23:48]And yeah, you can see over here that the sum function actually uses I minus equal to Y and minus I which we just discussed, right? That is because and we have also added while if greater than zero because it is one base indexing right and zero doesn't exist in a table as well. And for add you can see over here I told you that we are using plus equal to I and minus. So this is how the basic structure for code would be. Um these parts are just construction initializations and uh formation of vectors and stuff which you can look out. That's very basic part of C++ right and this is usually used in computer programming as well the template which I have showed over here uh you can copy the template as well I'll provide the link in the description and I'll also provide a few links for a good research papers which you can check out yourselves and that's it for