I've been participating in programming contests ever since I was a child. However, I've always had this fear of advanced data structures and algorithms. To me, anyone discussing tricky combinatorics or Segment trees was like a magician; I would stand quietly next to such people and listen to them in awe, not understanding a damn thing.
However, once I finished university, I decided to give all this magic another go and finally become a sorcerer better developer too. One might think, "All these data structures and algorithms (also called DSA, by the way) are rubbish, as they are never used in real programming anyway." However, I have to disagree. You see, even though it's certainly not necessary to notice tricky use cases for most of the advanced DSA out there, they are useful in the way that they actually teach you how to think and to spot bigger patterns in general.
I believe that over the past several years I've become a quicker thinker simply because I've been practicing a lot of these very puzzles, be it on LeetCode or other websites I'll share with you. Nowadays, I can implement most of the basic algorithms without much thinking, similarly to how people use their native languages when they speak. Hence, I'm of the opinion that learning more advanced DSA may be beneficial to your overall self-confidence.
To make this article more interesting, I'm going to take you on a journey with me, so you're in for a treat today. Not only will you learn something new about an advanced data structure, but I'll also give you an idea of how to approach learning DSA in general.
What is a Fenwick Tree?
Do you like trees or do they scare you? What's the first thing that comes to your mind when you hear this word? If your first instinct is those green leafy plants, you're a normal person – stop reading here and enjoy the nature outside. If you thought recursion is the answer, I'll advice you to think a bit more. Perhaps there are some other kind of trees that don't imply this concept? Well, I wouldn't be asking you this question if the answer was no.
Sometimes it's easier to represent a tree in an array. Maybe you're already familiar with the Heap data structure. In this case, you know what I'm talking about. However, there are other examples as well, and one of them is the Fenwick tree.
Before going any further, I advice you to take a look at one amazing competitive programmer's handbook available for free on the Internet. It'd be rather foolish of me to simply teach you something you can read there, especially because Antti Laaksonen, the author, has explained this data structure truly well.
So, instead of rambling on and flexing my understanding of the Fenwick tree, I'll take you on a journey I recently took myself while learning this data structure. Still with me? Good, then go to the chapter called "Range Queries" and locate the section "Binary Indexed Tree." Incidentally, it's just another name for the Fenwick tree.
Say you have an array A = [2, 7, 6, 3, 5, 9, 0, 4] of size N, and you need to find the sum from the first element to the fifth one, i.e. the sum of [2, 7, 6, 3, 5]. Of course, we can do that in linear time, i.e. O(M), going through each element and summing up the total, but wouldn't it be neat to always get the answer in O(logM) instead, where M is the size of our range?
And with a little preprocessing on the initial array, which takes O(NlogN), the Fenwick tree allows us to do just that! What's more, your array doesn't have to stay the same during the whole process. In other words, you can update some of its elements in O(logN) time and still get your answer in O(logM) for any range sum query!
Before I continue, I advice you to go through that chapter all by yourself, just like I did a few days ago. I bet you'll be surprised at how much you can understand even on the first go! Still, there might be some things you can find a little bit tricky; at least, this was the case for me. Read on to find out how I managed to clear my doubts in the end.
The challenges I faced
Honestly, the explanation provided by the handbook was very clear, and I came up with my own implementation in Python pretty quickly:
class FenwickTree:
def __init__(self, A: list[int]) -> None:
self.n = len(A)
self.tree = [0] * (self.n + 1)
for k in range(1, self.n + 1):
self.add(k, A[k - 1])
def add(self, k: int, x: int) -> None:
while k <= self.n:
self.tree[k] += x
k += k & -k
def sum(self, k: int) -> int:
s = 0
while k >= 1:
s += self.tree[k]
k -= k & -k
return s
def range_sum(self, a: int, b: int) -> int:
return self.sum(b) - self.sum(a - 1)
Basically, the only functions I had to implement by myself were init and range_sum, which are pretty intuitive anyway. Perhaps the hardest thing to understand was the while loops, in which we do the following magic: k += k & -k and k -= k & -k. What's going on there?
Well, first of all, let's get clear on the fact that k & -k is just a fancy way of getting the last set bit in our number k. For instance, if k = 22, then this is what we get in the binary representation: k = 10110. To represent -k in computer memory, we have to make use of a so-called complement code, which you get by inverting all bits of k and adding 1, like so: -k = 01001 + 1 = 01010. Now, when you take k & -k, it's clear that you'll get the last set bit in k: k & -k = 10110 & 01010 = 00010. Play around with some other examples to see why it always works.
By the way, here's a nice article that explains how negative numbers are stored in a computer. I refer to it whenever I have to clear some doubts.
Anyway, why would we have to iteratively perform k += k & -k in the add method? Just look at the diagram in the last example from the book. When you update the value A[2] of our initial array, there are three values that get updated in our Fenwick tree: tree[3], tree[4], tree[8]. And here's how we get their indices:
# First iteration
k = 3
# Second iteration
k = 3 + (3 & -3) = 3 + 1 = 4
# Third iteration
k = 4 + (4 & -4) = 4 + 4 = 8
The function sum is very similar; the only difference is that summing up requires us to go to the left rather than to the right, which is why we subtract k & -k from k. For example, to get sum(7), which is the sum of the first 7 elements, we have to add up the following tree values: tree[7], tree[6], tree[4].
# First iteration
k = 7
# Second iteration
k = 7 - (7 & -7) = 7 - 1 = 6
# Third iteration
k = 6 - (6 & -6) = 6 - 2 = 4
Well, what I just shared with you is an approach I usually take whenever I don't understand a certain algorithm: I try to go step by step and imitate it using pen and paper. Diagrams and pictures are usually of great help too, which is why I found the examples in the handbook particularly useful.
How can you deepen your knowledge?
Okay, writing and understanding the whole thing is great, but is there something else you could do before moving on? Usually, I'd suggest playing around with the code a bit to make sure you fully understand it. However, I don't think it's very useful here.
Instead, it would be better to do some practice problems! Whenever I learn a new algorithm or a data structure, I prefer to practice it on a website called CSES. For example, you can go to the problem "Static Range Sum Queries" and solve it using our new data structure. You'll be surprised that the problem that might have looked so scary to you in the past will seem pretty easy now. This feeling of understanding something complex is very satisfying!
There are only a few lines you have to add to solve the above problem:
from sys import stdin
class FenwickTree:
# ...
n, q = map(int, stdin.readline().split())
A = [int(x) for x in stdin.readline().split()]
tree = FenwickTree(A)
for _ in range(q):
a, b = map(int, stdin.readline().split())
print(tree.range(a, b))
Remembering what you've learned
Now some of you might be wondering: "How do I make sure I won't forget this new data structure in the future?" I suggest focusing on just one thing: its use case. In other words, the only thing you need to remember is that the Fenwick tree is useful for handling a lot of range sum queries, and it also allows updates to the initial array.
Don't worry about memorizing the code, since you can simply save this data structure somewhere and refer to it as a ready tool. Seriously, no one would ever ask you to implement it from scratch, unless you participate in a competitive programming contest that doesn't allow you to look up your code snippets. But let's be honest, is it really such a common case?
Besides, if you truly get what's going on under the hood in the Fenwick tree, you're likely to recreate its implementation simply from your understanding. It's very similar to how we are able to write a letter when we already know what it's going to say.
What's next?
Great! We just learned a pretty advanced data structure, and hopefully, it didn't even feel that scary to you. Now you might feel more confident, ready to confront other advanced DSA, and to practice harder programming problems.
Even though some of you might still not be quite convinced as to why all these DSA matter, I'm pretty sure that over time, I'll shed more light on this question and insipire you to become a more well-rounded developer. After all, it's the exact path I'm on right now too.
Top comments (0)