uniolympiads Ελληνικά

Fenwick tree

Update one element and query a prefix sum, both in O(log⁡n)O(\log n), with one array and two loops.

When

When prefix sums are not enough because the array changes between queries. For sums (or anything with an inverse, such as xor) it is shorter and faster than a segment tree.

The idea

With 1-based indexing, node ii holds the sum of the last i&(−i)i \mathbin{\&} (-i) elements up to and including ii. i&(−i)i \mathbin{\&} (-i) is the lowest set bit of ii. For example, node 12=1100212 = 1100_2 holds a9,…,a12a_9, \dots, a_{12}.

  • Prefix up to ii: add tit_i and clear the lowest bit, i−=i&(−i)i \mathrel{-}= i \mathbin{\&} (-i), until 0.
  • Update at ii: update tit_i and climb, i+=i&(−i)i \mathrel{+}= i \mathbin{\&} (-i), until nn.

Each loop takes at most ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 steps.

Range update, point query. Range Update Queries asks for "add vv to [l,r][l, r]" and "what is aka_k?". Keep the difference array inside the Fenwick tree: add(l, v), add(r + 1, -v), and aka_k is prefix(k).

The kk-th element. With non-negative values, lowerBound(k) walks down the bits from the highest and finds the smallest ii whose prefix is ≥k\ge k, in O(log⁡n)O(\log n). With occurrence counts, this is the kk-th smallest element of a multiset.

Pitfalls

  • Indexing starts at 1. With add(0, v) the loop never ends, because 0&0=00 \mathbin{\&} 0 = 0.
  • In Salary Queries the values go up to 10910^9. Compress the coordinates first, reading all queries offline.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/fenwick.cpp
// Fenwick tree (binary indexed tree), 1-indexed.
// add(i, v): a[i] += v.  prefix(i): a[1] + ... + a[i].  Both O(log n).
// i & -i is the lowest set bit of i: node i stores the sum of the last (i & -i) elements up to i.

struct Fenwick {
    int n;
    vector<ll> tree;

    Fenwick(int size) : n(size), tree(size + 1, 0) {}

    void add(int i, ll v) {
        while (i <= n) {
            tree[i] += v;
            i += i & -i;
        }
    }

    ll prefix(int i) {
        ll s = 0;
        while (i > 0) {
            s += tree[i];
            i -= i & -i;
        }
        return s;
    }

    ll rangeSum(int l, int r) {
        return prefix(r) - prefix(l - 1);
    }

    // Smallest i with prefix(i) >= k, assuming all values are non-negative. Returns n + 1 if none.
    int lowerBound(ll k) {
        int pos = 0;
        int step = 1;
        while (step * 2 <= n) {
            step *= 2;
        }
        while (step > 0) {
            if (pos + step <= n && tree[pos + step] < k) {
                pos += step;
                k -= tree[pos];
            }
            step /= 2;
        }
        return pos + 1;
    }
};

Tested on 500 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.