Fenwick Tree (Binary Indexed Tree)

Prefix sum queries, range sum updates, and advanced applications

Learn about the Fenwick Tree, a space-efficient data structure for prefix sum queries and range updates.

Fenwick Tree Fundamentals

What is a Fenwick Tree?

A Fenwick Tree (also called Binary Indexed Tree) is a data structure that efficiently supports prefix sum queries and point updates. It's more space-efficient than a Segment Tree for prefix sum operations.

Basic Structure

class FenwickTree {
private:
    vector<int> tree;
    int n;
    
public:
    FenwickTree(int size) {
        n = size;
        tree.resize(n + 1, 0);
    }
    
    // Get the least significant bit
    int lsb(int x) {
        return x & (-x);
    }
    
    // Update value at index idx
    void update(int idx, int delta) {
        idx++; // 1-indexed
        while (idx <= n) {
            tree[idx] += delta;
            idx += lsb(idx);
        }
    }
    
    // Query prefix sum from 1 to idx
    int query(int idx) {
        idx++; // 1-indexed
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= lsb(idx);
        }
        return sum;
    }
    
    // Query range sum from l to r
    int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
};

Prefix Sum Queries

Basic Prefix Sum

// Get sum of elements from index 0 to idx
int prefixSum(int idx) {
    idx++; // Convert to 1-indexed
    int sum = 0;
    while (idx > 0) {
        sum += tree[idx];
        idx -= lsb(idx);
    }
    return sum;
}

Range Sum Query

// Get sum of elements from index l to r
int rangeSum(int l, int r) {
    return prefixSum(r) - prefixSum(l - 1);
}

Point Update

// Add delta to element at index idx
void pointUpdate(int idx, int delta) {
    idx++; // Convert to 1-indexed
    while (idx <= n) {
        tree[idx] += delta;
        idx += lsb(idx);
    }
}

Range Sum Updates

Range Update with Point Query

class RangeUpdateFenwickTree {
private:
    FenwickTree tree1, tree2;
    int n;
    
public:
    RangeUpdateFenwickTree(int size) : tree1(size), tree2(size), n(size) {}
    
    // Update range [l, r] by adding val
    void rangeUpdate(int l, int r, int val) {
        tree1.update(l, val);
        tree1.update(r + 1, -val);
        tree2.update(l, val * l);
        tree2.update(r + 1, -val * (r + 1));
    }
    
    // Get value at index idx
    int pointQuery(int idx) {
        return tree1.query(idx) * (idx + 1) - tree2.query(idx);
    }
    
    // Get sum from 0 to idx
    int prefixSum(int idx) {
        return tree1.query(idx) * (idx + 1) - tree2.query(idx);
    }
    
    // Get range sum from l to r
    int rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
};

Range Update with Range Query

class RangeUpdateRangeQueryFenwickTree {
private:
    FenwickTree tree1, tree2;
    int n;
    
public:
    RangeUpdateRangeQueryFenwickTree(int size) : tree1(size), tree2(size), n(size) {}
    
    // Update range [l, r] by adding val
    void rangeUpdate(int l, int r, int val) {
        tree1.update(l, val);
        tree1.update(r + 1, -val);
        tree2.update(l, val * l);
        tree2.update(r + 1, -val * (r + 1));
    }
    
    // Get sum from 0 to idx
    int prefixSum(int idx) {
        return tree1.query(idx) * (idx + 1) - tree2.query(idx);
    }
    
    // Get range sum from l to r
    int rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
};

Inversion Count

Count Inversions in Array

// Count number of inversions in array
int countInversions(vector<int>& arr) {
    int n = arr.size();
    
    // Coordinate compression
    vector<int> temp = arr;
    sort(temp.begin(), temp.end());
    
    for (int i = 0; i < n; i++) {
        arr[i] = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin() + 1;
    }
    
    // Count inversions using Fenwick Tree
    FenwickTree ft(n);
    int inversions = 0;
    
    for (int i = n - 1; i >= 0; i--) {
        inversions += ft.query(arr[i] - 1);
        ft.update(arr[i], 1);
    }
    
    return inversions;
}

Count Inversions in 2D

// Count inversions in 2D array
int countInversions2D(vector<pair<int, int>>& points) {
    int n = points.size();
    
    // Sort by x-coordinate
    sort(points.begin(), points.end());
    
    // Coordinate compression for y-coordinates
    vector<int> yCoords;
    for (auto& p : points) {
        yCoords.push_back(p.second);
    }
    sort(yCoords.begin(), yCoords.end());
    
    for (auto& p : points) {
        p.second = lower_bound(yCoords.begin(), yCoords.end(), p.second) - yCoords.begin() + 1;
    }
    
    // Count inversions
    FenwickTree ft(n);
    int inversions = 0;
    
    for (int i = n - 1; i >= 0; i--) {
        inversions += ft.query(points[i].second - 1);
        ft.update(points[i].second, 1);
    }
    
    return inversions;
}

2D Fenwick Tree

2D Range Sum Query

class FenwickTree2D {
private:
    vector<vector<int>> tree;
    int n, m;
    
public:
    FenwickTree2D(int rows, int cols) {
        n = rows;
        m = cols;
        tree.resize(n + 1, vector<int>(m + 1, 0));
    }
    
    // Update value at (row, col)
    void update(int row, int col, int delta) {
        row++; col++; // 1-indexed
        for (int i = row; i <= n; i += lsb(i)) {
            for (int j = col; j <= m; j += lsb(j)) {
                tree[i][j] += delta;
            }
        }
    }
    
    // Query sum from (1,1) to (row, col)
    int query(int row, int col) {
        row++; col++; // 1-indexed
        int sum = 0;
        for (int i = row; i > 0; i -= lsb(i)) {
            for (int j = col; j > 0; j -= lsb(j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
    
    // Query sum in rectangle from (r1, c1) to (r2, c2)
    int rangeQuery(int r1, int c1, int r2, int c2) {
        return query(r2, c2) - query(r1 - 1, c2) - query(r2, c1 - 1) + query(r1 - 1, c1 - 1);
    }
    
private:
    int lsb(int x) {
        return x & (-x);
    }
};

Advanced Applications

Kth Smallest Element

// Find kth smallest element in array
int kthSmallest(vector<int>& arr, int k) {
    int n = arr.size();
    
    // Coordinate compression
    vector<int> temp = arr;
    sort(temp.begin(), temp.end());
    
    for (int i = 0; i < n; i++) {
        arr[i] = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin() + 1;
    }
    
    // Binary search for kth smallest
    FenwickTree ft(n);
    int left = 1, right = n;
    
    while (left < right) {
        int mid = (left + right) / 2;
        int count = ft.query(mid);
        
        if (count < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return temp[left - 1];
}

Range Sum with Updates

class RangeSumFenwickTree {
private:
    FenwickTree tree;
    vector<int> arr;
    int n;
    
public:
    RangeSumFenwickTree(vector<int>& input) : tree(input.size()), arr(input), n(input.size()) {
        for (int i = 0; i < n; i++) {
            tree.update(i, arr[i]);
        }
    }
    
    // Update value at index idx
    void update(int idx, int newVal) {
        int delta = newVal - arr[idx];
        arr[idx] = newVal;
        tree.update(idx, delta);
    }
    
    // Get sum from index l to r
    int rangeSum(int l, int r) {
        return tree.rangeQuery(l, r);
    }
    
    // Get value at index idx
    int get(int idx) {
        return arr[idx];
    }
};

Frequency Array Operations

class FrequencyFenwickTree {
private:
    FenwickTree tree;
    int maxVal;
    
public:
    FrequencyFenwickTree(int maxValue) : tree(maxValue), maxVal(maxValue) {}
    
    // Add value to frequency array
    void add(int val) {
        tree.update(val, 1);
    }
    
    // Remove value from frequency array
    void remove(int val) {
        tree.update(val, -1);
    }
    
    // Get frequency of value
    int getFrequency(int val) {
        return tree.rangeQuery(val, val);
    }
    
    // Get count of values <= val
    int getCountLessEqual(int val) {
        return tree.query(val);
    }
    
    // Get count of values < val
    int getCountLess(int val) {
        return tree.query(val - 1);
    }
    
    // Get count of values > val
    int getCountGreater(int val) {
        return tree.query(maxVal) - tree.query(val);
    }
};

Performance Analysis

Time Complexity

• Update: O(log n)
• Query: O(log n)
• Range Update: O(log n)
• Range Query: O(log n)
• Build: O(n log n)

Space Complexity

• 1D Fenwick Tree: O(n)
• 2D Fenwick Tree: O(n × m)
• Range Update Tree: O(n)

Advantages over Segment Tree

• Space efficient: O(n) vs O(4n)
• Simple implementation: Less code
• Cache friendly: Better memory access pattern
• Fast for prefix queries: Optimized for prefix operations

Common Patterns

1. Prefix sum queries with point updates
2. Range sum queries with point updates
3. Range updates with point queries
4. Inversion counting in arrays
5. Frequency array operations

Applications

• Range sum queries: Efficient prefix sum operations
• Inversion counting: Count inversions in arrays
• 2D range queries: Matrix range operations
• Frequency problems: Count frequencies efficiently
• Competitive programming: Fast range operations

When to Use Fenwick Tree

• Prefix sum queries are frequent
• Point updates are common
• Space is limited compared to Segment Tree
• Simple implementation is preferred
• Range queries are less frequent than prefix queries