Home › DSA › Advanced Patterns

Implementation of Binary Indexed Tree

A Binary Indexed Tree is designed to efficiently compute prefix sums and handle updates in logarithmic time. It achieves this by storing cumulative information at specific indices, enabling quick retrieval and updates.

Structure of BIT

For an input array of size n, the BIT is typically represented as an array of size n + 1, with the 0-th index left unused for simplicity. The key idea is that each index in the BIT array represents a sum of elements from the input array, covering different ranges.

Tree Structure

The structure of a BIT can be visualized as a tree where each index is connected to its parent. The parent index is determined using the following formula:

In simpler terms, you can get the parent index by flipping the rightmost set bit in the binary representation of (i).

In the diagram below, we have shown the Binary Indexed Tree for array having 10 elements.

To help visualize the tree structure, let’s consider the indices and how they relate to their parent nodes.

Table: Index to Parent Mapping

Index	Binary Value	Flip Last Set Bit	Parent Index
1	0001	0000	0
2	0010	0000	0
3	0011	0010	2
4	0100	0000	0
5	0101	0100	4
6	0110	0100	4
7	0111	0110	6
8	1000	0000	0
9	1001	1000	8
10	1010	1000	8
11	1011	1010	10

Binary Value: The binary representation of the index.
Flip Last Set Bit: The result of flipping the rightmost set bit in the binary value.
Parent Index: The decimal value after flipping the last set bit, which gives the parent index.

This table helps visualize how each index in the BIT connects to its parent, forming a tree-like structure.

Understanding the Range of Nodes in a Binary Indexed Tree

Let's take the array [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3] and see how a Binary Indexed Tree (BIT) stores the range of sums at different nodes. Each node in the BIT represents a cumulative sum over a specific range of indices, determined by the binary representation of the node's index.

Example 1: Calculate Range for bit[2]

Binary Representation: 2 is 10 in binary.
Least Significant Set Bit: The least significant set bit is 2¹ (or 2).
Range Calculation: Using the formula i - (i & -i) to i-1, the range is 2 - 2 to 1, which gives 0 to 1.
Stored Sum: bit[2] will store the sum of the elements at indices 1 and 2, which are 3 + 2 = 5.

Example 2: Calculate Range for bit[4]

Binary Representation: 4 is 100 in binary.
Least Significant Set Bit: The least significant set bit is 2² (or 4).
Range Calculation: The range is 4 - 4 to 4-1, which gives 0 to 3.
Stored Sum: bit[4] will store the sum of elements at indices 1 through 4, which are 3 + 2 - 1 + 6 = 10.

Example 3: Calculate Range for bit[6]

Binary Representation: 6 is 110 in binary.
Least Significant Set Bit: The least significant set bit is 2¹ (or 2).
Range Calculation: The range is 6 - 2 to 5, which gives 4 to 5.
Stored Sum: bit[6] will store the sum of elements at indices 5 and 6, which are 5 + 4 = 9.

Calculating Prefix Sum for Range (0, 6) Using BIT

To find the sum of elements from index 0 to 6 using a Binary Indexed Tree (BIT), we combine the values stored in specific nodes of the BIT that cover this range.

Steps

Start at Node 7:
- Value: bit[7] stores the sum of the range (6, 6).
- Sum: sum = -3.
Move to Node 6:
- Value: bit[6] stores the sum of the range (4, 5).
- Sum: sum = sum + bit[6] = -3 + 9 = 6.
Move to Node 4:
- Value: bit[4] stores the sum of the range (0, 3).
- Sum: sum = sum + bit[4] = 6 + 10 = 16.

The final result is the sum of the elements from index 0 to 6, which is 16. This approach leverages the BIT structure to achieve the sum in logarithmic time complexity, as it only needs to visit a few nodes rather than summing directly from the array.

Constructing the Binary Indexed Tree

Constructing a Binary Indexed Tree (BIT) involves building the tree structure from a given array. The BIT will store cumulative sums that allow efficient range queries and updates.

Step-by-Step Algorithm

Initialize the BIT:
- Create an array bit[] of the same length as the input array, initialized to 0.
Populate the BIT:
- Iterate through each element in the input array.
- For each element, update the BIT using an update function.
Update Function:
- The update function adds the value of the current element to the appropriate indices in the BIT.
- We will look at update() function in the next part.

Code

java

class Solution {
    int[] bit;
    int n;

    // Constructor to initialize the BIT with the given array
    public void constructBIT(int[] arr) {
        n = arr.length;
        bit = new int[n + 1];  // BIT is 1-indexed, so we use n+1 size

        // Build the BIT by updating it with each element of the array
        for (int i = 0; i < n; i++) {
            update(i, arr[i]);
        }
    }
}

Updating the Binary Indexed Tree

The update() function is essential in maintaining the Binary Indexed Tree (BIT). When an element in the original array is modified, we need to update the BIT to reflect this change efficiently. This function ensures that the BIT remains consistent, allowing for quick prefix sum queries.

Step-by-Step Algorithm

Identify the Starting Index:
- Convert the zero-based index to one-based by adding 1.
Update the BIT at the Current Index:
- Add the value to bit[index].
Move to the Next Node Using index += (index & -index):
- The formula index += (index & -index) moves the index to the next node in the BIT that needs to be updated.
- How Does This Work?:
  - The expression (index & -index) isolates the rightmost set bit in the binary representation of index.
  - This represents the smallest power of 2 that divides index, corresponding to the size of the range that this node covers.
  - When you add this value to the current index, it moves you to the next node that covers a larger range.
Repeat Until the End of the BIT:
- Continue updating the nodes until the index exceeds the size of the BIT. This ensures that all relevant nodes reflecting the range affected by the original index are updated.

Example: Why Does index += (index & -index) Work?

Index 5 (Binary: 101):
- (index & -index) gives 1 (binary 001).
- Adding this moves you from 5 to 6 (binary 110).
- Node 5 covers just index 5, while node 6 covers indices 5 to 6 (1-based).
- The jump ensures that the BIT efficiently updates nodes that affect overlapping ranges.
Index 6 (Binary: 110):
- (index & -index) gives 2 (binary 010).
- Adding this moves you from 6 to 8 (binary 1000).
- Node 6 covers indices 5 and 6, while node 8 covers indices 1 to 8 (1-based).

This method of moving ensures that only the necessary nodes are updated, keeping the BIT efficient.

Let's understand the below node updating examples with a diagram.

Example: Update Value at Node 3 to 1

Code

java

class Solution {
    int[] bit;
    int n;

    // Function to update the BIT with the difference at a specific index
    private void update(int index, int difference) {
        index++;  // Convert to 1-based index for the BIT

        // Update the BIT by adding 'difference' to the appropriate indices
        while (index <= n) {
            bit[index] += difference;  // Add the difference to the current node
            index += index & -index;  // Move to the next node to update
        }
    }
}

Complexity Analysis

Time Complexity

Construction: Building the BIT takes time. For each element in the array, the update() function is called, which runs in time.
Update: Updating a single element in the BIT takes time. The number of operations depends on how many times you can move to the next node, which is logarithmic relative to the array size.

Space Complexity

Construction: The BIT uses space. The space required is proportional to the size of the input array, with an additional space for the BIT array itself.
Update: , as we don't use any extra space for update operation.

Implementing the getSum() Function in BIT

The getSum() function in a Binary Indexed Tree (BIT) calculates the prefix sum from the start of the array up to a given index. This operation is efficient and crucial for range queries.

Step-by-Step Algorithm

Initialize the Sum:
- Start with sum = 0.
Adjust Index for 1-Based BIT:
- Convert the zero-based index to one-based by incrementing it with index++.
Iterate Over the BIT Using a While Loop:
- Inside the loop:
  - Add Current Node's Value: Add the value at bit[index] to sum.
  - Move to Parent Node: Update the index using index -= (index & -index). This moves to the parent node, which represents a range covering fewer elements.
- Repeat until index becomes 0.
Return the Result:
- Return the accumulated sum, which now contains the prefix sum up to the original index.

Code

java

class Solution {
    int[] bit;
    int n;

    // Function to get the prefix sum up to a specific index
    public int getSum(int index) {
        int sum = 0;
        index++;  // Convert to 1-based index for the BIT

        // Traverse the BIT, summing the values until we reach the root
        while (index > 0) {
            sum += bit[index];  // Add the value at the current node
            index -= index & -index;  // Move to the parent node
        }

        return sum;  // Return the final computed sum
    }
}

Complexity Analysis

Time Complexity

Time Complexity: The getSum() function runs in time. This is because, in the worst case, the while loop will execute times, moving from the given index to the root of the Binary Indexed Tree.

Space Complexity:

Space Complexity: The space complexity is since the function only uses a constant amount of extra space (sum variable) and does not depend on the size of the input array or BIT.

Example Code

java

class Solution {
    int[] bit;
    int n;

    // Constructor to initialize the BIT with the given array
    public Solution(int[] arr) {
        n = arr.length;
        bit = new int[n + 1];  // BIT is 1-indexed, so we use n+1 size

        // Build the BIT by updating it with each element of the array
        for (int i = 0; i < n; i++) {
            update(i, arr[i]);
        }
    }

    // Function to update the BIT with the value at a specific index
    private void update(int index, int value) {
        index++;  // Convert to 1-based index for the BIT

        // Update the BIT by adding 'value' to the appropriate indices
        while (index <= n) {
            bit[index] += value;  // Add the value to the current node
            index += index & -index;  // Move to the next node to update
        }
    }

    // Function to get the prefix sum up to a specific index
    public int getSum(int index) {
        int sum = 0;
        index++;  // Convert to 1-based index for the BIT

        // Traverse the BIT, summing the values until we reach the root
        while (index > 0) {
            sum += bit[index];  // Add the value at the current node
            index -= index & -index;  // Move to the parent node
        }

        return sum;  // Return the final computed sum
    }

    // Main method to demonstrate the functionality
    public static void main(String[] args) {
        int[] arr = {3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3};  // Example array
        Solution solution = new Solution(arr);

        // Get sum from index 0 to 10
        int sumBeforeUpdate = solution.getSum(10);
        System.out.println("Sum from 0 to 10 before update: " + sumBeforeUpdate);

        // Update element at index 3 (change value from -1 to 1)
        solution.update(3, 2);  // 2 is the difference (new value 1 - old value -1)

        // Recalculate the sum from index 0 to 10 after the update
        int sumAfterUpdate = solution.getSum(10);
        System.out.println("Sum from 0 to 10 after update: " + sumAfterUpdate);
    }
}

Now, let's start solving the problems on the Binary Indexed Tree pattern.

🤖 Don't fully get this? Learn it with Claude

Stuck on Implementation of Binary Indexed Tree? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Implementation of Binary Indexed Tree** (DSA) and want to truly understand it. Explain Implementation of Binary Indexed Tree from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Implementation of Binary Indexed Tree** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Implementation of Binary Indexed Tree** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Implementation of Binary Indexed Tree** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Introduction to Binary Indexed Tre Coding Patterns A Cheat Sheet →