Binary indexed tree

Introduction

The binary indexed tree (or Fenwick tree) is a data structure that stores a list of numbers, while supporting fast updates and fast range sums both in Θ(log n) time. This efficient structure is useful for handling dynamic frequency tables in arithmetic coding.

The binary indexed tree has 3 fundamental operations. The most basic API possible would like this:

class BinaryIndexedTree {
    
    // Constructs a new tree that represents
    // a list of 'n' zeros. Requires n >= 0.
    // Effectively performs: int[] vals = {0, ..., 0};
    // Runs in Θ(n) time.
    BinaryIndexedTree(int n);
    
    // Adds the given amount to the element at
    // the given index. Requires 0 <= index < n.
    // Effectively performs: vals[index] += delta;
    // Runs in Θ(log n) time.
    void add(int index, int delta);
    
    // Computes the sum of the 'k' foremost
    // elements. Requires 0 <= k <= n.
    // Effectively returns: vals[0] + vals[1] + ... + vals[k-1].
    // Runs in Θ(log n) time.
    int prefixSum(int k);
}

In addition to the fundamental operations, a binary indexed tree can efficiently support other operations, as illustrated by these optional APIs:

    // Constructs a new tree representing the given list of numbers.
    // Effectively performs: int[] vals = vs.clone();
    // Runs in Θ(n) time.
    BinaryIndexedTree(int[] vs);
    
    // Gets the value of the element at the
    // given index. Requires 0 <= index < n.
    // Effectively returns: vals[index].
    // Runs in Θ(log n) time.
    int get(int index);
    
    // Sets the element at the given index to the
    // given value. Requires 0 <= index < n.
    // Effectively performs: vals[index] = val.
    // Same as add(index, val-get(index)). Runs in Θ(log n) time.
    void set(int index, int val);
    
    // Computes the sum of all elements.
    // Effectively returns: vals[0] + vals[1] + ... + vals[n-1].
    // Equal to prefixSum(n). Runs in Θ(log n) time.
    int totalSum();
    
    // Computes the sum of the given range [start,end)
    // of elements. Requires 0 <= start <= end <= n.
    // Effectively returns: vals[start] + ... + vals[end-1].
    // Equal to prefixSum(end)-prefixSum(start). Runs in Θ(log n) time.
    int rangeSum(int start, int end);

The most basic implementation of a binary indexed tree uses just one array of length n. If we add another array, we can speed up get() to Θ(1) time. If we add a scalar field, we can speed up totalSum() to Θ(1) time.

Source code

Java (SE 7+)

BinaryIndexedTree.java
BinaryIndexedTreeTest.java (JUnit)

The elements being stored are of type long (int64). Addition and subtraction of elements are performed modulo 2⁶⁴; overflow is unchecked but well-defined to wrap around.

Python

C++ (C++11 and above)

The type of numeric element being stored is parameterized as T. Note that if T is an unsigned type, then overflow is guaranteed to wrap modulo 2^N where N is the bit width of the type T. Otherwise if T is signed, then overflow is undefined behavior (nasty), unless the non-standard compiler option -fwrapv is used.

TypeScript / JavaScript

Be careful to not let the sum of any consecutive elements exceed ±2⁵³, or else there might be silent loss of precision in the sums.

Rust

The type of numeric element being stored is parameterized as T. Choose the type carefully with consideration towards overflow behavior.

License: MIT (open source)

Slow data structures

Let’s revisit the 3 fundamental operations that a binary indexed tree supports: Creating a list of zeros, adding to an element, and computing a prefix sum.

These operations are easy to implement with an array. Notice that add is fast but prefix sum is slow. So this is better if add is performed frequently but prefix sum rarely. The code sketch:

// Construct, Θ(n) time
int[] vals = new int[n];

// Add, Θ(1) time
vals[index] += delta;

// Prefix sum, Θ(k) time, worst-case Θ(n)
int sum = 0;
for (int i = 0; i < k; i++)
    sum += vals[i];

Alternatively, instead of having the array represents the elements themselves, we can make the array be the cumulative sum of elements. Now notice that prefix sum is fast but add is slow. So this is better if prefix sum is performed frequently but add rarely. The code sketch:

// Construct, Θ(n) time
int[] cums = new int[n];

// Add, Θ(index) time, worst-case Θ(n)
for (int i = index; i < n; i++)
    cums[i] += delta;

// Prefix sum, Θ(1) time
int sum = 0;
if (k > 0)
    sum = cums[k - 1];

More info

Note: My binary indexed tree implementation uses 0-based indexing for storage efficiency, whereas most literature/code uses 1-based indexing to simplify human understanding. In other words, index i in my code corresponds to index i+1 in most other people’s work.