Fenwick Tree (Binary Indexed Tree)

The Fenwick Tree, also known as Binary Indexed Tree (BIT), is a data structure used to efficiently perform range queries and point updates on arrays. It is especially useful for problems that require frequent updates to array elements and range queries over the array, such as finding the sum of array elements in a given range.

The Fenwick Tree is an improvement over the naive approach of computing prefix sums or prefix products over the array, which takes O(n) time complexity for both updates and range queries. The Fenwick Tree can perform both operations in O(log n) time complexity, making it a popular choice for solving various competitive programming problems and algorithmic challenges.

Brief History and Development

The Fenwick Tree was first introduced by Peter Fenwick in 1994 as a solution to the problem of efficiently computing prefix sums for wavelet compression. It was later rediscovered by M. Binary Indexed Trees were also independently invented by K. J. Supowit in 1974 for the purpose of fast data compression.

Since then, the Fenwick Tree has been widely adopted in the competitive programming community and has found applications in various fields such as computer science, engineering, and finance.

Key Concepts and Principles

The Fenwick Tree is based on the principle of cumulative frequency, where each node in the tree stores the sum of a certain range of elements in the array. The nodes are organized in a binary tree structure, where each node represents a range of array elements.

To compute the sum of a range [1, i] in the original array, we start by traversing the binary tree from i to the root, adding the value of each node encountered to the final result. To update an element in the array, we simply update the corresponding node in the tree and all its ancestors.

The key concept behind the Fenwick Tree is the use of binary representation to efficiently compute the range sum and perform updates. Specifically, each node in the tree is responsible for storing the sum of a range of elements, where the range is determined by the binary representation of its index.

For example, the sum of elements [1, 4] in the array is stored in node 4, since 4 in binary is 100, and the range of elements [1, 4] covers the first 4 elements in the array.

Pseudocode and Implementation Details

The Fenwick Tree can be implemented using an array of size n+1, where n is the length of the original array. The extra element is used to simplify node indexing, since node i in the tree corresponds to index i in the array.

def update(bit, i, val):
    # Add val to the i-th element in array
    n = len(bit)
    while i <= n:
        bit[i] += val
        i += i & -i

def query(bit, i):
    # Compute the sum of elements [1, i] in array
    res = 0
    while i > 0:
        res += bit[i]
        i -= i & -i
    return res

The update function takes a Binary Indexed Tree bit, an index i, and a value val, and updates the Fenwick Tree by adding val to the i-th element in the array. The while loop iteratively updates the tree by adding val to the current node, then moves to its parent node by adding the least significant bit of i.

The query function takes a Binary Indexed Tree bit and an index i, and computes the sum of elements [1, i] in the original array. The while loop iteratively traverses the tree from i to the root, adding the value of each node encountered to the final result, then moves to the next node by removing the least significant bit of i.

Examples and Use Cases

Example 1: Computing Prefix Sum

Suppose we have an array of integers a = [1, 2, 3, 4, 5, 6, 7, 8], and we want to compute the prefix sums of the array. The prefix sum of an array is defined as the sum of elements [1, i] for each index i in the array.

We can use the Fenwick Tree to compute the prefix sums in O(n log n) time complexity, where n is the length of the original array.

def build_bit(a):
    # Build the Binary Indexed Tree from array a
    n = len(a)
    bit = [0] * (n+1)
    for i in range(1, n+1):
        update(bit, i, a[i-1])
    return bit

a = [1, 2, 3, 4, 5, 6, 7, 8]
bit = build_bit(a)

# Computing prefix sum of array a
for i in range(1, len(a)+1):
    print(query(bit, i))

The output of the above code is:

1
3
6
10
15
21
28
36

Example 2: Finding the Sum of Elements in a Given Range

Suppose we have an array of integers a = [1, 2, 3, 4, 5, 6, 7, 8], and we want to find the sum of elements in the range [3, 6] of the array.

We can use the Fenwick Tree to answer this query in O(log n) time complexity, where n is the length of the original array.

a = [1, 2, 3, 4, 5, 6, 7, 8]
bit = build_bit(a)

# Finding sum of elements [3, 6] in array a
print(query(bit, 6) - query(bit, 2))

The output of the above code is:

18

Advantages and Disadvantages

Advantages

• The Fenwick Tree has a small memory footprint and can be implemented using a one-dimensional array, making it efficient in terms of both space and time complexity.
• The Fenwick Tree supports both range queries and point updates in O(log n) time complexity, making it useful for solving various algorithmic challenges and problems that require frequent updates to array elements and range queries over the array.

Disadvantages

• The Fenwick Tree can only be used for operations that are associative and have an inverse, such as addition and multiplication. It cannot be used for non-associative operations such as finding the maximum or minimum element in a range.
• The Fenwick Tree has limited applicability in certain fields such as natural language processing and image processing, where the operations on the data are not associative.

Related Algorithms or Variations

The Fenwick Tree is related to other data structures such as Segment Tree and Binary Search Tree.

The Segment Tree is a similar data structure that also supports range queries and point updates over an array. The main difference between the Segment Tree and the Fenwick Tree is that the Segment Tree is a tree-based data structure, whereas the Fenwick Tree is based on the binary representation of indices.

The Binary Search Tree is another data structure that supports range queries and point updates over an array. However, the Binary Search Tree has a worst-case time complexity of O(n) for both operations, whereas the Fenwick Tree has a worst-case time complexity of O(log n).

Conclusion

The Fenwick Tree, also known as Binary Indexed Tree, is a data structure used to efficiently perform range queries and point updates on arrays. It is based on the principle of cumulative frequency and uses the binary representation of indices to efficiently compute the range sum and perform updates. The Fenwick Tree has a small memory footprint and can be implemented using a one-dimensional array, making it efficient in terms of both space and time complexity. It supports both range queries and point updates in O(log n) time complexity, making it useful for solving various algorithmic challenges and problems. However, it can only be used for operations that are associative and have an inverse, and has limited applicability in certain fields such as natural language processing and image processing.