Data Structures and Algorithms in C (DSA)

📘 Chapter: Fenwick Tree / Binary Indexed Tree (BIT)

Building on the concepts of efficient range queries, we now introduce the Fenwick Tree, also known as a Binary Indexed Tree (BIT). Developed by Peter Fenwick in 1994, this data structure provides a concise and efficient way to handle two common operations on an array: getting the prefix sum (sum of elements up to an index) and updating individual elements, both in logarithmic time. While Segment Trees are more versatile for various range operations, BITs are often simpler to implement and have better constant factors for prefix sums and point updates.

💡 What is a Fenwick Tree (BIT)? The Power of Binary Representation

A Fenwick Tree is an array-based data structure that allows for efficient calculation of prefix sums and point updates. Its elegance lies in leveraging the binary representation of indices to determine which array elements affect which parts of the sum.

• It's essentially a tree structure embedded within a one-dimensional array.
• Each node in the BIT array stores the sum of a certain range of elements from the original array. The size of this range is determined by the lowest set bit (rightmost '1') in the index's binary representation.
• For an index `i`, `tree[i]` stores the sum of elements from `(i - (i & -i) + 1)` to `i` in the original array. The expression `(i & -i)` isolates the lowest set bit.

This clever indexing scheme ensures that both querying a prefix sum and updating an element involve traversing only O(log N) elements in the BIT array.

🔧 Core Operations on a Fenwick Tree

A Fenwick Tree primarily supports:

1. Update (Point Update)

To update an element `arr[idx]` by adding `val` to it (or setting it to a new value, by adding the difference), we need to update all BIT array elements that cover `arr[idx]`.

• Start from `idx + 1` (since BIT is 1-indexed, or handle 0-indexing carefully).
• Add `val` to `BIT[current_idx]`.
• Move to the next index that needs updating by adding `(current_idx & -current_idx)` to `current_idx`. This effectively moves to the parent node in the implicit tree structure.
• Repeat until `current_idx` exceeds the array size.

// Global array for Fenwick Tree (1-indexed)
int BIT[MAX_SIZE + 1];
int N; // Size of original array

// Adds 'val' to element at 'idx' (0-indexed in original array)
void update(int idx, int val) {
    idx = idx + 1; // Convert to 1-indexed
    while (idx <= N) {
        BIT[idx] += val;
        idx += (idx & -idx); // Move to next relevant index (parent)
    }
}
  

Time Complexity: O(log N) for each update.

2. Query (Prefix Sum)

To get the sum of elements from index 0 to `idx` (inclusive) in the original array, we query the BIT.

• Start from `idx + 1`.
• Add `BIT[current_idx]` to a running sum.
• Move to the previous index that contributes to the prefix sum by subtracting `(current_idx & -current_idx)` from `current_idx`. This effectively moves to a "parent" or "sibling" node in the implicit tree.
• Repeat until `current_idx` becomes 0.

// Gets sum of elements from 0 to 'idx' (0-indexed in original array)
int query(int idx) {
    idx = idx + 1; // Convert to 1-indexed
    int sum = 0;
    while (idx > 0) {
        sum += BIT[idx];
        idx -= (idx & -idx); // Move to previous relevant index
    }
    return sum;
}
  

Time Complexity: O(log N) for each query.

Range Sum Query (Derived)

While BITs inherently provide prefix sums, a range sum `sum(L, R)` (sum of elements from index L to R) can be easily derived using two prefix sum queries:
`sum(L, R) = query(R) - query(L-1)`

📊 Fenwick Tree Structure Visualization

🚀 Advantages and Disadvantages of Fenwick Trees

Advantages:

• Space Efficiency: Requires only O(N) space, exactly `N+1` elements for an array of size `N`. This is more compact than Segment Trees (typically 4N).
• Simpler Implementation: Generally easier and shorter to implement than Segment Trees for point updates and prefix/range sum queries.
• Fast Operations: Both point updates and prefix sum queries are O(log N).

Disadvantages:

• Limited Functionality: Primarily designed for prefix sums and point updates. It's less flexible than a Segment Tree for arbitrary range queries (e.g., range min/max, GCD) or range updates (without significant modifications).
• Only Associative Operations: The operation must be associative (like sum, product, XOR) for range queries to work correctly.

📌 Real-Life Example (UdaanPath)

Fenwick Trees, due to their efficiency for prefix sums and updates, can be valuable for specific data analytics and tracking features on a platform like UdaanPath:

• Cumulative Performance Tracking: For a series of tests or assignments, if you want to quickly query a student's total score up to a certain assignment, or the sum of points gained in a specific period. When a student's score for an assignment is updated, the BIT can reflect this change efficiently.
• Leaderboard Updates (Simple Cumulative Scores): If a leaderboard primarily ranks users by total score (cumulative sum of points) and points are added incrementally, a BIT can rapidly update a user's score and retrieve the total, helping maintain dynamic rankings without full recalculations.
• Real-time Analytics of Event Counts: For tracking events over a timeline, such as "number of video lectures completed by all users up to a certain date" or "total questions attempted by new users in their first N days". As new events occur, the BIT is updated, and cumulative counts are queried fast.
• Inventory Management (Simple Stock Updates): In a simplified scenario where you need to track the cumulative stock of items by ID (e.g., item ID 1 to 100), and items are added/removed. You can query the total quantity of items up to a certain ID range.

✅ Summary: Compact & Efficient for Sums

• A Fenwick Tree (Binary Indexed Tree / BIT) is an array-based data structure for efficient point updates and prefix sum queries on an array.
• It leverages the binary representation of indices to achieve O(log N) time complexity for both `update` and `query` operations.
• Range sum queries can be performed in O(log N) using two prefix sum queries.
• Compared to Segment Trees, BITs are more space-efficient (O(N)) and often simpler to implement for their specific range of capabilities.
• Its primary limitation is less flexibility for arbitrary range queries (e.g., min/max) and range updates compared to Segment Trees.

📤 Coming Next: Heap & Priority Queues (Min-Heap, Max-Heap)

Our journey through data structures continues with the powerful Heap & Priority Queues. We'll explore how these specialized tree-based structures efficiently manage elements based on their priority, enabling quick retrieval of the minimum or maximum element, which is crucial for algorithms like Dijkstra's and Prim's, and for managing task scheduling.