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?
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.