PrevNext
Rare
 0/10

2D Range Queries

Author: Benjamin Qi

Extending Range Queries to 2D (and beyond).

2D RMQ

Quite rare, I've only needed this once.

2D BIT

Focus Problem – read through this problem before continuing!

Tutorial

Implementation

See my implementations.

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

Problems

StatusSourceProblem NameDifficultyTagsSolution
DMOJNormal
Show Tags

2D, BIT

Check DMOJ
IOINormal
Show Tags

3D, BIT

External Sol
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.

  • USACO Camp - "Cows Play Global Thermonuclear War" (2D case)

2D Offline Sum Queries

Focus Problem – read through this problem before continuing!

The intended complexity is O(Nlog2N)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)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 O(Nlog2N)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 O(NlogN)O(N\log N) memory.

This doesn't require knowing the queries beforehand.

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

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

The fastest way.

Problems

StatusSourceProblem NameDifficultyTagsSolution
PlatNormal
Show Tags

2D, BIT

External Sol
PlatNormal
Show Tags

2D, BIT

External Sol
APIONormal
Show Tags

2D, BIT

View Solution

Sparse Segment Tree

Implementation

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

2D Segment Tree

Basically a segment tree of (maybe sparse) segment trees (or BBSTs, see "Advanced - Treap").

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)O(\log^2C) time each but some queries make Quadtree take Θ(C)\Theta(C) time!

Resources
CPHbrief description

Implementation

Resources
USACOcode

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

Note - Memory Usage

Naively, inserting NN elements into a sparse segment tree requires O(NlogC)O(N\log C) memory, giving a bound of O(Nlog2C)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)O(N) while maintaining the same O(NlogC)O(N\log C) insertion time (see the solution for IOI Game below for details).
  • Use BBSTs instead of sparse segment trees.

Problems

Can also try the USACO problems from above.

StatusSourceProblem NameDifficultyTagsSolution
POIHard
Show Tags

2D, Lazy SegTree

External Sol
IOIHard
Show Tags

2D, Sparse SegTree

External Sol
JOIVery Hard
Show Tags

2D, SegTree

External Sol

Module Progress:

Give Us Feedback on 2D Range Queries!

PrevNext