This content originally appeared on Bits and Pieces - Medium and was authored by Fernando Doglio
The mediocre data structure that successfully fails at optimization
Sometimes data structures have a direct and very practical use case that you can think of and understand why someone would come up with it.
That’s not always the case though, sometimes data structures are simply there because they provide an advantage or a performance improvement somehow. Are you always going to use them? Unlikely. But you’ll be happy to know about them the moment when it actually comes in handy.
So today, I wanted to tell you about BITs, or in other words, Binary Indexed Tress, a data structure that tries to make searching and inserting as optimized as possible and fails at it.
The “why” behind BITs
I like to call BITs the “mediocre data structure” because while others focus on optimizing either the insert or the read operation on trees making it O(1) and leaving the other one as O(n), BITs try to improve both.
However, you can’t insert and read into a Tree in constant time, hence why I say that this particular DS fails at what it tries to do, because it’s really impossible to achieve.
That said, it gets pretty close, in fact, BITs allow you to insert and read data both with an O(Log n) performance. Not great, but not terrible either, so, you know, kinda mediocre.
Joking aside, BITs allow you to both, query the tree and update it with a reasonable performance. So if you’re dealing with tree-like structures and your logic performs many reads and writes to it, then this might be the right data structure for you.
The main use case for this DS, is the ability to have efficient prefix sums of elements inside an array (i.e the sum of all elements up to the n-th one). This apparently comes in handy when working with Arithmetic coding. But let’s not dive into that rabbit hole right now.
Implementing a Binary Indexed Tree in JavaScript
To implement this code, we’re not going to do what you’d expect. Instead of implementing a tree-like structure with classes, we’re going to represent this structure as an array and we’ll use a special bit operation to understand how to traverse it.
We’re going to focus on two operations: updating it and getting the sum up to a particular position.
The update operation will add a given value to the desired position and it’ll also traverse the structure down the tree to update all children.
The “getSum” operation will return the sum of the sub-tree starting from the first node up to the desired one.
Creating the BIT
The first thing we’ll cover is how to create it. Like I said before, we’ll represent it as an array, and we’ll move through it by calculating the last set bit of the current index, and either adding it or removing it from it, depending on whether we’re moving down or up the tree.
To create the BIT initially, we’re going down, so we’ll add the last set bit.
Initially, our BIT array is all set to 0, and then we start going through our original array of values, and we start following this logic:
- We start at the first index (in this case 0)
- We add 1 to the index (our BIT array is leaving the initial element empty).
- We add the value from the array at the current index, to the new position inside the BIT array.
- We take the last set bit of our index (i.e 1) and add it to the index (turning it into a 2).
- Go back to step 1.
Let’s assume we have this array to begin with: [2, 1, 1, 3, 2, 3] and we want to save the prefix sum on our BIT.
- Starting at index 0, we get the value 2.
- We go to our BIT array and add 1, so our BIT index is 1.
- We add 2 to the value in our BIT array at position 1 (making it a 2).
- We take the last set bit of 1, which is 1, and add it to our BIT index (making it a 2).
- At index 2 of our BIT array, we’re adding 2 again, making it a 2.
- The last set bit of 2 (10) is 2, so we jump to BIT index 4.
- We add 2 at the BIT index 4, making it a 2 as well.
- The last set bit of 4 (100) is also 4, so we would jump to index 8, which doesn’t exist, so we end here.
At this point, the BIT array looks like this: [0, 2, 2, 0, 2, 0, 0]
And we only added the first 2 of the original array. We do the same for the second element of our array (at position 1):
- Original index 1 means BIT index 2 (remember, we add 1 to the index at the start).
- We add a 1 to the value in BITArray[2], making it a 3
- The 2 turns into 4 so we add 1 to the 4th position of our BIT array, making a 3 as well.
- And now, the 4 would change to 8, which again, is out of range, so we stop here.
At this point, the BIT array looks like this: [0, 2, 3, 0, 3, 0, 0]
And if we keep going, we’ll get:
Idx — BIT array
0 — [0, 0, 0, 0, 0, 0, 0] - initial state
1 — [0, 2, 2, 0, 2, 0, 0] - first iteration
2 — [0, 2, 3, 0, 3, 0, 0] - second iteration (described above)
3 — [0, 2, 3, 1, 4, 0, 0]
4 — [0, 2, 3, 1, 7, 0, 0]
5 — [0, 2, 3, 1, 7, 2, 2]
6 — [0, 2, 3, 1, 7, 2, 5]
In the end, once we’ve added all values to our BIT array, we have [0, 2, 3, 1, 7, 2, 5]
With that understood, let’s look at an implementation of this:
The constructBITree function is the one that initializes the array and for each value, it updates it.
Now, once the array is set, we can start querying, which essentially means we can ask for the prefix sum of our values up to an index of our choice.
Querying the tree
To query the tree we follow a similar approach as before, but in reverse.
Instead of starting at index 0, we start at the index we’re looking for (adding 1 of course), and move “up” the tree subtracting the last set bit of the index to itself until we reach 0 or lower.
For our BIT array: [0, 2, 3, 1, 7, 2, 5] let’s say we want to query the tree to get the prefix sum of the 5th element. This of course, would mean it’s the same as adding up all values of the original array (it has 6 values).
- Now, we start with the index 5, but we add 1 to it, so 6
- The value at index 6 on the BIT array is 5.
- Now, we take the last set bit of the index (6, which is 110 in binary) and subtract it, so it turns to 4.
- The value at index 4 of our BITArray is 7, so we add it to 5, which gives us 12 so far.
- The last set bit of 4 is, well, 4, so we subtract it and get 0.
- We’re done.
So instead of going through the original array adding all numbers, which would’ve been the equivalent of an O(n) algorithm (with “n” being 6), we only needed 2 values from the BITArray.
This change turned our O(n) into an O(Log2(n)) algorithm. Pretty neat, isn’t it?!
Now, let’s look at the implementation:
It’s a simple implementation, the key is on line 8, where we subtract the last set bit from our current index. That’s where all the magic happens really.
Did you like what you read? Consider subscribing to my FREE newsletter where I share my 2 decades’ worth of wisdom in the IT industry with everyone. Join “The Rambling of an old developer” !
Binary Indexed Trees are very cool once you understand the logic behind them. Don’t feel bad if they make no sense on the first try, it took me a long time to “get it”. My recommendation would be to try and break up the process as much as you can, seeing the intermediate values stored in the array, and following the steps I showed you above.
Have you used BITs before? What have you done with them? I’d love to know about a real-world implementation of this data structure! So make sure to share it in the comments!
Build apps with reusable components like Lego
Bit’s open-source tool help 250,000+ devs to build apps with components.
Turn any UI, feature, or page into a reusable component — and share it across your applications. It’s easier to collaborate and build faster.
Split apps into components to make app development easier, and enjoy the best experience for the workflows you want:
→ Micro-Frontends
→ Design System
→ Code-Sharing and reuse
→ Monorepo
Learn more
- How We Build Micro Frontends
- How we Build a Component Design System
- The Bit Blog
- 5 Ways to Build a React Monorepo
- How to Create a Composable React App with Bit
Advanced Data Structures and Algorithms: Implementing your first Binary Indexed Tree was originally published in Bits and Pieces on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Bits and Pieces - Medium and was authored by Fernando Doglio
Fernando Doglio | Sciencx (2022-12-21T08:01:49+00:00) Advanced Data Structures and Algorithms: Implementing your first Binary Indexed Tree. Retrieved from https://www.scien.cx/2022/12/21/advanced-data-structures-and-algorithms-implementing-your-first-binary-indexed-tree/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.