Data Structures & Algorithms

Fenwick Tree

A compact range-query structure for point updates, prefix sums, and frequency-based order statistics.

Category Data Structures

Level basic

Source TeX + C++

range queriesprefix sumsbinary lifting

Data Structures

Fenwick Tree

The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.

Raw TeX

Overview

The Fenwick tree is the data structure I reach for when the query is really about prefixes and the updates are local. It is smaller than a segment tree, usually easier to debug, and often exactly right for frequency tables after coordinate compression.

The usual contest version supports point updates and prefix sums. From that, range sums come for free by subtraction. With a couple of standard transformations, the same structure also supports range updates or order statistics on a multiset of counts.

When to Use It

Use it when:

the answer over \([l, r]\) can be written as the difference of two prefixes,
updates affect one index at a time, or can be reduced to a few point updates,
you want something lighter than a segment tree,
the array is really a compressed axis of frequencies, counts, or prefix contributions.
Typical patterns include inversion counting, sweep-line counting, offline rectangle queries, dynamic frequency tables, and ``find the k-th active value'' after coordinate compression.

Core Idea

For a 1-indexed array, each cell \(\texttt{bit[i]}\) stores the sum of a suffix of the prefix ending at \(i\). The length of that suffix is the least significant set bit:

\[ \mathrm{lsb}(i) = i \& (-i), \qquad \texttt{bit[i]} = \sum_{j=i-\mathrm{lsb}(i)+1}^{i} a_j. \]

responsibility

So \(\texttt{bit[12]}\) covers a chunk of length \(4\), namely \([9, 12]\), because \(\mathrm{lsb}(12) = 4\). Different indices cover chunks of different lengths, but they fit together in a very structured way.

Worked example.

Suppose I want the prefix sum up to \(13\). The Fenwick walk visits: \[ 13 \rightarrow 12 \rightarrow 8 \rightarrow 0. \] That means the query uses the disjoint buckets \([13,13]\), \([9,12]\), and \([1,8]\). Those intervals are exactly the full prefix \([1,13]\), with no overlap and no missing position.

Key Insight

The two famous transitions \[ i \mathrel{-}= i \& -i \quad\text{and}\quad i \mathrel{+}= i \& -i \] are not arbitrary bit tricks. They are the reason the structure works.

In a prefix query, subtracting \(\mathrm{lsb}(i)\) removes the chunk currently owned by \(\texttt{bit[i]}\), then jumps to the next disjoint chunk still needed.
In an update, adding \(\mathrm{lsb}(i)\) jumps to the next Fenwick bucket whose responsibility range still contains the updated index.
So the query walk partitions a prefix into canonical chunks, while the update walk climbs through exactly the buckets that must be changed.

Operations / Main Technique

The standard interface is:

add(i, delta): add \(\texttt{delta}\) to one position,
prefix_sum(i): sum the first \(i\) values,
range_sum(l, r): answer by \(\texttt{prefix\_sum(r) - prefix\_sum(l - 1)}\),
kth(k): on nonnegative frequencies, find the first index whose prefix sum is at least \(k\).

Range tricks.

The three standard variants are worth remembering:

point update + range query: the ordinary tree,
range update + point query: maintain the difference array in one Fenwick tree,
range update + range query: use two Fenwick trees and prefix algebra.
I do not memorize the formulas blindly. I remember that Fenwick trees like prefixes, so the trick is always to turn the desired operation into something prefix-based.

Correctness Intuition

The invariant is that every \(\texttt{bit[i]}\) stores one canonical interval ending at \(i\). Those intervals are chosen so that:

the prefix walk visits disjoint intervals whose union is the queried prefix,
the update walk visits exactly the intervals that contain the updated position.
That is enough for correctness.

For queries, nothing is double-counted because the visited intervals are disjoint. Nothing is missed because the walk stops only after consuming the whole prefix. For updates, every bucket that should contain the position is visited, and every bucket that should not contain it is skipped.

Complexity Analysis

point update: \(O(\log n)\),
prefix query: \(O(\log n)\),
range query: \(O(\log n)\),
k-th query on frequencies: \(O(\log n)\),
memory: \(O(n)\).
The logarithm comes from the number of times the least significant set bit can change before the index reaches \(0\) or leaves the array.

Implementation

The reference code keeps the 1-indexed version because I find it easier to reason about than the 0-indexed formulas. It includes:

add,
prefix_sum,
range_sum,
kth for a frequency table.
That is already enough for a large fraction of Fenwick tree problems. The main implementation habit is to convert the external index convention once and then stay consistent everywhere else.

Common Pitfalls

Mixing 0-indexed input with a 1-indexed Fenwick implementation.
Calling kth when some frequencies are negative, so prefix sums are no longer monotone.
Forgetting that range sums use \(\texttt{prefix\_sum(l - 1)}\), not \(\texttt{prefix\_sum(l)}\).
Using int when prefix sums can easily exceed \(2^{31} - 1\).
Remembering that ``Fenwick supports range updates'' but forgetting which transformed array is actually stored.

Variants / Extensions

Two-tree Fenwick for range add and range sum.
Fenwick over frequencies for order statistics.
Multidimensional Fenwick trees for offline geometry or matrix updates.
Fenwick on a different associative group, not just sums, as long as prefix subtraction makes sense.
There are also specialized variants for prefix minima under restricted updates, but sums and frequencies are still the main contest use cases.

Practice Problems

Count inversions after coordinate compression.
Maintain a dynamic multiset with insert, erase, and k-th queries.
Offline rectangle counting with a sweep line over one axis and a Fenwick tree over the other.
Problems where range updates can be rewritten as difference-array point updates.

References

Peter M. Fenwick, A New Data Structure for Cumulative Frequency Tables.
cp-algorithms: Fenwick Tree.
AtCoder Library: fenwicktree.
Codeforces Catalog.

C++ competitive_programming/dsa/data-structures/fenwick-tree/code.cpp

Kept as a standalone source file so the implementation can be copied without TeX markup around it.

Raw file

struct Fenwick {
    int n;
    vector<long long> bit;

    Fenwick() : n(0) {}
    explicit Fenwick(int n) { init(n); }
    explicit Fenwick(const vector<long long>& values) { build(values); }

    void init(int n_) {
        n = n_;
        bit.assign(n + 1, 0);
    }

    void build(const vector<long long>& values) {
        init((int)values.size());
        for (int i = 0; i < n; ++i) {
            add(i + 1, values[i]);
        }
    }

    void add(int idx, long long delta) {
        for (; idx <= n; idx += idx & -idx) {
            bit[idx] += delta;
        }
    }

    long long prefix_sum(int idx) const {
        long long result = 0;
        for (; idx > 0; idx -= idx & -idx) {
            result += bit[idx];
        }
        return result;
    }

    long long range_sum(int left, int right) const {
        if (left > right) return 0;
        return prefix_sum(right) - prefix_sum(left - 1);
    }

    // Smallest index idx such that prefix_sum(idx) >= k.
    // Assumes all values are nonnegative and 1 <= k <= total sum.
    int kth(long long k) const {
        int idx = 0;
        int step = 1;
        while ((step << 1) <= n) step <<= 1;
        for (; step > 0; step >>= 1) {
            int next = idx + step;
            if (next <= n && bit[next] < k) {
                idx = next;
                k -= bit[next];
            }
        }
        return idx + 1;
    }
};

Show raw files

Note TeXcompetitive_programming/dsa/data-structures/fenwick-tree/note.texC++ codecompetitive_programming/dsa/data-structures/fenwick-tree/code.cppFigure 1competitive_programming/dsa/data-structures/fenwick-tree/figures/responsibility.svg

Fenwick Tree

Overview

When to Use It

Core Idea

Key Insight

Operations / Main Technique

Correctness Intuition

Complexity Analysis

Implementation

Common Pitfalls

Variants / Extensions

Practice Problems

References

Code

Source Files and Assets