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.

  • $\begingroup$ Why tree? How many entries are filled? Have you considered sparse matrix representation? Is there a constraint on query time? $\endgroup$
    – Evil
    Nov 3 '17 at 22:17
  • 1
    $\begingroup$ 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)) $\endgroup$ 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.

  • $\begingroup$ Is it possible to answer queries in faster way, O(K) is pretty slow if we want to answer more queries $\endgroup$ Nov 5 '17 at 9:04
  • $\begingroup$ @someone12321, sorry, that was a typo, I meant $O(\log k)$. I've updated my answer accordingly. This should be fast. $\endgroup$
    – D.W.
    Nov 5 '17 at 18:36
  • $\begingroup$ Thanks for your answer, is it best to build persistent segment tree? $\endgroup$ Nov 5 '17 at 19:04
  • $\begingroup$ @someone12321, you could, but since the intervals are disjoint, you don't need to do that -- a binary search tree (keyed on the endpoints of the intervals) suffices and is probably simpler to implement. $\endgroup$
    – D.W.
    Nov 5 '17 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.