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...);

Problems

2D Offline Sum Queries

See my implementations.

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.

Solution - Soriya's Programming Project

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

Idea 1 - Use an unordered map instead of a 2D array.

Bad idea ... This gives $\mathcal{O}(N\log^2N)$ memory and time and the constant factors for both are terrible.

Idea 2 - Compress the points to be updated so that you only need $\mathcal{O}(N\log N)$ memory.

This doesn't require knowing the queries beforehand.

• my 1D offline BIT
• my 2D offline BIT

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

Idea 3 - Use divide & conquer with a 1D BIT

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.