Fenwick Tree

What is a Fenwick Tree?

A Fenwick Tree (also called Binary Indexed Tree or BIT) is a data structure that efficiently supports:

• Point updates: Add a value to an element
• Prefix queries: Query sum from index 0 to i

Both operations in O(log n) time with O(n) space.

Key Insight: Binary Representation

The magic of Fenwick Tree is using the binary representation of indices:

Index:    1    2    3    4    5    6    7    8
Binary:  001  010  011  100  101  110  111 1000

BIT[1] covers: [1]
BIT[2] covers: [1,2]
BIT[3] covers: [3]
BIT[4] covers: [1,2,3,4]
BIT[5] covers: [5]
BIT[6] covers: [5,6]
BIT[7] covers: [7]
BIT[8] covers: [1,2,3,4,5,6,7,8]

Implementation

public class FenwickTree {
    private int[] tree;
    private int n;
    
    public FenwickTree(int size) {
        n = size;
        tree = new int[n + 1]; // 1-indexed
    }
    
    public FenwickTree(int[] nums) {
        n = nums.length;
        tree = new int[n + 1];
        for (int i = 0; i < n; i++) {
            update(i, nums[i]);
        }
    }
    
    // Add val to index i (0-indexed)
    public void update(int i, int val) {
        i++; // Convert to 1-indexed
        while (i <= n) {
            tree[i] += val;
            i += i & (-i); // Add lowest set bit
        }
    }
    
    // Query prefix sum from 0 to i (0-indexed)
    public int query(int i) {
        i++; // Convert to 1-indexed
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & (-i); // Remove lowest set bit
        }
        return sum;
    }
    
    // Query range sum from left to right (0-indexed)
    public int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }
}

The XOR Trick

i & (-i) gives the lowest set bit:

• If i = 6 (110), then -i = ...010, so i & (-i) = 2 (010)
• This tells us how far the current node reaches

Time & Space Complexity

• Build (from array): O(n log n) or O(n) with optimized build
• Update: O(log n)
• Query: O(log n)
• Space: O(n)

2D Fenwick Tree

For 2D range queries and updates:

public class FenwickTree2D {
    private int[][] tree;
    private int rows, cols;
    
    public FenwickTree2D(int m, int n) {
        rows = m;
        cols = n;
        tree = new int[m + 1][n + 1];
    }
    
    public void update(int row, int col, int val) {
        for (int i = row + 1; i <= rows; i += i & (-i)) {
            for (int j = col + 1; j <= cols; j += j & (-j)) {
                tree[i][j] += val;
            }
        }
    }
    
    public int query(int row, int col) {
        int sum = 0;
        for (int i = row + 1; i > 0; i -= i & (-i)) {
            for (int j = col + 1; j > 0; j -= j & (-j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
    
    public 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);
    }
}

Counting Inversions with Fenwick Tree

public int countInversions(int[] nums) {
    // Coordinate compression
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    Map<Integer, Integer> map = new HashMap<>();
    int rank = 1;
    for (int num : sorted) {
        map.putIfAbsent(num, rank++);
    }
    
    FenwickTree ft = new FenwickTree(rank);
    int inversions = 0;
    
    // Process from right to left
    for (int i = nums.length - 1; i >= 0; i--) {
        int r = map.get(nums[i]);
        inversions += ft.query(r - 1); // Count smaller elements to the right
        ft.update(r, 1);
    }
    
    return inversions;
}

Dynamic Frequency Counting

// Count numbers in range [left, right] that have been added so far
class FrequencyCounter {
    private FenwickTree ft;
    private int offset;
    
    public FrequencyCounter(int maxValue) {
        offset = maxValue; // Handle negative numbers
        ft = new FenwickTree(2 * maxValue + 1);
    }
    
    public void add(int num) {
        ft.update(num + offset, 1);
    }
    
    public void remove(int num) {
        ft.update(num + offset, -1);
    }
    
    public int countInRange(int left, int right) {
        return ft.rangeQuery(left + offset, right + offset);
    }
}