Two Dimensional Binary Indexed Tree or Fenwick Tree

Table of Contents#

1. Basics of One - Dimensional Binary Indexed Tree
2. Understanding Two - Dimensional Binary Indexed Tree
3. Construction of Two - Dimensional Binary Indexed Tree
4. Point Update in Two - Dimensional Binary Indexed Tree
5. Range Query in Two - Dimensional Binary Indexed Tree
6. Example Usage
7. Best Practices and Common Pitfalls
8. Conclusion
9. References

1. Basics of One - Dimensional Binary Indexed Tree#

Before diving into the two - dimensional version, let's quickly recap the one - dimensional Binary Indexed Tree.

A one - dimensional BIT is an array bit[] of size n + 1 (where n is the size of the original array). The key idea behind the BIT is based on the binary representation of indices. Each element bit[i] stores the sum of a certain range of elements from the original array.

The main operations in a one - dimensional BIT are:

• Point Update: Given an index i and a value val, we update the original array at index i and also update the relevant nodes in the BIT in $O(\log n)$ time.
• Range Query: Given two indices l and r, we can find the sum of elements in the range [l, r] in $O(\log n)$ time.

Here is a simple Python code for a one - dimensional BIT:

class BIT:
    def __init__(self, n):
        self.bit = [0] * (n + 1)
        self.n = n
 
    def update(self, idx, val):
        while idx <= self.n:
            self.bit[idx] += val
            idx += idx & -idx
 
    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & -idx
        return res
 
    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)
 
 

2. Understanding Two - Dimensional Binary Indexed Tree#

A two - dimensional Binary Indexed Tree is an extension of the one - dimensional BIT to handle two - dimensional arrays. Instead of a single array, we have a two - dimensional array bit[][] of size (n + 1) x (m + 1) (where n and m are the dimensions of the original two - dimensional array).

The key concept remains the same as the one - dimensional BIT, but now we have to consider both the row and column indices. Each element bit[i][j] stores the sum of a rectangular region in the original two - dimensional array.

3. Construction of Two - Dimensional Binary Indexed Tree#

To construct a two - dimensional BIT, we first initialize the bit array with all zeros. Then, for each element arr[i][j] in the original two - dimensional array, we perform a point update operation on the BIT.

Here is the Python code for constructing a two - dimensional BIT:

class BIT2D:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.bit = [[0] * (m + 1) for _ in range(n + 1)]
 
    def update(self, x, y, val):
        i = x + 1
        while i <= self.n:
            j = y + 1
            while j <= self.m:
                self.bit[i][j] += val
                j += j & -j
            i += i & -i
 
    def query(self, x, y):
        res = 0
        i = x + 1
        while i > 0:
            j = y + 1
            while j > 0:
                res += self.bit[i][j]
                j -= j & -j
            i -= i & -i
        return res
 
    def range_query(self, x1, y1, x2, y2):
        return self.query(x2, y2) - self.query(x1 - 1, y2) - self.query(x2, y1 - 1) + self.query(x1 - 1, y1 - 1)
 
 

4. Point Update in Two - Dimensional Binary Indexed Tree#

To perform a point update at position (x, y) with value val in the original two - dimensional array, we need to update all the relevant nodes in the BIT.

We start from the node bit[x + 1][y + 1] (since the BIT is 1 - indexed) and then update all the nodes in the BIT that depend on this node. The update operation takes $O(\log n\times\log m)$ time, where n and m are the dimensions of the original two - dimensional array.

5. Range Query in Two - Dimensional Binary Indexed Tree#

To perform a range query for the rectangular region defined by (x1, y1) and (x2, y2) (where (x1, y1) is the top - left corner and (x2, y2) is the bottom - right corner), we use the principle of inclusion - exclusion.

The sum of the rectangular region is given by: [S = \text{query}(x_2,y_2)-\text{query}(x_1 - 1,y_2)-\text{query}(x_2,y_1 - 1)+\text{query}(x_1 - 1,y_1 - 1)]

The range query operation also takes $O(\log n\times\log m)$ time.

6. Example Usage#

Let's consider an example where we have a 3x3 two - dimensional array and we want to perform point updates and range queries.

# Initialize the BIT
n = 3
m = 3
bit = BIT2D(n, m)
 
# Original array
arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
 
# Construct the BIT
for i in range(n):
    for j in range(m):
        bit.update(i, j, arr[i][j])
 
# Perform a range query
x1, y1, x2, y2 = 0, 0, 1, 1
print(bit.range_query(x1, y1, x2, y2))
 
# Perform a point update
bit.update(0, 0, 10)
 
# Perform another range query
print(bit.range_query(x1, y1, x2, y2))
 
 

7. Best Practices and Common Pitfalls#

Best Practices#

• Initialization: Always initialize the BIT with all zeros before performing any operations.
• Indexing: Remember that the BIT is 1 - indexed, so when accessing elements in the original array, you need to adjust the indices accordingly.
• Memory Management: Be aware of the memory usage, especially for large two - dimensional arrays.

Common Pitfalls#

• Incorrect Indexing: Using the wrong indices can lead to incorrect results. Make sure to double - check the indices when performing updates and queries.
• Not Using Inclusion - Exclusion Principle: When performing range queries, forgetting to use the inclusion - exclusion principle can lead to incorrect results.

8. Conclusion#

The Two - Dimensional Binary Indexed Tree is a powerful data structure for efficiently performing range queries and point updates on two - dimensional arrays. It provides a significant improvement in time complexity compared to naive methods, especially for large arrays. By understanding the principles behind the one - dimensional BIT and extending them to two dimensions, we can effectively handle two - dimensional data in various applications.

9. References#

• Competitive Programming 3 by Steven Halim and Felix Halim
• GeeksforGeeks: https://www.geeksforgeeks.org/two-dimensional-binary-indexed-tree-or-fenwick-tree/
• TopCoder: https://www.topcoder.com/thrive/articles/Binary%20Indexed%20Trees