2D Range Queries

2D RMQ

Quite rare, I've only needed this once.

2D BIT

Tutorial

Implementation

Essentially, we just nest the loops that one would find in a 1D BIT to get N-dimensional BITs. We can then use PIE to query subrectangles.

Copy
#include <bits/stdc++.h>
using namespace std;

/**
 * 2D Fenwick Tree implementation.
 * Note that all cell locations are zero-indexed
 * in this implementation.
 */
template <typename T> class BIT2D {
  private:

Copy
template <class T, int... Ns> struct BIT {
	T val = 0;
	void upd(T v) { val += v; }
	T query() { return val; }
};

template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
	BIT<T, Ns...> bit[N + 1];
	template <typename... Args> void upd(int pos, Args... args) {
		for (; pos <= N; pos += (pos & -pos)) bit[pos].upd(args...);

Also see Benq's implementations.

Problems

Offline 2D BIT

The intended complexity is $\mathcal{O}(N\log^2 N)$ with a good constant factor. This requires updating points and querying rectangle sums $N$ times for points with coordinates in the range $[1,N]$. However, the 2D BITs mentioned above use $\mathcal{O}(N^2)$ memory, which is too much.

Since we know all of the updates and queries beforehand, we can reduce the memory usage while maintaining a decent constant factor.

We could use an unordered map instead of a 2D array, but this gives $\mathcal{O}(N\log^2N)$ memory and time and the constant factors for both are terrible; a better solution is to compress the points to be updated so that you only need $\mathcal{O}(N\log N)$ memory.

The idea is to first figure out which BIT values along one dimension each update will affect. In the below table, the updates are $(1, 1), (3, 3),$ and $(4, 2)$, and the cells they affect are blue, red, and green respectively.

We can now compress each row in the same fashion as an offline 1D BIT (remember, each row in a 2D BIT is another 1D BIT)! For example, we can compress the second row to a BIT of size 2, and map range queries $[1, y)$ with $y \in [1, 4)$ to a range query of $[1, 2)$, and queries with $y \in [4, \infty)$ to a range query of $[1, 3)$.

Similarly, for row 4 (which becomes a BIT of size 3):

• $y \in [1, 3)$ -> range query $[1, 2)$
• $y \in [3, 4)$ -> range query $[1, 3)$
• $y \in [4, \infty)$ -> range query $[1, 4)$

This only requires knowing the updates beforehand, not the queries!

Implementation

• Benq's 1D offline BIT
• Benq's 2D offline BIT

Here's an implementation of the offline 2D BIT presented above that may be easier to understand, albeit significantly slower due to a high constant factor:

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

/**
 * Offline 2D Fenwick Tree implementation.
 * Note that n needs to be of a reasonable size, and
 * all the updates/queries inputs are zero indexed.
 */
template <typename T> class OfflineBIT2D {

And you might use it like so:

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

/**
 * Offline 2D Fenwick Tree implementation.
 * Note that n needs to be of a reasonable size, and
 * all the updates/queries inputs are zero indexed.
 */
template <typename T> class OfflineBIT2D {

It's a bit difficult to pass the above problem within the time limit. Make sure to use fast input (and not endl)!

• thecodingwizard's implementation with 2D offline BIT above

1D BIT + Divide & Conquer

The fastest way.

• mentioned in this article
• thecodingwizard's (messy) implementation based off above

Problems

2D Segment Tree

A segment tree of (maybe sparse) segment trees.

Implementation

Note - Memory Usage

Naively, inserting $N$ elements into a sparse segment tree requires $\mathcal{O}(N\log C)$ memory, giving a bound of $\mathcal{O}(N\log^2C)$ on 2D segment tree memory. This is usually too much for $N=C=10^5$ and 256 MB (although it sufficed for "Mowing the Field" due to the 512MB memory limit). Possible ways to get around this:

• Use arrays of fixed size rather than pointers.
• Reduce the memory usage of sparse segment tree to $\mathcal{O}(N)$ while maintaining the same $\mathcal{O}(N\log C)$ insertion time (see the solution for IOI Game below for details).
• Use BBSTs instead of sparse segment trees. $\mathcal{O}(N)$ memory, $\mathcal{O}(N\log N)$ insertion time.

Problems

Can also try the USACO problems from above.