AlgoGenesis / C

AlgoGenesis is a centralized open-source platform dedicated to providing optimized and well-documented algorithm implementations in C. Perfect for both beginners and advanced users, this repository serves as a comprehensive learning resource for solving algorithmic challenges.
MIT License
88 stars 306 forks source link

[NEW ALGORITHM] 2D Binary Index Tree #1490

Closed MahraibFatima closed 2 weeks ago

MahraibFatima commented 2 weeks ago

Issue will be closed if:

1) You mention more than one algorithm. You can create a separate issue for each algorithm once the current one is completed.
2) You propose an algorithm that is already present or has been mentioned in a previous issue.
3) You create a new issue without completing your previous issue.

Note: These actions will be taken seriously. Failure to follow the guidelines may result in the immediate closure of your issue.


Name:

[2D Binary Index Tree]

About:

PrerequisiteFenwick Tree

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).

Can we answer sub-matrix sum queries efficiently using Binary Indexed Tree ? The answer is yes. This is possible using a 2D BIT which is nothing but an array of 1D BIT.

Algorithm:

We consider the below example. Suppose we have to find the sum of all numbers inside the highlighted area:

Screenshot 2024-10-30 130026

We assume the origin of the matrix at the bottom – O.Then a 2D BIT exploits the fact that-

Sum under the marked area = Sum(OB) - Sum(OD) - Sum(OA) + Sum(OC)

Labels:

new algorithm, gssoc-ext, hacktoberfest, level3


Assignees:

Riddhi12349 commented 2 weeks ago

Please assign me