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.

1#include <bits/stdc++.h>
2using namespace std;
3
4int bit[1001][1001];
5int n;
6
7void update(int x, int y, int val) {
8    for (; x <= n; x += (x & (-x))) {
9        for (int i = y; i <= n; i += (i & (-i))) {
10            bit[x][i] += val;

1template <class T, int ...Ns> struct BIT {
2    T val = 0;
3    void upd(T v) { val += v; }
4    T query() { return val; }
5};
6 
7template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
8    BIT<T,Ns...> bit[N + 1];
9    template<typename... Args> void upd(int pos, Args... args) {
10        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 }^{2}N)$ 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 }^{2}C)$ 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.