2D Fenwick Tree / 2D Binary Indexed Tree

data-structure
tree-data-structure
fenwick-tree
binary-indexed-tree
2d-fenwick-tree
2d-binary-indexed-tree

(Team) #1

Fenwick Tree is used to answer range or interval queries in an array in logarithmic time. Fenwick tree can be generalized to multiple dimensions. 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.

Read this article to understand 2D Fenwick Tree in depth

Have a doubt or thought? Join the discussion now


This is a companion discussion topic for the original entry at http://iq.opengenus.org/2d-fenwick-tree/