# 2D rectangle queries

### The problem
Given $N$ points $(x_i,y_i)$ that satisfy $1 \leq x_i,y_i \leq N$, answer $Q$ queries of the form "how many points are in the rectangle $[a,b] \times [c,d]$."

We will solve the problem in $O((N+Q)\log(N))$ offline. Offline means that we know all the queries beforehand, and can answer all of them at once.

### Solution
The following technique is known as sweep line. The goal is to reduce the problem to something that can be solved using a normal 1D segment tree.

First, realize that every query $[a,b] \times [c,d]$ can be split into two parts. Suppose
$$s=\text{countpoints}([a,b]\times[c,d])$$

Then, we can realize that this is equal to
$$s=\text{countpoints}([a,b]\times[0,d])-\text{countpoints}([a,b]\times[0,c-1])$$

You will see later that this is easier to compute. Visually, suppose we want to count the number of points in the blue region.

Then, this is equal to the number of points in the green region minus the number of points in the red region.



Using this, we can split an arbitrary query into two parts, both being a rectangle query of the form $[a,b] \times [0,y]$.

To answer these queries, let's sort all of them by increasing $y$ value. We also sort all points by their $y$ in increasing order. Let's iterate through queries in increasing order of $y$ value. To answer a query $[a,b] \times [0,y_q]$, ensure that every point $(x_i,y_i)$ with $y_i < y_q$ is added to a segment tree. To "add" a point $(x_i,y_i)$ to the segment tree, increment $x_i$ by 1. Then, the answer to the query can be gotten by querying $[a,b]$ in the segment tree.

Visually, suppose we want to query $[1,4] \times [0,3]$.


Then, our segment tree will have all points with $y_i \leq 3$. It will look like this:


Notice that the sum of all values in $[1,4]=4$, which is the number of points in the rectangle.

Pseudocode

answers = [0 for i in range(q)]
queries = []
for i in range(q):
    a,b,c,d=queries[i]
    # [a,b] x [c,d]
    queries.append((d,a,b,i,+1)) # The last one is plus since this is green region
    queries.append((c-1,a,b,i,-1)) # The last one is minus since this is red region
queries.sort()

segtree = new Segtree(n)
points.sort(lambda p: p[1]) # sort points by y
p_ind = 0
for query in queries:
    y = query[0]
    while p_ind < n and points[p_ind][1] <= y:
        tree.add(points[p_ind][0], 1)
        p_ind += 1
    
    q_ind = query[3]
    l,r = query[1],query[2]
    sign = query[4]
    answers[q_ind] += sign * segtree.query(l,r)

### Extensions
We can do this online (queries are not known beforehand, we have to answer them sequentially) in the same complexity using persistent segment trees. https://usaco.guide/adv/persistent?lang=cpp#persistent-segment-tree
Unfortunately, they have a worse constant factor.

In general, any offline algorithm that uses sweepline segment tree can be made online using persistent segment trees.