0
$\begingroup$

Let's say we have given matrix $N\cdot N$, with zeros and ones only at $P$ position at it. We want to implement queries $q(x_1, y_1, x_2, y_2)$ which will return the number of ones in the sub-rectangle described with those two points. Since $N$ can be up to $10^4$ we cannot create standard DP matrix for answering the queries in $O(1)$. Is it possible to answer such queries without generating the DP matrix?

$\endgroup$
  • $\begingroup$ Instead of using a segment tree, how about using a spatial index such as quadtree or kd-tree? $\endgroup$ – TilmannZ Apr 13 '18 at 10:54
  • $\begingroup$ I havent worked with quadtrees or kd-trees and I dont know much about those. $\endgroup$ – someone12321 Apr 13 '18 at 14:13
  • $\begingroup$ I gave a bit more details in the answer below, let me know if anything is unclear. $\endgroup$ – TilmannZ Apr 14 '18 at 18:38
1
$\begingroup$

You could use a quadtree or kD-Tree. They are multidimensional indexes (your case only needs 2D) that perform insertion, deletion and window queries (rectangle defined by two coordinates) in $O(log (n))$.

In your case you would simply insert all coordinates/cells with '1' into the quadtree/kd-tree. Then you can perform a window query that returns all '1' in a given rectangle. For example, to define a '1' at $(3,7)$:

KDTree<Boolean> tree = new KDTree<>(2); //2 dimensions
tree.put(3, 7, 1); //You could ommit the '1', since all entries will have a '1'.

To perform a query between $(1,1)$ and $( 4,6)$:

Iterator<Entry> iter = tree.query(1,1,4,7);

The iterator contains a sequence of Entries, where each entry has coordinates and a value, such as '1'. The example should return exactly one Entry for $(3,7)$. The syntax will differ between implementations, but they should all be similar.

Be aware that this is only useful if $N$ is large and $P$ is small, because there is some storage overhead.

There are example implementations all over the web, also referenced from the Wikipedia pages. I also have my own Java implementations here, however, they are implemented to work with any dimensionality and take any Object as values so they are a bit overkill if you just use 2D and only store boolean 1/0.

$\endgroup$
  • $\begingroup$ In my case N is up to 10^4 and P is up to 10^5, isnt this overkill for my case $\endgroup$ – someone12321 Apr 14 '18 at 20:19
  • $\begingroup$ Let's just say KD-Tree uses 64bytes per '1', that's about 6.4MB. A simple N*N byte array would be about 100MB. Both should easily fit into memory, but you wrote it would be to large for a DP matrix (but I'm not sure what 'DP' means or implies ?). Both are likely slower than matrix search. I'm sure there are also libraries to store sparse matrices. I made a performance comparison see diagrams 8a (x-label should say bytes per entry) and 14a (for query performance). Look for QZ (quadtree) and KDx (KD-tree). $\endgroup$ – TilmannZ Apr 14 '18 at 22:27
  • $\begingroup$ DP means the well known dynamic programming technique $\endgroup$ – someone12321 Apr 15 '18 at 12:14
  • $\begingroup$ You didn't specify what you mean by DP (even though you tagged the question with 'dynamic programming'), if you search the web for 'DP matrix' there are numerous explanations. But my question was more aimed at what it implies for you: How many searches do you perform before you change or even rebuild the matrix? How many matrices do you need to keep in parallel? Why can you not create a 100MB matrix? If KD-tree is solving the problem of not being able to create the matrix, then it is probably not overkill. $\endgroup$ – TilmannZ Apr 15 '18 at 13:45
  • $\begingroup$ I'm sorry for this, KD tree or quad tree will do my job, but I don't know how to implement it. $\endgroup$ – someone12321 Apr 15 '18 at 19:53

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.