Fenwick Tree (Binary Indexed Tree)

Point updates and prefix sums, range sums, coordinate compression, inversion counting, frequency order statistics, range update variants, and 2D Fenwick trees.

Typical operations: O(log n) update and prefix query, O(log n) range sum via prefix differences.

How it works

Index i (1-based) stores the sum of the range (i − lowbit(i), i], where lowbit(i) = i & −i. A prefix query walks i → i − lowbit(i), an update walks i → i + lowbit(i); each loop touches at most log₂ n cells.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Range-update/point-query uses a Fenwick tree over the difference array (Module 5); range-update/range-query uses two Fenwick trees. A 2-D Fenwick tree nests the loops for O(log² n) operations on a grid.

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n; vector<long long> t;
    explicit Fenwick(int n_) : n(n_), t(n_ + 1, 0) {}
    void add(int i, long long v) { for (++i; i <= n; i += i & -i) t[i] += v; }          // 0-based public index
    long long prefix(int i) const { long long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }   // sum of [0, i)
    long long range(int l, int r) const { return prefix(r) - prefix(l); }              // [l, r)
    int lowerBound(long long target) const {          // smallest i with prefix(i+1) >= target (non-negative values)
        int pos = 0; long long acc = 0;
        for (int step = 1 << 20; step; step >>= 1)
            if (pos + step <= n && acc + t[pos + step] < target) { pos += step; acc += t[pos]; }
        return pos;
    }
};

int main() {
    Fenwick f(8);
    vector<int> a = {5, 2, 9, 4, 7, 1, 3, 6};
    for (int i = 0; i < 8; ++i) f.add(i, a[i]);
    cout << "sum [2, 6) = 9+4+7+1 = " << f.range(2, 6) << '\n';
    f.add(3, 10);                                     // a[3] += 10
    cout << "after a[3] += 10: sum [2, 6) = " << f.range(2, 6) << '\n';
    cout << "cells covered by t[i]:";
    for (int i = 
…

sum [2, 6) = 9+4+7+1 = 21
after a[3] += 10: sum [2, 6) = 31
cells covered by t[i]: t1=(0,1] t2=(0,2] t3=(2,3] t4=(0,4] t5=(4,5] t6=(4,6] t7=(6,7] t8=(0,8]
inversions in {1000000,3,77,3,-50,12}: 10
3rd smallest of {42,7,99,7,15}: 15
20000 random updates/queries match a plain array

Quiz

? Which cells does t[6] cover in a 1-based Fenwick tree?
+ (4, 6] :: lowbit(6) = 2, so it covers 2 elements ending at 6.
- (0, 6] :: That would be t[8]-style coverage.
- (5, 6] :: lowbit(6) is 2, not 1.
- [6, 8) :: No.

? Why can a Fenwick tree answer range sums but not range minimums by subtraction?
+ Sums are invertible (subtract one prefix from another); minimum is not. :: Use a segment tree or sparse table for min.
- Minimum is too slow to compute. :: It is O(1) per merge.
- Fenwick trees only store counts. :: They store any group operation.
- They can. :: Not by prefix subtraction.

? What do the update loop `i += i & -i` and query loop `i -= i & -i` cost?
+ O(log n) each :: Each step changes the lowest set bit.
- O(1) :: No.
- O(√n) :: That is sqrt decomposition.
- O(n) :: No.