## Table of Contents

2D RMQ2D BITTutorialImplementationAlternative ImplementationProblems2D Offline Sum QueriesSolution - Soriya's Programming ProjectIdea 1 - Use an unordered map instead of a 2D array.Idea 2 - Compress the points to be updated so that you only need $\mathcal{O}(N\log N)$ memory.Idea 3 - Use divide & conquer with a 1D BITProblems2D Segment TreeImplementationNote - Memory UsageProblems# 2D Range Queries

Authors: Benjamin Qi, Andi Qu

Extending Range Queries to 2D (and beyond).

### Prerequisites

## Table of Contents

2D RMQ2D BITTutorialImplementationAlternative ImplementationProblems2D Offline Sum QueriesSolution - Soriya's Programming ProjectIdea 1 - Use an unordered map instead of a 2D array.Idea 2 - Compress the points to be updated so that you only need $\mathcal{O}(N\log N)$ memory.Idea 3 - Use divide & conquer with a 1D BITProblems2D Segment TreeImplementationNote - Memory UsageProblems## 2D RMQ

Resources | ||||
---|---|---|---|---|

CF |

Quite rare, I've only needed this once.

## 2D BIT

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

### Tutorial

Resources | ||||
---|---|---|---|---|

GFG | ||||

TC |

### 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;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; }}

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

### Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Back From Summer | Normal | ## Show Tags2DRQ, BIT | |||

IOI | Normal | ## 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.

## 2D Offline Sum Queries

See my implementations.

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

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.

#### $\mathcal{O}(N\log N)$ memory.

Idea 2 - Compress the points to be updated so that you only needThis 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.

- mentioned in this article
- thecodingwizard's (messy) implementation based off above

### Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Plat | Normal | ## Show Tags2DRQ, BIT | |||

Plat | Normal | ## Show Tags2DRQ, BIT | |||

APIO | Normal | ## 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 $C$, then 2D segment tree queries run in
$\mathcal{O}(\log^2C)$ time each but some queries make Quadtree take $\Theta(C)$
time!

Resources | ||||
---|---|---|---|---|

CPH | Brief description |

### Implementation

Resources | ||||
---|---|---|---|---|

USACO | Code | |||

cp-algo | More code |

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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

POI | Hard | ## Show Tags2DRQ, Lazy SegTree | |||

IOI | Hard | ## Show Tags2DRQ, Sparse SegTree, Treap | |||

JOI | Very 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!