# Is it possible to obtain dynamic tree with two dimensions in big matrix

Let's say we have given matrix of size $n \cdot m$, such that both $n, m$ are big numbers and we cannot keep the whole matrix in memory (up to 10 millions).

In some of the coordinates of the matrix there are positive numbers and all other fields are zeroes (at most 100000 elements are with value different from 0). For each element we are keeping three values, the $x, y$ coordinate and the value of it.

How could we answer queries of type $q(i, j)$ to return the sum in the fields that are in the submatrix from $(0, 0) \text{ to } (i, j)$.

Is there way to create tree that will be able to answer such queries. Thanks in advance.

• Why tree? How many entries are filled? Have you considered sparse matrix representation? Is there a constraint on query time?
– Evil
Nov 3 '17 at 22:17
• Around 100000 entries are filled with numbers, we should be able to answer more queries, so they should be in O(logN) or O(sqrt(N)) Nov 3 '17 at 22:25

Yes. Use a persistent data structure. Build a tree data structure to answer queries of the form $q(i,0)$. Then, advance $j$, updating the persistent tree data structure as you do. This will build a data structure of size $k$ and let you answer queries in $O(\log k)$ time, where $k$ is the number of non-zero entries in the matrix.
• @someone12321, sorry, that was a typo, I meant $O(\log k)$. I've updated my answer accordingly. This should be fast.