Fenwick Tree (Binary Indexed Tree) Implementation in Python
A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that provides efficient methods for prefix sum queries and updates on an array of numbers. It is particularly useful when the array is frequently updated and queried for prefix sums, as both operations can be performed in O(log n) time.
Program Structure
The Fenwick Tree implementation in Python consists of the following components:
1. FenwickTree Class
This class encapsulates the functionality of the Fenwick Tree. It includes the following methods:
__init__(self, n): Initializes the Fenwick Tree with a given sizen.update(self, index, delta): Updates the value at a given index by addingdeltato it.prefix_sum(self, index): Returns the prefix sum from the start of the array to the given index.range_sum(self, left, right): Returns the sum of elements within a specified range [left,right].
Python Code Implementation
class FenwickTree:
def __init__(self, n):
"""
Initialize a Fenwick Tree for an array of size n.
:param n: Size of the array.
"""
self.size = n
self.tree = [0] * (n + 1) # Fenwick Tree array
def update(self, index, delta):
"""
Update the value at index by adding delta.
:param index: The index to update (1-based index).
:param delta: The value to add to the index.
"""
while index <= self.size:
self.tree[index] += delta
index += index & -index # Move to the next index
def prefix_sum(self, index):
"""
Compute the prefix sum from the start of the array to the given index.
:param index: The index up to which to compute the prefix sum (1-based index).
:return: The prefix sum.
"""
result = 0
while index > 0:
result += self.tree[index]
index -= index & -index # Move to the parent index
return result
def range_sum(self, left, right):
"""
Compute the sum of elements within the range [left, right].
:param left: The starting index of the range (1-based index).
:param right: The ending index of the range (1-based index).
:return: The sum of elements within the range.
"""
return self.prefix_sum(right) - self.prefix_sum(left - 1)
Explanation
The Fenwick Tree is a data structure designed to efficiently calculate prefix sums and update elements. Here’s how the implementation works:
1. FenwickTree Class
The FenwickTree class manages the operations of the Fenwick Tree.
Initialization
The __init__ method initializes the tree with a given size n. The tree is represented as an array of size n + 1 to handle 1-based indexing easily.
Update
The update method adds a value delta to the element at the specified index. It propagates the change to the necessary nodes in the tree by iterating through the tree with the formula index += index & -index, which moves to the next relevant node in the tree.
Prefix Sum
The prefix_sum method calculates the sum of elements from the start of the array to the given index. It iterates through the tree using index -= index & -index to accumulate the relevant sums.
Range Sum
The range_sum method calculates the sum of elements within a specific range [left, right] by using the difference of two prefix sums: prefix_sum(right) and prefix_sum(left - 1).
Usage Example
# Example usage of the FenwickTree
# Initialize a Fenwick Tree for an array of size 10
fenwick_tree = FenwickTree(10)
# Update elements at specific indices
fenwick_tree.update(1, 5) # Add 5 at index 1
fenwick_tree.update(2, 3) # Add 3 at index 2
fenwick_tree.update(3, 7) # Add 7 at index 3
# Get the prefix sum up to index 3
print("Prefix sum up to index 3:", fenwick_tree.prefix_sum(3))
# Output: Prefix sum up to index 3: 15
# Get the sum of elements in the range [2, 3]
print("Range sum from index 2 to 3:", fenwick_tree.range_sum(2, 3))
# Output: Range sum from index 2 to 3: 10
This example demonstrates how to create a Fenwick Tree, update elements in the tree, and query both prefix sums and range sums.
