I want to talk about Fenwick trees and point updates. So let's dive right in. But before we get to that, absolutely, make sure you checked out the Fenwick tree range query video that I posted last, just to get the context of how the Fenwick tree is set up and how we're doing operations on it. Okay, so just to refresh your brain on how we actually did a prefix sum, and how we did those range queries. So what we did was, we started at a value at some index doesn't matter which and then we continuously removed the least significant bit until we hit zero. That's a cascading down effect that gave.

So let's say we started at 13 or 13, the least significant bit was one, so we removed one, and we got 12. And then we found out that the least nificant bit of 12 was four. So we removed four and then the least significant of eight was eight, then we reach zero. And once we reach zero, we know that we're done. So doing a point at date is very analogous to this. Instead of removing, we're going to be adding the least significant bit as you'll see.

So for instance, if we want to add a value at index nine, then we have to find out all the cells which are responsible for nine because remember, cells are responsible for a range of responsibility. So if we start with nine, we find the least significant impact 910 so 10 finally significant bit, is has a value of two, then we add it to 10 then find the least significant bit 12 at 12. So it's for now 16. And then we would do the same thing, and then we're out of bounds. So we will know to stop. So if I draw a line outwards from nine, all the cells that I hit are the ones I have to update.

So remember, those lines represent a range of responsibility. So the lines that I hit are the ones that I got when I added the least significant bits. Okay. So for to add some constant x at position six in the Fenwick tree. Which cells do I need to modify? So we start sex, and then we find the least significant bit six and add sex.

So get eight, find the least significant bit of eight and add 816. So if I draw a line out from six, then indeed the cells that I do hit are six, eight and 16. So the required updates for our Fenwick tree are that we need to add x to position six, eight and 16. So the algorithm is really really simple. So if we have a Fenwick tree, stored in an array of size n, then while I, so is the position we originally want to update, so i is less than n. We're going to add x to the tree at position I and add on The value of the least significant bit of AI. And that's it where the function LSB is the least significant bit of AI.

And there are built in functions to do that usually. And we're going to have a look at some source code. Alright, so that was point updates. And now we actually need to construct the Fenwick tree. And we're going to do that in the next video. So guys, if you learned something, please hit the like button and share this video.

And that's all for now. I'll catch you next time.