Fenwick Tree (Binary Indexed Tree)

Overview

Fenwick Tree, also known as Binary Indexed Tree (BIT), is a space-efficient data structure that supports prefix sum queries and point updates in O(log n) time. It’s particularly useful when you need to frequently update elements and query prefix sums.

Time Complexity

Build: O(n log n)
Point Update: O(log n)
Prefix Query: O(log n)
Range Query: O(log n) (two prefix queries)

Space Complexity: O(n)

Implementation

range_query_fenwick_tree_std.cpp

template <typename T> class Fenwick {
  public:
    vector<T> fenw;
    int n;

    Fenwick(int _n) : n(_n) { fenw.resize(n); }
    
    void modify(int x, T v) {
        while (x < n) {
            fenw[x] += v;
            x |= (x + 1);
        }
    }

    T query(int x) {
        T v{};
        while (x >= 0) {
            v += fenw[x];
            x = (x & (x + 1)) - 1;
        }
        return v;
    }
};

template <typename T> using fenwick = Fenwick<T>;

Custom Node Structure

For more complex operations, you can use custom node structures:

struct node {
    int a = 0;  // Default value
    
    inline void operator+=(const node &other) {
        a += other.a;
    }
    
    inline node operator-(const node &other) {
        node result = *this;
        result.a -= other.a;
        return result;
    }
};

fenwick<node> ft(n);

Basic Usage

Prefix Sum
Range Sum
Frequency Counter

int n = 10;
fenwick<int> ft(n);

// Add values to positions
ft.modify(0, 5);  // arr[0] += 5
ft.modify(1, 3);  // arr[1] += 3
ft.modify(2, 7);  // arr[2] += 7
ft.modify(5, 4);  // arr[5] += 4

// Query prefix sum [0, 2]
int sum = ft.query(2);  // Returns 15 (5+3+7)

// Query prefix sum [0, 5]
sum = ft.query(5);  // Returns 19 (5+3+7+0+0+4)

fenwick<int> ft(n);

// Initialize array
vector<int> values = {1, 2, 3, 4, 5, 6, 7, 8};
for (int i = 0; i < values.size(); i++) {
    ft.modify(i, values[i]);
}

// Query sum in range [2, 5]
int l = 2, r = 5;
int range_sum = ft.query(r) - (l > 0 ? ft.query(l - 1) : 0);
// Returns 18 (3+4+5+6)

// Update: add 10 to position 3
ft.modify(3, 10);

// Query again
range_sum = ft.query(r) - (l > 0 ? ft.query(l - 1) : 0);
// Returns 28 (3+14+5+6)

// Count frequencies of elements
int MAX_VAL = 1000;
fenwick<int> freq(MAX_VAL);

// Process stream of values
vector<int> stream = {5, 3, 7, 3, 5, 1, 7, 9};
for (int val : stream) {
    freq.modify(val, 1);  // Increment frequency
}

// Count elements <= 5
int count = freq.query(5);  // Returns 5

// Count elements in range [3, 7]
count = freq.query(7) - freq.query(2);  // Returns 6

// Find k-th smallest (binary search)
auto find_kth = [&](int k) {
    int lo = 0, hi = MAX_VAL - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (freq.query(mid) < k) lo = mid + 1;
        else hi = mid;
    }
    return lo;
};

int third_smallest = find_kth(3);  // Find 3rd smallest element

Advanced Patterns

2D Fenwick Tree

template <typename T> class Fenwick2D {
    int n, m;
    vector<vector<T>> fenw;
    
public:
    Fenwick2D(int _n, int _m) : n(_n), m(_m) {
        fenw.assign(n, vector<T>(m));
    }
    
    void modify(int x, int y, T v) {
        for (int i = x; i < n; i |= (i + 1)) {
            for (int j = y; j < m; j |= (j + 1)) {
                fenw[i][j] += v;
            }
        }
    }
    
    T query(int x, int y) {
        T v{};
        for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
            for (int j = y; j >= 0; j = (j & (j + 1)) - 1) {
                v += fenw[i][j];
            }
        }
        return v;
    }
    
    // Query sum in rectangle (x1, y1) to (x2, y2)
    T query_range(int x1, int y1, int x2, int y2) {
        T result = query(x2, y2);
        if (x1 > 0) result -= query(x1 - 1, y2);
        if (y1 > 0) result -= query(x2, y1 - 1);
        if (x1 > 0 && y1 > 0) result += query(x1 - 1, y1 - 1);
        return result;
    }
};

Range Update, Point Query

Use difference array technique:

fenwick<int> diff(n);

// Add value to range [l, r]
auto range_update = [&](int l, int r, int val) {
    diff.modify(l, val);
    if (r + 1 < n) diff.modify(r + 1, -val);
};

// Get value at position i
auto point_query = [&](int i) {
    return diff.query(i);
};

// Example
range_update(2, 5, 10);  // Add 10 to [2, 5]
range_update(3, 7, 5);   // Add 5 to [3, 7]
int val = point_query(4); // Get value at position 4

Range Update, Range Query

Use two Fenwick trees:

fenwick<long long> B1(n), B2(n);

auto range_update = [&](int l, int r, int val) {
    B1.modify(l, val);
    B1.modify(r + 1, -val);
    B2.modify(l, val * (l - 1));
    B2.modify(r + 1, -val * r);
};

auto prefix_sum = [&](int i) {
    return B1.query(i) * i - B2.query(i);
};

auto range_query = [&](int l, int r) {
    return prefix_sum(r) - (l > 0 ? prefix_sum(l - 1) : 0);
};

Binary Search on Fenwick Tree

Find the k-th smallest element efficiently:

fenwick<int> ft(MAX_N);

// Find smallest index with prefix sum >= k
int find_kth(int k) {
    int pos = 0;
    int bit_mask = 1;
    while (bit_mask < MAX_N) bit_mask <<= 1;
    bit_mask >>= 1;
    
    while (bit_mask > 0) {
        if (pos + bit_mask < MAX_N) {
            if (ft.fenw[pos + bit_mask] < k) {
                k -= ft.fenw[pos + bit_mask];
                pos += bit_mask;
            }
        }
        bit_mask >>= 1;
    }
    return pos + 1;
}

Applications

Inversion Count

Count inversions in array in O(n log n)

Dynamic Median

Maintain median of dynamic dataset

Range Sum Queries

Efficient prefix and range sum calculations

Order Statistics

Find k-th smallest element dynamically

Fenwick vs Segment Tree

Feature	Fenwick Tree	Segment Tree
Space	O(n)	O(4n)
Implementation	Simpler	More complex
Point Update	O(log n)	O(log n)
Range Update	Requires tricks	Native support
Supported Operations	Must have inverse	Any associative op
Cache Performance	Better	Worse
Constant Factor	Lower	Higher

When to use Fenwick Tree:

Operations have inverses (addition/subtraction)
Memory is constrained
Need simpler, faster code
Dealing with prefix sums or frequency counting

When to use Segment Tree:

Need range updates with lazy propagation
Operations don’t have inverses (min, max, gcd)
Need to store additional information per node
Need binary search on tree

Practice Problems

Range Sum Query - Mutable (LeetCode 307)
Count of Smaller Numbers After Self (LeetCode 315)
Dynamic Range Sum Queries (CSES)
Salary Queries (CSES)
Inversion Count (SPOJ)

Graph Algorithms

Data Structures

Range Query

String Algorithms

Math & Number Theory

Numeric

Search Algorithms

Techniques

Geometry

Utilities

Overview

Implementation

Custom Node Structure

Basic Usage

Advanced Patterns

2D Fenwick Tree

Range Update, Point Query

Range Update, Range Query

Binary Search on Fenwick Tree

Applications

Inversion Count

Dynamic Median

Range Sum Queries

Order Statistics

Fenwick vs Segment Tree

Practice Problems

See Also

Build docs developers (and LLMs) love

Graph Algorithms

Data Structures

Range Query

String Algorithms

Math & Number Theory

Numeric

Search Algorithms

Techniques

Geometry

Utilities

​Overview

​Implementation

​Custom Node Structure

​Basic Usage

​Advanced Patterns

​2D Fenwick Tree

​Range Update, Point Query

​Range Update, Range Query

​Binary Search on Fenwick Tree

​Applications

Inversion Count

Dynamic Median

Range Sum Queries

Order Statistics

​Fenwick vs Segment Tree

​Practice Problems

​See Also

Build docs developers (and LLMs) love

Overview

Implementation

Custom Node Structure

Basic Usage

Advanced Patterns

2D Fenwick Tree

Range Update, Point Query

Range Update, Range Query

Binary Search on Fenwick Tree

Applications

Fenwick vs Segment Tree

Practice Problems

See Also