PrevNext
Rare
 0/10

2D Range Queries

Authors: Benjamin Qi, Andi Qu

Contributors: Daniel Zhu, Justin Ji

Extending Range Queries to 2D (and beyond).

2D RMQ

Quite rare, I've only needed this once.

2D BIT

Focus Problem – try your best to solve this problem before continuing!

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.

C++

#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:

Alternative Implementation

Using the multidimensional implementation mentioned here.

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

StatusSourceProblem NameDifficultyTags
Back From SummerNormal
Show Tags2DRQ, BIT
IOINormal
Show Tags3DRQ, BIT

Optional: Range Update and Range Query in Higher Dimensions

Lazy propagation on segment trees does not extend to higher dimensions. However, you can extend the 1D BIT solution to solve range increment range sum in higher dimensions as well! See this paper for details.

Focus Problem – try your best to solve this problem before continuing!

Offline 2D BIT

The intended complexity is O(Nlog2N)\mathcal{O}(N\log^2 N) with a good constant factor. This requires updating points and querying rectangle sums NN times for points with coordinates in the range [1,N][1,N]. However, the 2D BITs mentioned above use O(N2)\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 O(Nlog2N)\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 O(NlogN)\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),(1, 1), (3, 3), and (4,2)(4, 2), and the cells they affect are blue, red, and green respectively.

(1, 1) (1, 2) (1, 3) (1, 4)
(2, 1) (2, 2) (2, 3) (2, 4)
(3, 1) (3, 2) (3, 3) (3, 4)
(4, 1) (4, 2) (4, 3) (4, 4)

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)[1, y) with y[1,4)y \in [1, 4) to a range query of [1,2)[1, 2), and queries with y[4,)y \in [4, \infty) to a range query of [1,3)[1, 3).

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

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

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

Implementation

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:

C++

#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:

C++

#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 {

Warning: Implementation Note

As mentioned earlier, the above OfflineBIT2D implementation is significantly slower than Benq's OffBIT2D and, in fact, will get TLE on the Soriya's Programming Project.

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

1D BIT + Divide & Conquer

The fastest way.

Problems

StatusSourceProblem NameDifficultyTags
PlatinumNormal
Show Tags2DRQ, BIT
PlatinumNormal
Show Tags2DRQ, BIT
APIONormal
Show Tags2DRQ, BIT

2D Segment Tree

A segment tree of (maybe sparse) segment trees.

Pro Tip

This is not the same as Quadtree. If the coordinates go up to CC, then 2D segment tree queries run in O(log2C)\mathcal{O}(\log^2C) time each but some queries make Quadtree take Θ(C)\Theta(C) time!

Resources
CPH

Brief description

Implementation

Resources
USACO

Code

cp-algo

More code

Note - Memory Usage

Naively, inserting NN elements into a sparse segment tree requires O(NlogC)\mathcal{O}(N\log C) memory, giving a bound of O(Nlog2C)\mathcal{O}(N\log^2C) on 2D segment tree memory. This is usually too much for N=C=105N=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 O(N)\mathcal{O}(N) while maintaining the same O(NlogC)\mathcal{O}(N\log C) insertion time (see the solution for IOI Game below for details).
  • Use BBSTs instead of sparse segment trees. O(N)\mathcal{O}(N) memory, O(NlogN)\mathcal{O}(N\log N) insertion time.

Problems

Can also try the USACO problems from above.

StatusSourceProblem NameDifficultyTags
POIHard
Show Tags2DRQ, Lazy SegTree
IOIHard
Show Tags2DRQ, Sparse SegTree, Treap
JOIVery Hard
Show Tags2DRQ, SegTree

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext