1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Why tree? How many entries are filled? Have you considered sparse matrix representation? Is there a constraint on query time? $\endgroup$
    – Evil
    Commented Nov 3, 2017 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$
    – someone12321
    Commented Nov 3, 2017 at 22:25

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Is it possible to answer queries in faster way, O(K) is pretty slow if we want to answer more queries $\endgroup$
    – someone12321
    Commented Nov 5, 2017 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. ♦
    Commented Nov 5, 2017 at 18:36
  • $\begingroup$ Thanks for your answer, is it best to build persistent segment tree? $\endgroup$
    – someone12321
    Commented Nov 5, 2017 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. ♦
    Commented Nov 5, 2017 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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