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;

int bit[1001][1001];
int n;

void update(int x, int y, int val) {
	for (; x <= n; x += (x & (-x))) {
		for (int i = y; i <= n; i += (i & (-i))) { bit[x][i] += val; }
	}

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
// index of largest value <= x in v (sorted)
// if v = [1, 2, 4], ind(v, 3) would return 1
int ind(vector<int> v, int x) {
	return upper_bound(v.begin(), v.end(), x) - v.begin() - 1;
}

class BIT2D {
  private:
	int n;  // max x-coordinate
	vector<vector<int>> vals, bit;

And you might use it like so:

Copy
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

 Code Snippet: BIT2D (Click to expand)

int main() {

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.