Let's say that we have n Rectangles with known coordinates and m Points with known coordinates.
How to count the number of points that lie inside each Rectangle given that the coordinates are integers (>= 0, <= 106) and n & m <= 106.
Surely, the complexity of O(n*m) is not desirable!
I think of Segment Tree but don't know how and if it's better or not!
May you help me, please?
Hint
You could use a 2D segment tree. https://cp-algorithms.com/data_structures/segment_tree.html
For each rectangle, let's define $$$x_1, x_2, y_1, y_2$$$ as:
consecutively.
Obviously if a point $$$i$$$ is inside the rectangle, the condition $$$x_1 ≤ x_i ≤ x_2$$$ and $$$y_1 ≤ y_i ≤ y_2$$$ must be satisfied.
To solve the problem, sort all points based on their $$$x$$$ coordinate first. Let $$$A$$$ denote the array of $$$y$$$ coordinate of all the points(after have been sorted).
For rectangle $$$j$$$, use binary search to find all points with $$$x$$$ coordinate lie within the range $$$[x_1, x_2]$$$. Assume the points we found is the range $$$[l_j, r_j]$$$, the problem turns into finding how many elements smaller or equal to $$$y_2$$$ and bigger or equal to $$$y_1$$$ in range $$$[l_j, r_j]$$$ of array $$$A$$$. This problem can be solved with Segment Tree or Fenwick Tree easily. In order to calculate the answer easier, we can see that the answer is equal to the difference between the number of elements smaller or equal to $$$y_2$$$ and the number of elements smaller than $$$y_1$$$.