2D Fenwick Tree / 2D Binary Indexed Tree

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/

(post withdrawn by author, will be automatically deleted in 24000 hours unless flagged)

Hi,
I have a question about the time complexity of update an query function.
The outer while x > 0 loop runs in O(logN) time, and the inner while y > 0 loop runs in O(logM) time, so I think it runs in O(log(N)log(M)) instead of O(log(MN)) in total.