0
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. $O(N^2)$ space requirement is likely to make me run out of memory, is there a better solution? $\endgroup$ – HK Tong Aug 3 at 3:58
  • $\begingroup$ @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. $\endgroup$ – orlp Aug 3 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.