Fenwick Tree

The Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that provides efficient operations for prefix sum queries and updates in an array. It was proposed by Peter Fenwick in 1994.

Key Features

• Time Complexity: O(log n) for both update and prefix sum operations
• Space Complexity: O(n) where n is the size of the array
• Efficient: Offers better performance than segment trees for range sum queries when updates are frequent

Core Concepts

How It Works

The Fenwick Tree uses a binary representation to store cumulative sums. For an array of size n, it maintains an auxiliary array BIT of the same size where:

• BIT[i] stores the sum of elements from index i - (i & (-i)) + 1 to i
• The operation i & (-i) isolates the rightmost set bit in i

Example

Let's take an array arr = [1, 3, 5, 7, 9].

We build the BIT array like this:

Index:   1  2  3  4  5  6  7  8
BIT:     1  4  5  16 9  18  0  32

In this case:

• BIT[1] = arr[0] = 1
• BIT[2] = arr[0] + arr[1] = 1 + 3 = 4
• BIT[3] = arr[2] = 5
• BIT[4] = arr[0] + arr[1] + arr[2] + arr[3] = 1 + 3 + 5 + 7 = 16
• And so on.

Operations

Update Operation

To update the value at index i by adding delta:

1. Start from index i
2. Add delta to BIT[i]
3. Move to next index using the formula: i = i + (i & (-i))
4. Repeat until i <= size of BIT

function update(BIT, i, delta) {
    while (i <= BIT.length - 1) {
        BIT[i] += delta;
        i += (i & (-i));
    }
}

Prefix Sum Query Operation

To compute the prefix sum up to index i:

1. Start from index i
2. Add BIT[i] to result
3. Move to previous index using the formula: i = i - (i & (-i))
4. Repeat until i > 0

function prefixSum(BIT, i) {
    let sum = 0;
    while (i > 0) {
        sum += BIT[i];
        i -= (i & (-i));
    }
    return sum;
}

Usage Patterns

Range Sum Query with Updates

For problems where you need to support both range sum queries and point updates efficiently:

// Initialize Fenwick Tree with array
function initFenwickTree(arr) {
    const BIT = new Array(arr.length + 1).fill(0);
    for (let i = 1; i <= arr.length; i++) {
        update(BIT, i, arr[i - 1]);
    }
    return BIT;
}

// Get prefix sum up to index i
function getSum(BIT, i) {
    let sum = 0;
    while (i > 0) {
        sum += BIT[i];
        i -= (i & (-i));
    }
    return sum;
}

// Update value at index i by delta
function update(BIT, i, delta) {
    while (i <= BIT.length - 1) {
        BIT[i] += delta;
        i += (i & (-i));
    }
}

// Range sum from l to r
function rangeSum(BIT, l, r) {
    return getSum(BIT, r) - getSum(BIT, l - 1);
}

Time and Space Complexity Analysis

| Operation | Time Complexity | Space Complexity |

|------------------|---------------|----------------|

| Initialization | O(n log n) | O(n) |

| Update | O(log n) | O(1) |

| Prefix Sum Query | O(log n) | O(1) |

Common Mistakes to Avoid

1. Off-by-one errors: Be careful with array indexing. Fenwick Tree is typically 1-indexed internally but can be adapted for 0-based.

1. Incorrect bit manipulation: Ensure that i & (-i) correctly isolates the rightmost set bit.

1. Not handling edge cases: When dealing with updates, make sure to account for zero or negative delta values.

Real-world Applications

1. Range Sum Queries: Used in scenarios like calculating prefix sums in large datasets.
2. Dynamic Programming: Can be used to speed up certain DP transitions involving prefix sums.
3. Computational Geometry: For area queries in 2D space (when extended to 2D Fenwick Trees).

Variants

2D Fenwick Tree (Binary Indexed Tree)

In two dimensions, the structure can handle updates and queries over rectangular regions:

// 2D Fenwick Tree Implementation (Simplified)
function init2DFenwickTree(rows, cols) {
    const BIT = Array(rows + 1).fill().map(() => Array(cols + 1).fill(0));
    return BIT;
}

function update2D(BIT, x, y, delta) {
    for (let i = x; i <= BIT.length - 1; i += i & (-i)) {
        for (let j = y; j <= BIT[0].length - 1; j += j & (-j)) {
            BIT[i][j] += delta;
        }
    }
}

function query2D(BIT, x, y) {
    let sum = 0;
    for (let i = x; i > 0; i -= i & (-i)) {
        for (let j = y; j > 0; j -= j & (-j)) {
            sum += BIT[i][j];
        }
    }
    return sum;
}

Best Practices for Implementation

1. Proper initialization: Make sure to initialize the BIT array correctly.
2. Consistent indexing: Stick to either 0-based or 1-based indexing throughout the code.
3. Code clarity: Keep variable names descriptive and comments helpful for future maintainers.
4. Performance testing: Test with edge cases such as all zeros, single elements, and large arrays.

Example Use Case: Counting Inversions

Fenwick Tree can be used to count inversions in an array:

function countInversions(arr) {
    const BIT = new Array(arr.length + 1).fill(0);
    let invCount = 0;
    
    // Assuming elements are in range [1, n]
    for (let i = arr.length - 1; i >= 0; i--) {
        invCount += query(BIT, arr[i] - 1);
        update(BIT, arr[i], 1);
    }
    return invCount;
}

function query(BIT, i) {
    let sum = 0;
    while (i > 0) {
        sum += BIT[i];
        i -= (i & (-i));
    }
    return sum;
}

function update(BIT, i, delta) {
    while (i <= BIT.length - 1) {
        BIT[i] += delta;
        i += (i & (-i));
    }
}

Comparison with Segment Trees

| Feature | Fenwick Tree | Segment Tree |

|--------------------------|----------------------|-----------------------|

| Update time | O(log n) | O(log n) |

| Query time | O(log n) | O(log n) |

| Space complexity | O(n) | O(2n) |

| Memory access pattern | More cache-friendly | Less cache-friendly |

| Simpler to implement | Yes | More complex |

Fenwick Tree is generally preferred over Segment Trees when the operations are limited to prefix sum queries and updates, as it offers better memory efficiency and simpler implementation.