Core Idea
The fundamental approach to rectangle point counting problems involves sorting all points by their x-coordinate, then reducing the 2D problem to a 1D problem on y-coordinates. As we sweep across the x-axis, a Binary Indexed Tree (Fenwick Tree) maintains operations on y-values, enabling efficient querying of points within specified rectangular bounds.
Problem 1: Rectangle Query Point Counting
Statement: Given n points and m axis-aligned rectangle queries, determine how many points fall inside each query rectangle. All operations are offline.
Constraints: (0 \leq n, m \leq 5 \times 10^5), coordinates range from 0 to (10^7).
Solution:
Transform each rectangle query into four corner points using the inclusion-exclusion principle:
[N_{total} = N_{x_2,y_2} - N_{x_1-1,y_2} - N_{x_2,y_1-1} + N_{x_1-1,y_1-1} ]
This decomposes the rectangle query into prefix sum computations. By collecting all corner points and sorting them along with the original points by x-then-y order, a single sweep sufffices.
During the sweep, maintain a BIT where each update adds 1 at the current point's y-coordinate, and each query asks for the count of points with y-coordinate less than or equal to the target y.
Since coordinates begin at 0 but BIT operates on 1-indexed arrays, shift all coordinates by +1.
Implementation:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
const int MAXY = 1e7 + 5;
struct Point {
int x, y;
bool operator<(const Point& other) const {
return x < other.x || (x == other.x && y < other.y);
}
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
} pts[MAXN];
struct QueryNode {
Point coord;
int coeff, qid;
bool operator<(const QueryNode& other) const {
return coord < other.coord;
}
} queries[4 * MAXN];
int bit[MAXY];
int n, m, result[MAXN];
int lsb(int x) { return x & -x; }
void update(int idx, int delta) {
while (idx <= n) {
bit[idx] += delta;
idx += lsb(idx);
}
}
int prefixSum(int idx) {
int sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= lsb(idx);
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> pts[i].x >> pts[i].y;
++pts[i].x;
++pts[i].y;
}
sort(pts + 1, pts + n + 1);
for (int i = 1; i <= m; ++i) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
queries[4*i-3] = {{x1, y1}, 1, i};
queries[4*i-2] = {{x2+1, y2+1}, 1, i};
queries[4*i-1] = {{x1, y2+1}, -1, i};
queries[4*i] = {{x2+1, y1}, -1, i};
}
m *= 4;
sort(queries + 1, queries + m + 1);
int pIdx = 1;
for (int i = 1; i <= m; ++i) {
while (pIdx <= n && (pts[pIdx] < queries[i].coord || pts[pIdx] == queries[i].coord)) {
update(pts[pIdx].y, 1);
++pIdx;
}
result[queries[i].qid] += queries[i].coeff * prefixSum(queries[i].coord.y);
}
for (int i = 1; i <= m/4; ++i)
cout << result[i] << '\n';
return 0;
}
Problem 2: Weighted Rectangle Query
Statement: Given n weighted points and m rectangle queries, compute the sum of point weights within each query rectangle.
Constraints: (1 \leq n, m \leq 10^5), coordinates and weights span the full 32-bit signed integer range.
Key Differences:
- Point weights require summation rather then simple counting
- Coordinate ranges are much wider, necessitating y-coordinate discretization
- Use 64-bit integers to prevent overflow when accumulating weights
Solution:
The approach mirrors the previous problem, but y-coordinates must be discretized into a contiguous range since (|y| < 2^{31}). Collect all y-values from both points and query boundaries, sort them, and map each y-coordinate to its rank in the sorted list.
Implementation:
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MAXN = 3e5 + 5;
struct Point {
int64 x, y;
bool operator<(const Point& other) const {
return x < other.x || (x == other.x && y < other.y);
}
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
struct WeightedPoint {
Point p;
int64 weight;
} wp[MAXN];
struct QueryPoint {
Point coord;
int coeff, qid;
bool operator<(const QueryPoint& other) const {
return coord < other.coord;
}
} qp[4 * MAXN];
vector<int64> yValues;
int64 bit[5 * MAXN], answer[MAXN];
int n, m;
int lsb(int x) { return x & -x; }
void update(int idx, int64 delta) {
while (idx <= n + 4*m) {
bit[idx] += delta;
idx += lsb(idx);
}
}
int64 prefixSum(int idx) {
int64 sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= lsb(idx);
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> wp[i].p.x >> wp[i].p.y >> wp[i].weight;
yValues.push_back(wp[i].p.y);
}
sort(wp + 1, wp + n + 1);
for (int i = 1; i <= m; ++i) {
int64 x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
qp[4*i-3] = {{x1-1, y1-1}, 1, i};
qp[4*i-2] = {{x2, y2}, 1, i};
qp[4*i-1] = {{x1-1, y2}, -1, i};
qp[4*i] = {{x2, y1-1}, -1, i};
yValues.push_back(y1 - 1);
yValues.push_back(y2);
}
sort(yValues.begin(), yValues.end());
yValues.erase(unique(yValues.begin(), yValues.end()), yValues.end());
int totalQueries = 4 * m;
sort(qp + 1, qp + totalQueries + 1);
int pIdx = 1;
for (int i = 1; i <= totalQueries; ++i) {
while (pIdx <= n && (wp[pIdx].p < qp[i].coord || wp[pIdx].p == qp[i].coord)) {
int yIdx = lower_bound(yValues.begin(), yValues.end(), wp[pIdx].p.y) - yValues.begin() + 1;
update(yIdx, wp[pIdx].weight);
++pIdx;
}
int yIdx = lower_bound(yValues.begin(), yValues.end(), qp[i].coord.y) - yValues.begin() + 1;
answer[qp[i].qid] += qp[i].coeff * prefixSum(yIdx);
}
for (int i = 1; i <= m; ++i)
cout << answer[i] << '\n';
return 0;
}
Complexity Enalysis:
Both solutions achieve (O((n + m) \log(n + m))) time complexity through sorting and BIT operations, with (O(n + m)) space usage dominated by the discretization array and BIT.
The sweep line technique transforms the 2D offline query problem into a sequence of 1D prefix sum operations, making it applicable to various geometric counting and aggregation problems.