Alright, let's have a look at some Fenwick tree source code. I'm here in my GitHub repository. You can find it at this link which I'll put in the description below. William fees slash data dash structures, and the Fenwick tree is source code is right here under the Fenwick tree folder, so let's dive right in. I have it here local on my computer, and my text editor. Alright, so this source code is provided to you in Java, but it's really easy to translate it to any language you're working in.
So I create a Fenwick tree class which has two constructors. One they'll create an empty tree for a given size and then you populate yourself and another one which you give it an array of values. Like was on last video and constructs the Fenwick tree in a linear time. So this is probably the constructor you want to use, and not the other one. But I give you the option to use either or. So one thing that you guys should know is that the values array pass in, this thing needs to be one based.
In the last video, I was hesitant on whether or not he has to go less than or less than or equal to the length of the array. And that's going to depend on whether your way is one based or zero based. Usually everything if no tree is one based, in which case, it would be less than if you're using this as the length. All right, but other than that, so this is just the construction algorithm we saw. So just propagate the value to the parent. So That's right here and ignore it if it's out of bounds, so pretty simple stuff.
So this is probably one of the most interesting methods is the least significant bit method. And it's going to return the value of the least thing and if you bet for some integer I, so this bit magic right here, essentially isolates and returns the least significant bit value. Something that's a bit more readable is this right here, which is Java has built in method finally significant bit. However, using a Rob manipulation, like this without initial function call will be faster. Okay, so the prefix songs. This is something we covered in the first video, which allows you to compute the prefix sum from one to AI both inclusive and all this has been done one based.
So this would do the cascading down that we talked about. So start with a sum equal to zero and add the values that the indices you hit along the way while cascading down. And this line line 55 is equivalent to i minus equal the least significant bit of IO, which is a lot more readable than this crazy manipulation, which essentially just clears that bit. But you want to use as much bit manipulation as you can't keep your family tree fast, even though it's already really, really fast. But the More button manipulation you use, the less operation or machine level operations you're going to do. And so your program is going to be so much faster.
Okay, if you want to find the sum between inclusive then Then we can call the prefix some methods right here, and just essentially get the differences. So that's easy. So adding, so this is for a new appointment date acquisition I and add K to it. So k can be positive or negative, that doesn't really matter. So what you're going to do as for AI, you're going to update everyone who's responsible for you. So all the ranges, they're responsible for you.
And for each of those, you're going to add the constant K. And then you're going to propagate up to your parent by saying i equals i plus the least significant bit, and you're going to do that until you're still within the tree at some valid index. And this additional method I added for fun is to set the index is equal to Okay, this might sometimes be useful. So just get the value add, I saw eye to eye, and then call the Add method. So pretty simple stuff. As you see this is, what 8080 ish lines and half of it is comments. So this is a really simple and yet extremely fast the structure.
Guys, thanks a lot for watching. Hit the like button, subscribe if you learned something, and I'll catch you in the next data structure I cover or if you have any suggestions, I'm also open to those. See you next time.