Fenwick Trees are Awesome!

submited by

Style Pass

2025-01-15 17:30:34

This post will only use one-based indexing since that’s what Fenwick trees traditionally use, although they can be modified to use zero-based indexing.

So imagine you have an array $A$ of size $N$, and you’d like to support two operations. The first one, called $Update(i, v)$, is trivial: Given an index $i$, add $v$ to $A_i$. Easy peasy!

Cool. For the second operation, $RangeQuery(i, j)$, you’re given $i$ and $j$, and you’d like to find the sum of the elements of $A$ between indices $[i, j]$ inclusive. Also super easy, right?

Problem is, that’s really inefficient if $A$ is huge! Due to that loop, $RangeQuery$ takes $O(N)$ time. However, $Update$ is as fast as it could possibly be and only takes $O(1)$ time. So, can we do better for $RangeQuery$?

Summing from $i$ to $j$ is really slow. What if we had some sums already computed? Specifically, if we knew the sum from $[1, j]$, and subtracted the sum from $[1, i - 1]$, we’d end up with the sum from $[i, j]$. This only takes $O(1)$ time!