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[k1]. // 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, valget(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[n1]. // 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[end1]. // 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+)

The elements being stored are of type
long
(int64). Addition and subtraction of elements are performed modulo 2^{64}; overflow is unchecked but welldefined to wrap around.  Python
 C++ (C++11 and above)

The type of numeric element being stored is parameterized as
T
. Note that ifT
is an unsigned type, then overflow is guaranteed to wrap modulo 2^{N} where N is the bit width of the typeT
. Otherwise ifT
is signed, then overflow is undefined behavior (nasty), unless the nonstandard compiler optionfwrapv
is used.  TypeScript / JavaScript

 BinaryIndexedTree.ts / BinaryIndexedTree.js
 BinaryIndexedTreeTest.ts / BinaryIndexedTreeTest.js
 BinaryIndexedTreeTest.xhtml
Be careful to not let the sum of any consecutive elements exceed ±2^{53}, 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, worstcase Θ(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, worstcase Θ(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 0based indexing for storage efficiency, whereas most literature/code uses 1based indexing to simplify human understanding. In other words, index i in my code corresponds to index i+1 in most other people’s work.