# Fast query on the number of elements in a quarter plane

I have a scatter of 2D elements on a 2D plane.

I would like an efficient algorithm to prepare and query the number of points in a quarter plane (inclusive of boundary).

The quarter plane is defined by a point $$(x,y)$$. All elements $$(x', y')$$ where $$x<=x'$$ and $$y<=y'$$ are in the quarter plane.

For example

• I have elements [(1,1), (2,2), (1,2), (3,2)],
• My queries are [(1,1), (2,2), (3,3)]

The program should return [1,3,4].

This is for a past competitive programming challenge (WiFi Network problem in this competition)

A 2D Fenwick tree can solve this in $$O(\log^2 N)$$ time and $$O(N^2)$$ space for both update and query, when your coordinates are integers and $$N$$ is the size of the maximum coordinate.

Fenwick trees are nice for competitive programming because they have a really compact implementation, for example in C++:

typedef unsigned long long uw;
uw lsb(uw x) { return x & -x; }
uw  up(uw x) { return x + lsb(x); }
uw  dn(uw x) { return x - lsb(x); }

template<class T> struct Fenwick2D {
uw n; std::vector<std::vector<T>> b;
Fenwick2D(uw n) : n(n), b(n+1, std::vector<T>(n+1)) { }

void increase(uw x, uw y_, T v) {
for (; x <= n; x = up(x))
for (uw y = y_; y <= n; y = up(y))
b[x][y] += v;
}

T prefix_sum(uw x, uw y_) {
T s = 0;
for (; x >= 1; x = dn(x))
for (uw y = y_; y >= 1; y = dn(y))
s += b[x][y];
return s;
}
};


And this shows your example from the question:

int main(int argc, char** argv) {
Fenwick2D<int> fw(4);
fw.increase(1, 1, 1);
fw.increase(2, 2, 1);
fw.increase(1, 2, 1);
fw.increase(3, 2, 1);
std::cout << fw.prefix_sum(1, 1) << "\n";
std::cout << fw.prefix_sum(2, 2) << "\n";
std::cout << fw.prefix_sum(3, 3) << "\n";
return 0;
}


This data structure is more general than your problem as well. In general it can increase any grid element $$g_{x,y}$$ by value $$v$$ (which decreases for negative $$v$$), and ask the value of the lower quadrant prefix sum $$\sum_{i\leq x}\sum_{j\leq y} g_{i,j}$$ for any $$x, y$$. Note that this means you can get area sums as well using 4 queries by the inclusion-exclusion principle.

• Thank you for your answer. $O(N^2)$ space requirement is likely to make me run out of memory, is there a better solution? – HK Tong Aug 3 at 3:58
• @HKTong I would suggest asking a new question with any memory limits in mind. In general I believe you should ask a new question because I took a look at the programming problem and it involves circular neighborhood searches, which is different than what you asked here. – orlp Aug 3 at 9:37