Patterns & Practice

March 2026 · 25 min read

The real power of Fenwick trees shows up in the problems they solve. This post covers the classic applications: counting inversions, coordinate compression, 2D BIT, order statistics, and a collection of competition-ready templates.

Pattern 1: Counting Inversions

An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. Counting inversions measures how "unsorted" an array is. The classic merge-sort approach runs in O(n log n), but a BIT solution is often cleaner.

The Idea

Process elements from left to right. For each element arr[i]:

1. Query: how many elements already processed are greater than arr[i]? That's i - query(arr[i]) (total processed so far minus those ≤ arr[i]).
2. Update: mark arr[i] as seen: update(arr[i], 1).

long long countInversions(vector<int>& arr) {
    int n = arr.size();
    // Coordinate compress to [1, n]
    vector<int> sorted_arr(arr);
    sort(sorted_arr.begin(), sorted_arr.end());
    sorted_arr.erase(unique(sorted_arr.begin(), sorted_arr.end()), sorted_arr.end());
    
    FenwickTree bit(sorted_arr.size());
    long long inv = 0;
    
    for (int i = 0; i < n; i++) {
        // Map arr[i] to its rank (1-indexed)
        int rank = lower_bound(sorted_arr.begin(), sorted_arr.end(), arr[i])
                   - sorted_arr.begin() + 1;
        // Elements seen so far with rank > current rank
        inv += i - bit.query(rank);
        bit.update(rank, 1);
    }
    return inv;
}

Pattern 2: Coordinate Compression

BITs index by value, so if values range up to 10⁹, you can't create an array that large. Coordinate compression maps the values to their rank in [1, m] where m is the number of distinct values.

// Given: arr with values up to 1e9
// After compression: mapped to [1, m]

vector<int> compress(const vector<int>& arr) {
    vector<int> sorted(arr);
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    
    vector<int> result(arr.size());
    for (int i = 0; i < arr.size(); i++) {
        result[i] = lower_bound(sorted.begin(), sorted.end(), arr[i])
                    - sorted.begin() + 1;  // 1-indexed rank
    }
    return result;
}

After compression, the BIT needs only m + 1 entries instead of max_value + 1. This is a key technique whenever BIT indices represent values rather than positions.

Pattern 3: 2D Fenwick Tree

Fenwick trees extend naturally to 2D for 2D prefix sums with point updates. The structure is a 2D array where each dimension uses the same lowbit logic:

class FenwickTree2D {
    vector<vector<int>> bit;
    int rows, cols;
public:
    FenwickTree2D(int r, int c) : rows(r), cols(c),
        bit(r + 1, vector<int>(c + 1, 0)) {}

    void update(int x, int y, int delta) {
        for (int i = x; i <= rows; i += i & (-i))
            for (int j = y; j <= cols; j += j & (-j))
                bit[i][j] += delta;
    }

    int query(int x, int y) {
        int sum = 0;
        for (int i = x; i > 0; i -= i & (-i))
            for (int j = y; j > 0; j -= j & (-j))
                sum += bit[i][j];
        return sum;
    }

    // Sum of rectangle [x1,y1] to [x2,y2]
    int query(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x1 - 1, y2)
             - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
    }
};

Operations are O(log(rows) · log(cols)). Memory is O(rows · cols) — the same as a plain 2D array, but with fast update support.

Pattern 4: Order Statistics

A BIT can find the k-th smallest element in a dynamic set in O(log² n) by binary searching on the prefix sums. Even better, with a bit of cleverness, you can do it in O(log n) using a technique called "BIT walking".

O(log² n) Approach: Binary Search on Prefix

// Find smallest x such that prefix(x) >= k
int kth_smallest(FenwickTree& bit, int n, int k) {
    int lo = 1, hi = n, ans = n;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (bit.query(mid) >= k) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return ans;
}

O(log n) Approach: BIT Walking

// Find smallest x such that prefix(x) >= k in O(log n)
int kth_smallest_fast(int bit[], int n, int k) {
    int pos = 0;
    int bitMask = 1;
    while (bitMask <= n) bitMask <<= 1;
    
    for (bitMask >>= 1; bitMask > 0; bitMask >>= 1) {
        int next = pos + bitMask;
        if (next <= n && bit[next] < k) {
            k -= bit[next];
            pos = next;
        }
    }
    return pos + 1;
}

The walking technique mirrors binary search but exploits the BIT's structure: each step tests one bit of the answer, moving or staying based on whether the partial sum at that position is enough.

Competition Templates

Template 1: Minimal BIT (Copy-Paste Ready)

struct BIT {
    int n; vector<long long> t;
    BIT(int n) : n(n), t(n + 1) {}
    void upd(int i, long long v) { for (; i <= n; i += i&-i) t[i] += v; }
    long long qry(int i) { long long s=0; for (; i; i -= i&-i) s += t[i]; return s; }
    long long qry(int l, int r) { return qry(r) - qry(l-1); }
};

Template 2: BIT with Max (Non-standard)

// Only works for POINT updates and PREFIX-MAX queries
// Values must be non-negative and updates must be non-decreasing
struct MaxBIT {
    int n; vector<int> t;
    MaxBIT(int n) : n(n), t(n + 1, 0) {}
    void upd(int i, int v) { for (; i <= n; i += i&-i) t[i] = max(t[i], v); }
    int qry(int i) { int m=0; for (; i; i -= i&-i) m = max(m, t[i]); return m; }
};

Caveat: Max-BIT only supports prefix-max with increasing updates. It cannot be used for arbitrary range-max queries or for decreasing values. For general range-max, use a segment tree.

Template 3: 2D BIT

struct BIT2D {
    int R, C; vector<vector<long long>> t;
    BIT2D(int r, int c) : R(r), C(c), t(r+1, vector<long long>(c+1)) {}
    void upd(int x, int y, long long v) {
        for (int i=x; i<=R; i+=i&-i)
            for (int j=y; j<=C; j+=j&-j) t[i][j]+=v;
    }
    long long qry(int x, int y) {
        long long s=0;
        for (int i=x; i; i-=i&-i)
            for (int j=y; j; j-=j&-j) s+=t[i][j];
        return s;
    }
    long long qry(int x1, int y1, int x2, int y2) {
        return qry(x2,y2)-qry(x1-1,y2)-qry(x2,y1-1)+qry(x1-1,y1-1);
    }
};

Practice Problems

Fenwick Tree Cheat Sheet

Series Wrap-Up

Across five posts, we've built a complete understanding of Fenwick trees:

1. Introduction, motivation and comparison
2. Structure & lowbit, binary indexing
3. Point Updates & Queries, core operations
4. Range Operations, difference arrays and two-BIT technique
5. Patterns & Practice (this post), applications and templates

Fenwick trees are one of those data structures that, once internalized, you reach for instinctively. They're the right tool for a surprising number of problems, and they're hard to beat on speed and simplicity when they apply.