shehneelkhan / two-dimensional-binary-indexed-tree

It is a data structure used to update and query a 2D matrix in a better way because of its good time and space complexities.

2D Fenwick Tree

This is the project for "Data structures and algorithms". I have used Python for this project whereas no libraries have been used.

Introduction

To understand 2D Fenwick tree better, you should first understand Fenwick tree.

Binary Indexed Tree/Fenwick Tree

A Binary Indexed Tree or Fenwick Tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. We know that to answer range sum queries on a 1-D array efficiently, binary indexed tree (or Fenwick Tree) is the best choice (even better than segment tree due to less memory requirements and a little faster than segment tree).

Two Dimenstional Binary Indexed Tree/2D Fenwick Tree

2D Fenwick tree is one such implementation used to answer sub-matrix queries, i.e. queries in 2 dimensions. Fenwick tree is considered a prerequisite to understand 2D Fenwick tree. Like 1D, 2D Fenwick tree also requires the operation to be invertible.

Since Fenwick tree stores prefix sums, 1D Fenwick tree works by processing query(m, n) as query(1, n) - query(1, m - 1). 2D Fenwick tree operates on a matrix, so query is processed differently, but the requirement is still same, i.e. operation must be invertible.

Complexity

Space complexity : O(MN)

Worst case time complexities:

• Update : O(log2(MN))
• Query : O(log2(MN)) Where the matrix is of size M x N

Applications

• Is much more space efficient than 2D Segment tree or Quad tree.
• The queries can be processed in O(log2mn) time.
• Used for finding sub-matrix sum/product etc.
• Cannot be used for sub-matrix min/max.

two-dimensional-binary-indexed-tree's Issues

fix some bug and improve some code

'''python
class FenwickTree:

def __init__(self, matrix):
    self.m = len(matrix)
    self.n = len(matrix[0])
    self.ft = [[0 for i in range(self.n + 1)] for i in range(self.m + 1)] # (m+1)*(n+1) matrix full of 0
    for i in range(self.m):
        for j in range(self.n):
            self.update(i+1, j+1, matrix[i][j]) # ft[1,m][1,n]

def LSB(self, x):
    return x & (-x) # toggling of the last set 1 bit in the binary representation of i

def update(self, x, y, val):
    while x <= self.m:
        y1 = y
        while y1 <= self.n:
            self.ft[x][y1] += val
            y1 += self.LSB(y1)
        x += self.LSB(x)

def summation(self, x, y):
    if x > self.m or y > self.n or x < 1 or y < 1:
        raise IndexError(f"0 < x < {self.m +1}, 0 < y < {self.n + 1}")
    s = 0
    x1 = x
    while x1 > 0:
        y1 = y
        while y1 > 0:
            s += self.ft[x1][y1]
            y1 -= self.LSB(y1)
        x1 -= self.LSB(x1)
    return s

def Summation(self, x1, y1, x2, y2):
    return (self.summation(x2, y2) - self.summation(x1-1, y2) - self.summation(x2, y1-1) + self.summation(x1-1,x2-1))

if name == "main":

matrix = [[1, 2, 3, 4],
          [5, 3, 8, 1],
          [4, 6, 7, 5]]

f = FenwickTree(matrix)

print(f.summation(2,3)) # 1+2+3+5+3+8
print(f.summation(1, 1)) # 1
print(f.Summation(1,2,2,3)) # 2+3+3+8

'''