Implementation of Binary Indexed Tree

Grokking Advanced Coding Patterns for Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Implementation of Binary Indexed Tree

Table of Contents

Contents are not accessible

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:

$\text{parent}(i) = i - (i \& -i)$

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 21 (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 22 (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 21 (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

Python3

. . . .

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

Python3

. . . .

Complexity Analysis

Time Complexity

Construction: Building the BIT takes $O(n log n)$ time. For each element in the array, the update() function is called, which runs in $O(log n)$ time.
Update: Updating a single element in the BIT takes $O(log n)$ 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 $O(n)$ space. The space required is proportional to the size of the input array, with an additional $O(n)$ space for the BIT array itself.
Update: $O(1)$ , 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

Python3

. . . .

Complexity Analysis

Time Complexity

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

Space Complexity:

Space Complexity: The space complexity is $O(1)$ 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

Python3

. . . .

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

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible