Binary Indexed Tree, or Fenwick Tree

BIT computes prefix sums and updates individual elements in \(O(\log n)\) time, using only \(O(n)\) space.

source code

Introduction

Binary Indexed Tree (BIT, or Fenwick Tree) maintains prefix sums of an array and supports adding a value to one element. Here we use ordinary addition: sum(i) returns a[1] + ... + a[i], and add(i, v) increases a[i] by v.

Unlike Segment Tree, Fenwick Tree directly queries prefixes. For addition, we can still query any range [l, r] by subtracting two prefixes: sum(r) - sum(l - 1). Other operations need their own algebraic conditions; associativity alone does not guarantee that the same query and update code works.

Fenwick Tree uses n + 1 array slots (index 0 is unused). An iterative segment tree commonly uses 2*n slots, and a recursive implementation commonly allocates about 4*n; all use \(O(n)\) space.

Fenwick Tree has two functions. They are sum and add, as shown below.

Which interval does each node store?

As in the segment tree diagrams, place each stored sum above the part of the original array it covers. Let lowbit(i) = i & -i: it is the value of the least significant set bit, and also the length of the interval stored at node i.

The invariant is: tree[i] stores the sum of a[i - lowbit(i) + 1 ... i]. Here a means the original array; tree means the BIT storage called A in the code below. The numbers in the diagram are indices, not array values or sums.

• tree[6]: 6 = 0b0110, so lowbit(6) = 2; it stores [5, 6].
• tree[12]: 12 = 0b1100, so lowbit(12) = 4; it stores [9, 12].
• tree[8]: 8 = 0b1000, so lowbit(8) = 8; it stores [1, 8].

Unlike a full segment tree, the BIT does not store both halves at every split: for example, it stores [1, 8] but has no single node for [9, 16]. It stores one block ending at each index, and the binary representation tells us how to move between blocks. The example uses n = 16 to make the pattern visible; n need not be a power of two.

add increase an element

1
2
3

void add(int i, T v) {  // increases original a[i] by v; A is BIT storage
    while (i <= n) A[i] += v, i += i & -i;
}

An update must change every stored interval containing the modified index. For add(5, Δ), these are [5, 5], [5, 6], [1, 8], and [1, 16].

i += lowbit(i) jumps to the next larger stored interval containing the current interval. In binary, adding the lowest set bit carries into a higher bit: 0101 → 0110 → 1000 → 10000. The new block’s right endpoint moves right, while its left endpoint stays put or moves left, so it still contains the updated element. Nodes between these jumps do not contain that element.

With n = 16, the loop visits 5 → 6 → 8 → 16, adds Δ to each stored sum, and stops when the next index is 32. Elements are 1-indexed; A[0] is unused, and add requires 1 <= i <= n (starting at 0 would never advance).

sum get a prefix sum

1
2
3
4
5

T sum(int i) {  // prefix sum of original a[1 ... i]; A is BIT storage
    T v{};
    while (i) v += A[i], i -= i & -i;
    return v;
}

To query a prefix, take the block ending at i, then continue immediately to its left. Because the block starts at i - lowbit(i) + 1, the remaining prefix ends at i - lowbit(i). This is exactly why the loop subtracts lowbit(i).

For sum(13), the steps are:

Thus sum(13) = tree[13] + tree[12] + tree[8]. For a concrete check, if a[i] = i, these stored sums are 13, 42, and 36, giving 91, the sum of integers 1 through 13.

Subtracting lowbit clears one set bit each time: 1101 → 1100 → 1000 → 0000. A query therefore visits as many nodes as there are set bits in its index, at most \(O(\log n)\). In an update, the lowest set bit moves strictly higher at each jump, so updates also take \(O(\log n)\) time. sum requires 0 <= i <= n; sum(0) returns 0, making the range formula work even when l = 1.

template

source code

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

#include <vector>

template <typename T>
class fenwick {
public:
  int n;
  std::vector<T> A;
  fenwick(int n): n(n), A(n+1) {} // A[0] not used
  T sum(int i) {  // prefix sum of original a[1 ... i]
    T v{};
    while (i) v += A[i], i -= i & -i;
    return v;
  }
  void add(int i, T v) {  // increases original a[i] by v
    while (i <= n) A[i] += v, i += i & -i;
  }
};

The constructor initializes all stored sums to zero. To build from an existing array, call add(i, a[i]) for each index 1 ... n; this simple construction takes \(O(n\log n)\) time. To assign a new value rather than add a delta, keep the original values and call add(i, new_value - a[i]), then update a[i]. Choose a numeric type large enough for all intermediate sums (for example, long long for integer sums that may exceed int).

Refs

• wiki: Fenwick Tree