A Fenwick tree or binary indexed tree is a data structure that helps compute prefix sums efficiently. Computing prefix sums are often important in various other algorithms, not to mention several competitive programming problems. For example, they are used to implement the arithmetic coding algorithm. Fenwick trees were invented by Peter M. Fenwick in 1994.

The \(n^\text{th}\) prefix sum of an array is the sum of the first \(n\) elements of the array.

This idea is also referred to as partial sums or cumulative sums.

What is the prefix sum of positive integers?

---

They are triangular numbers as shown in the diagram below.

triangles

The simplest way to compute the \(i^\text{th}\) prefix sum is to just scan over the first \(i\) elements of the array whilst adding them.

1
2
3
4
5

def prefix(arr,i):
   s = 0
   for j in xrange(i):
      s += arr[j]
   return s

This computes the prefix table in \(O(n)\) time. However, this is a little too much when the table has to be frequently updated, since the prefix tables have to be computed over and over again.

We can do better using a Fenwick tree.

Let's say that we have a 16 element array which forms the leaves of the following binary tree:

The leaves are labelled from 0000 to 1111.

Let us imagine that the parent nodes contain the sum of the children nodes everywhere throughout the tree. That'd mean that the root node has the sum of all the elements in the array.

Key Idea: The interesting observation is that to produce the sum of the first \(i\) elements we only need to know (and check) just \(O(\log i)\) nodes.

We only need to preserve the red nodes. The yellow nodes are only around for the demonstration. In fact, the red nodes are what the Fenwick tree consists of.

How would you find the \(1010^\text{th}\) prefix sum?

---

We use the red nodes labelled 1010, 100 and 0.

Now, let us look into how this can help when the values in the leaves change. When the value in a leaf is incremented, we just need to notify all the red nodes from the root to the leaf. Since the height of the tree is in \(O(\log n)\), we just need to perform \(O(\log n)\) operations.

This section can be hard unless you have the intuition.

For the sake of simplicity, we will assume that we are working with 1-based arrays.

Here is what the Fenwick tree on the array [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] would look like when embedded in an 1-based array:

We have already seen the motivation behind the data structure. Now, we need to see how it can be built, updated and queried.

Update

To increment the \(i^\text{th}\) position by \(x\):

\(1.\) Express \(i_1 = i = 2^{j_1} + 2^{j_2} + \cdots + 2^{j_n}, \text{ where } j_1 < j_2 < \cdots < j_n.\)

\(\hspace{1cm} 1.1\) Increment the \({i_1}^\text{th}\) position of the tree by \(x.\)

\(2.\) Let \(i_2 = 2^{j_1 + 1} + 2^{j_2} + \cdots + 2^{j_n},\) where the \(j\)'s are set as before.

\(3.\) Replace \(i_1\) by \(i_2\) and loop from step \(1\) until \(i_1\) exceeds the length of the array/tree.

As discussed before, this runs in \(O(\log N,)\) where \(N\) is the length of the Fenwick tree.

The above can be a little confusing, but the essential idea here is that we're notifying the parent "responsible" nodes of the changes. If you are really baffled, sketching through the idea with pen and paper can really help.

To create a Fenwick tree for an array, simply create and fill an empty tree with zeroes and then update the tree with all the array positions one by one. Thus, for an array with \(N\) entries, it takes \(O(N \log N)\) operations to setup its Fenwick tree.

Query

To query the \(i^\text{th}\) prefix sum:

\(1.\) Set the accumulator to 0.

\(2. \) Express \(i = 2^{j_1} + 2^{j_2} + \cdots + 2^{j_n}, \text{ where } j_1 < j_2 < \cdots < j_n.\)

\(\hspace{1cm} 2. 1.\) Increment the accumulator by the value in the \(\left(2^{j_1} + 2^{j_2} + \cdots + 2^{j_n}\right)^\text{th}\) position of the tree.

\(\hspace{1cm} 2. 2.\) Increment the accumulator by the value in the \(\left(2^{j_2} + \cdots + 2^{j_n}\right)^\text{th}\) position of the tree.
\(\hspace{1.3cm}.\)
\(\hspace{1.3cm}.\)
\(\hspace{1.3cm}.\)
\(\hspace{1cm}2. n.\) Increment accumulator by the value in the \(\left(2^{j_n}\right)^\text{th}\) position of the tree.

\(3. \) Return the current value of the accumulator.

This is no surprise, just simply adding up whatever we already stored during the update. This runs in \(O(\lg N)\) too.

The happy coincidence that computers internally use the binary system to represent integers brings us to a very interesting bit manipulation trick that makes it easy for us to implement the above algorithms.

Notice that we need to express integers as powers of two very frequently, and usually work with the lowest power in the above algorithms. Now, this lowest power is really the last set bit of the integer.

\[12 = 2^3 + 2^2 = (1100)_2\]

Here, the place value of the last set bit is \(100.\)

Obviously, we could write a loop to find this but it turns out that there is a better (simpler) way to do this. It turns out that a & (-a) does a very good job of the same.

Let us work out the same thing with 12.

We have \(a = \) 0b1100, the complement of which is 0b0011.

Thus \(-a = \) 0b0011 + 0b0001 or 0b0100.

1 2	>>> 12&-12 4

This should work for any integer. Here is a generalisation

The highest power of two which is not more than a is given by a & (-a). \(_\square\)

Let's say that \(a\) is an integer with the binary representation \(s 1 0^n.\)

Now, the complement of \(a\) is \(s' 0 1^n.\)

Hence, \(-a\) or the two's complement of \(a\) is \(s' 1 0^n \) (because by adding a 1, the 1's roll over and the 0 turns 1).

Now, we have the bitwise-and of \(a\) and \(-a\) = s100.... & s'100... = 100... = \(1 0^n \) since the \(s\) and \(s'\) cancel out. \(_\square\)

The implementations are straightforward, except that using the 1-based array can be easily mishandled.

Python:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Fenwick(): def update(self, i, x): #add x to the ith position while i <= self.x: self.BIT[i-1] += x #because we're working with an 1-based array i += i & (-i) #magic! don't touch! def query(self, i): #find the ith prefix sum s = 0 while i > 0: s += self.BIT[i-1] i -= i & (-i) return s def __init__(self, l=[]): #initialize the fenwick tree self.N = len(l) self.BIT = [0 for i in xrange(self.N)] for i in xrange(1,self.N+1): self.update(i, l[i-1])

Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

public class Fenwick{ int N; int* MyTree; public static int Fenwick(int a[],int N){ this.N=N; this.MyTree=new int[(this.N)+1]; for(int i=0; i<=N; i++){ MyTree[i]=0; } c=0; for(int i=1; i<=N ; i++){ c=i+a[i-1]; } } int getCum(int i){ int ax=i; int sum=0; while(ax>0){ sum+=MyTree[ax]; ix=ix+(ix&-ix); } return sum; } void addValue(int i, int v){ int ax=i; while(ax<=N){ MyTree[ax]+=v; ax+=(ax&-ax); } } int get(int i){ return getCum(i)-getCum(i-1); } }

C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Fenwick{ /*1-indexed*/ int N; int* MyTree; public: Fenwick(int a[],int N){ /*constructor to initialize Fenwick Tree*/ this->N=N; this->MyTree=new int[(this->N)+1]; for(int i=0;i<=N;i++){ MyTree[i]=0; } for(int i=1;i<=N;i++){ addValue(i,a[i-1]); } } int getCum(int i){ /*get i-th Prefix Sum*/ int ix=i; int sum=0; while(ix>0){ sum+=MyTree[ix]; ix=ix-(ix&-ix); } return sum; } void addValue(int i,int v){ /*add v to i-th value*/ int ix=i; while(ix<=N){ MyTree[ix]+=v; ix=ix+(ix&-ix); } } int get(int i){ return getCum(i)-getCum(i-1); /*get i-th value of array*/ } };