---
# System prepended metadata

title: Rectangle queries
tags: [algorithm blog]

---

# 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.
![Screenshot 2025-01-29 114713](https://hackmd.io/_uploads/B1XTDtDdyx.png)

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

![green](https://hackmd.io/_uploads/BkiCDYPOke.png)

![red](https://hackmd.io/_uploads/BJpk_KvOJl.png)

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]$.

![Screenshot 2025-01-29 120441](https://hackmd.io/_uploads/Bkq8stw_kg.png)

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

![Screenshot 2025-01-29 120720](https://hackmd.io/_uploads/SJKx2Fw_Je.png)

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

Pseudocode

```python!
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.
