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 point updates work.

Alright, 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 federal tree one at a time using point updates to get 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, legitimate finish tree, not just the array of values themselves.

And the idea is we're going to propagate the values throughout our Fenwick tree in place. And we're going to do this by updating the immediate cell is responsible for us. Eventually, as we pass through the entire tree, everyone's going to be updated, and we're going to have a fully functional Fenwick tree at the end of the day. So it kind of relies on this cascading idea. So you propagate some thing to the parent who's responsible for you and then that parent property, it's valued 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 AI. All right. So if we start at one, well, the least significant bit of 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 value I, which is three.

So now position two is value of seven. Now, we want a bit addition to, 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 four and add seven. Then who is 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 eight and add the value four. So now in position eight, we have four. So now we're at five, and then you see how we keep doing this updating our parent, the immediate cell responsible for us, it's now seven years of being eight.

But now Nobody will eat doesn't have a parent. Because our family tree is too small it only has 12 cells, but the parent that wouldn't be responsible for eight is 16. And 16 is a bound, so we just ignore it. It's not irrelevant. So now, we keep going. So I is nine nines, least significant bit is one.

So j is 10, as well the parent is so proxying that value 10s parents 12 elevens parent also 12. And now we are the same sort of situation we had eight where we have an out of band 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 one implement this, we will have a look at some source code in the next video. But if you're using another language using this could be helpful. So given an array of values, you want to turn into a Fenwick tree. Let's get it's about 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. And 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 bits of I don't If statement to check if j is less than n, that might actually be less than or equal to n actually now and think about it because everything is one based and in a Fenwick tree Yeah, I'm pretty sure it should be less than or equal to and 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 in the next video.