Transform 2D range query matrix into segment tree to make memory usage lower
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&lt;Boolean&gt; tree = new KDTree&lt;&gt;(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&lt;Entry&gt; 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.