· Development

Range sums with a Fenwick tree: the ranges i & -i picks and where O(log n) comes from

How a Fenwick tree uses i & -i to give each cell a range, traced on 8 elements through update and prefix-sum loops, with index conventions, build cost, overflow and segment trees.

DevelopmentAlgorithmsData structures

Sometimes you need to keep changing elements of an array a while also asking for a[l] + … + a[r-1] over and over. A precomputed prefix-sum array answers each query in O(1), but changing one element means rewriting every prefix sum after it, so an update costs O(n). Keeping only the raw array flips that: O(1) updates, O(n) queries.

A Fenwick tree (binary indexed tree) brings both operations to O(log n), and it stores nothing more than one array of length n. This post uses the documentation and source of fenwick_tree in the AtCoder Library (ACL) as its reference and walks through a small example: which range each cell holds the sum of, and why the two loops visit exactly the cells they do.

Where it started: cumulative frequency tables

The name comes from Peter M. Fenwick’s 1994 paper “A new data structure for cumulative frequency tables”, Software: Practice and Experience vol. 24, no. 3, pp. 327–336. According to the publisher’s abstract registered with Crossref, the paper presents a “binary indexed tree” for maintaining the cumulative frequencies used in dynamic arithmetic data compression. The abstract says cumulative frequencies are split into portions that parallel the binary representation of an element’s index, and that traversal follows the binary coding of that index.

For this post, though, what I checked was the Crossref bibliographic record and abstract only. The full paper on Wiley could not be opened, and OpenAlex lists no open full text. The explanation below is based on the ACL docs and source code; it does not reproduce proofs or notation from the original paper.

ACL’s public API

The interface defined in the ACL docs:

Call Meaning Constraint Complexity
fenwick_tree<T> fw(n) n elements, all zero O(n)
fw.add(p, x) a[p] += x 0 ≤ p < n O(log n)
fw.sum(l, r) a[l] + … + a[r-1] 0 ≤ l ≤ r ≤ n O(log n)

Public indices are 0-based and ranges are half-open, [l, r). The internal loops, however, run on 1-based numbers. Mixing the two conventions is where most bugs come from, so in this post p is a public position and i (= p + 1) is an internal number.

Rewritten with the same structure as the ACL source, it looks like this. ACL takes the value type as a template parameter T; here it is fixed to long long for readability.

struct Fenwick {
    int n;
    std::vector<long long> data;  // data[i-1]: sum of the range internal number i covers

    explicit Fenwick(int n) : n(n), data(n, 0) {}

    void add(int p, long long x) {             // a[p] += x
        for (int i = p + 1; i <= n; i += i & -i) data[i - 1] += x;
    }
    long long prefix(int r) const {            // a[0] + ... + a[r-1]
        long long s = 0;
        for (int i = r; i > 0; i -= i & -i) s += data[i - 1];
        return s;
    }
    long long sum(int l, int r) const {        // a[l] + ... + a[r-1]
        return prefix(r) - prefix(l);
    }
};

ACL’s add likewise increments p, then while p <= n adds to data[p-1] and moves on with p += p & -p. Its internal prefix sum adds data[r-1] while r > 0 and shrinks r with r -= r & -r. The public sum(l, r) is the difference of two internal prefix sums.

i & -i: the lowest set bit

In two’s complement, -i is ~i + 1. Every bit below i’s lowest set bit is 0, so inverting turns those positions into 1s, and adding 1 makes the carry stop exactly at that lowest set bit. As a result, the only bit that is 1 in both i and -i is the lowest set bit.

i      = 6 = 0110
-i         = 1010   (low 4 bits)
i & -i     = 0010 = 2

Call this value lowbit(i). The cell for internal number i holds the sum over internal numbers (i - lowbit(i), i], which is public indices [i - lowbit(i), i). Odd numbers cover just their own element; powers of two cover everything from the start up to themselves. Internal number 0 is never used: 0 & -0 is 0, so a loop starting at 0 never ends. That is also why ACL’s add increments p first.

Tracing eight elements

Take the public array a = [5, 2, 9, -3, 4, 0, 7, 1] (0-based). Each cell’s range and value:

Internal i Binary lowbit Public range data[i-1]
1 0001 1 [0, 1) 5
2 0010 2 [0, 2) 7
3 0011 1 [2, 3) 9
4 0100 4 [0, 4) 13
5 0101 1 [4, 5) 4
6 0110 2 [4, 6) 4
7 0111 1 [6, 7) 7
8 1000 8 [0, 8) 25

Prefix sum prefix(7) (= a[0] + … + a[6]):

i Cell added Range Running total Next i
7 (0111) data[6] = 7 [6, 7) 7 7 − 1 = 6
6 (0110) data[5] = 4 [4, 6) 11 6 − 2 = 4
4 (0100) data[3] = 13 [0, 4) 24 4 − 4 = 0

The ranges [6,7), [4,6) and [0,4) don’t overlap and together cover exactly [0,7). Clearing the lowest set bit one at a time is the same as peeling blocks off the right end of [0, r). The direct sum 5 + 2 + 9 − 3 + 4 + 0 + 7 = 24 agrees.

Range sum sum(2, 7): prefix(2) adds data[1] = 7 at i = 2 and stops, so it is 7. That gives 24 − 7 = 17, and indeed 9 − 3 + 4 + 0 + 7 = 17.

Update add(2, +10): public position 2 is internal number 3.

i Cell changed Range Next i
3 (0011) data[2]: 9 → 19 [2, 3) 3 + 1 = 4
4 (0100) data[3]: 13 → 23 [0, 4) 4 + 4 = 8
8 (1000) data[7]: 25 → 35 [0, 8) 8 + 8 = 16 > 8, stop

In the table, only i = 3, 4 and 8 have ranges containing public index 2, and the loop visited exactly those cells. Adding lowbit causes a carry that pushes the next number’s lowbit to a higher position, and that cell covers a wider range enclosing the current one. After the update, prefix(7) is data[6] + data[5] + data[3] = 7 + 4 + 23 = 34, which is 10 more than the earlier 24.

Complexity

  • Prefix sum: each iteration removes one set bit from i. The number of iterations is the number of set bits in r, and since r ≤ n it never exceeds ⌊log₂ n⌋ + 1.
  • Update: adding lowbit(i) to i at least doubles the next number’s lowbit. The loop stops once i exceeds n, so it runs at most ⌊log₂ n⌋ + 1 times.
  • Range sum: two prefix sums, so O(log n).
  • Space: one array of length n, O(n).

This analysis is derived from the loops above; its conclusion matches the O(log n) stated in the ACL docs.

Build cost with initial values

The O(n) for ACL’s constructor is the cost of a structure in which every element is zero. Loading an arbitrary initial array by calling add n times costs O(n log n).

A linear-time build exists too. It is not part of ACL’s API, so you implement it yourself: fill data with a, then for i = 1 to n in order, add each cell’s value into its parent i + lowbit(i) (when that is ≤ n).

for (int i = 1; i <= n; i++) data[i - 1] = a[i - 1];
for (int i = 1; i <= n; i++) {
    int j = i + (i & -i);
    if (j <= n) data[j - 1] += data[i - 1];
}

Only numbers smaller than i send values into i, so by the time i is processed, data[i-1] is already complete. Applied to the a above, it produces [5, 7, 9, 13, 4, 4, 7, 25], the same values as the table.

Common pitfalls

  • Empty range: sum(l, l) is prefix(l) - prefix(l), i.e. 0. ACL’s constraint allows l == r.
  • Bounds: the ACL docs require 0 ≤ p < n and 0 ≤ l ≤ r ≤ n. In a hand-written version, letting internal number 0 into the update loop makes it run forever.
  • Negative deltas: for sums, subtracting with add(p, -x) just works.
  • Assignment: a Fenwick tree doesn’t store a[p] separately. To do a[p] = v you need the old value, so either keep the original array alongside and call add(p, v - a[p]), or recover the current value with sum(p, p + 1) in O(log n).
  • Overflow: the magnitude of a sum can reach n × max|a[i]|. With n = 2×10⁵ and |a[i]| ≤ 10⁹ that is 2×10¹⁴, beyond 32-bit integers, so you need 64 bits. The ACL docs state that for integer types, an overflowed answer is returned modulo 2^bit. In your own C++ code, signed integer overflow is undefined behavior, so pick a wide enough type from the start. More in the integer overflow post.

Compared with other structures

Query Point update Memory
Prefix-sum array O(1) O(n) n + 1
Fenwick tree O(log n) O(log n) n
Segment tree O(log n) O(log n) usually more than n nodes

Without updates, a prefix-sum array is simpler and faster. A segment tree also handles point updates and range queries in O(log n), and it extends to operations with no inverse such as min and max, and to range updates with lazy propagation, at the cost of more code and more storage. There is no basis for saying a Fenwick tree is always faster than a segment tree; the actual difference has to be measured for a given implementation and workload.

A Fenwick range sum relies on subtraction: prefix(r) - prefix(l). That only works for an operation with an inverse, like addition. Max is associative, but you can’t subtract away a prefix, so the max over an arbitrary range [l, r) can’t be obtained the same way. Restricted variants exist, such as answering only prefix maxima when values only ever increase, but this post stays with integer sums.

Uses: back to cumulative frequencies

Just like the original purpose described in the abstract, it works directly for counting occurrences of symbols 0…n−1. Call add(s, 1) whenever symbol s appears; the cumulative frequency of symbols below s is sum(0, s). Counting “how many values seen so far are ≤ x” over a value range the same way solves problems like inversion counting in O(n log n). If the value range is large, map it onto 0…k−1 with coordinate compression first.

Sources checked

All checked on 2026-10-27.

Back to the blog