Consultas de rango 2D

RMQ 2D

Recursos
Fuente	Recurso	Notas
CF	retrograd - Multi-Dimensional RMQ

Bastante raro; solo lo necesité una vez.

BIT 2D

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Forest Queries II	Fácil	2DRQ, BIT	en el módulo

Tutorial

Recursos
Fuente	Recurso	Notas
GFG	2D BIT
TC	Binary Indexed Trees

Implementación

Esencialmente, anidamos los bucles que uno encontraría en un BIT 1D para obtener BIT de N dimensiones. Después podemos usar PIE para consultar subrectángulos.

C++


#include <iostream>
#include <vector>
using namespace std;
 
/**
 * Implementación de Árbol de Fenwick 2D.
 * Notar que todas las celdas están indexadas desde cero
 * en esta implementación.
 */
template <typename T> class BIT2D {
  private:
	const int n, m;
	vector<vector<T>> bit;
 
  public:
	BIT2D(int n, int m) : n(n), m(m), bit(n + 1, vector<T>(m + 1)) {}
 
	/** suma val al punto (r, c) */
	void add(int r, int c, T val) {
		r++, c++;
		for (; r <= n; r += r & -r) {
			for (int i = c; i <= m; i += i & -i) { bit[r][i] += val; }
		}
	}
 
	/** @returns suma de los puntos con fila en [0, r] y columna en [0, c] */
	T rect_sum(int r, int c) {
		r++, c++;
		T sum = 0;
		for (; r > 0; r -= r & -r) {
			for (int i = c; i > 0; i -= i & -i) { sum += bit[r][i]; }
		}
		return sum;
	}
 
	/** @returns suma de los puntos con fila en [r1, r2] y columna en [c1, c2] */
	T rect_sum(int r1, int c1, int r2, int c2) {
		return rect_sum(r2, c2) - rect_sum(r2, c1 - 1) - rect_sum(r1 - 1, c2) +
		       rect_sum(r1 - 1, c1 - 1);
	}
};
 
int main() {
	int n, q;
	cin >> n >> q;
	BIT2D<int> bit(n, n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			char c;
			cin >> c;
			if (c == '*') { bit.add(i, j, 1); }
		}
	}
 
	for (int i = 0; i < q; i++) {
		int type;
		cin >> type;
		if (type == 1) {
			int r, c;
			cin >> r >> c;
			r--, c--;
			if (bit.rect_sum(r, c, r, c) == 1) {
				bit.add(r, c, -1);
			} else {
				bit.add(r, c, 1);
			}
		} else if (type == 2) {
			int r1, c1, r2, c2;
			cin >> r1 >> c1 >> r2 >> c2;
			r1--, c1--, r2--, c2--;
			cout << bit.rect_sum(r1, c1, r2, c2) << '\n';
		}
	}
}

Implementación alternativa

Usando la implementación multidimensional mencionada acá.


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...);
	}
	template <typename... Args> T sum(int r, Args... args) {
		T res = 0;
		for (; r; r -= (r & -r)) res += bit[r].query(args...);
		return res;
	}
	template <typename... Args> T query(int l, int r, Args... args) {
		return sum(r, args...) - sum(l - 1, args...);
	}
};  // BIT<int,10,10> gives a 2D BIT
 
BIT<int, 1000, 1000> B;
int n, q;
 
int main() {
	setIO();
	re(n, q);
	F0R(i, n) {
		string s;
		re(s);
		F0R(j, n) if (s[j] == '*') B.upd(i + 1, j + 1, 1);
	}
	F0R(i, q) {
		int t;
		re(t);
		if (t == 1) {
			int y, x;
			re(y, x);
			if (B.query(y, y, x, x)) B.upd(y, x, -1);
			else B.upd(y, x, 1);
		} else {
			int y1, x1, y2, x2;
			re(y1, x1, y2, x2);
			ps(B.query(y1, y2, x1, x2));
		}
	}
}

También ver las implementaciones de Benq .

Problemas

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Back From Summer	Crowded Cities	Normal	2DRQ, BIT	—
	IOI	2007 - Pairs	Normal	3DRQ, BIT	Solución

Actualización de rango y consulta de rango en dimensiones superiores

La propagación perezosa en árboles de segmentos no se extiende a dimensiones superiores. Sin embargo, se puede extender la solución de BIT 1D para resolver incremento de rango y suma de rango también en dimensiones superiores. Ver este paper para los detalles.

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	DMOPC	Soriya's Programming Project	Normal	D&C, 2DRQ, BIT	—

BIT 2D offline

La complejidad intencionada es $\mathcal{O}(N\log^2 N)$ con un buen factor constante. Esto requiere actualizar puntos y consultar sumas de rectángulos $N$ veces para puntos con coordenadas en el rango $[1,N]$ . Sin embargo, los BIT 2D mencionados arriba usan memoria $\mathcal{O}(N^2)$ , que es demasiado.

Como conocemos de antemano todas las actualizaciones y consultas, podemos reducir el uso de memoria manteniendo un factor constante decente.

Podríamos usar un unordered map en vez de un arreglo 2D, pero esto da memoria y tiempo $\mathcal{O}(N\log^2N)$ y los factores constantes de ambos son terribles; una mejor solución es comprimir los puntos a actualizar de modo que solo se necesite memoria $\mathcal{O}(N\log N)$ .

La idea es primero averiguar qué valores del BIT a lo largo de una dimensión afectará cada actualización. En la tabla de abajo, las actualizaciones son $(1, 1), (3, 3)$ y $(4, 2)$ , y las celdas que afectan son azul, rojo y verde respectivamente.

(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)

Ahora podemos comprimir cada fila de la misma forma que un BIT 1D offline (recordar que cada fila de un BIT 2D es otro BIT 1D). Por ejemplo, podemos comprimir la segunda fila a un BIT de tamaño 2, y mapear consultas de rango $[1, y)$ con $y \in [1, 4)$ a una consulta de rango $[1, 2)$ , y consultas con $y \in [4, \infty)$ a una consulta de rango $[1, 3)$ .

De forma similar, para la fila 4 (que se vuelve un BIT de tamaño 3):

$y \in [1, 3)$ -> consulta de rango $[1, 2)$
$y \in [3, 4)$ -> consulta de rango $[1, 3)$
$y \in [4, \infty)$ -> consulta de rango $[1, 4)$

¡Esto solo requiere conocer las actualizaciones de antemano, no las consultas!

Implementación

Acá hay una implementación del BIT 2D offline presentado arriba que puede ser más fácil de entender, aunque bastante más lenta por un factor constante alto:

C++


#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
using namespace std;
 
/**
 * Implementación de Árbol de Fenwick 2D offline.
 * Notar que todos los índices de actualización y consulta
 * están indexados desde cero, y que las filas no están
 * comprimidas por coordenadas en esta implementación.
 */
template <typename T> class OfflineBIT2D {
  private:
	const int n;
	vector<vector<int>> vals;
	vector<vector<T>> bit;
 
	/** @return el primer índice i tal que v[i] <= x */
	int ind(const vector<int> &v, int x) {
		return upper_bound(begin(v), end(v), x) - begin(v) - 1;
	}
 
  public:
	OfflineBIT2D(int n, vector<array<int, 2>> &todo) : n(n), vals(n + 1), bit(n + 1) {
		sort(begin(todo), end(todo),
		     [](const array<int, 2> &a, const array<int, 2> &b) -> bool {
			     return a[1] < b[1];
		     });
 
		for (int i = 1; i <= n; i++) { vals[i].push_back(0); }
		for (auto [r, c] : todo) {
			r++, c++;
			for (; r <= n; r += r & -r) {
				if (vals[r].back() != c) { vals[r].push_back(c); }
			}
		}
		for (int i = 1; i <= n; i++) { bit[i].resize(vals[i].size()); }
	}
 
	/** suma val al punto (r, c) */
	void add(int r, int c, T val) {
		r++, c++;
		for (; r <= n; r += r & -r) {
			int i = ind(vals[r], c);
			for (; i < bit[r].size(); i += i & -i) { bit[r][i] += val; }
		}
	}
 
	/** @returns suma de los puntos con fila en [0, r] y columna en [0, c] */
	T rect_sum(int r, int c) {
		r++, c++;
		T sum = 0;
		for (; r > 0; r -= r & -r) {
			int i = ind(vals[r], c);
			for (; i > 0; i -= i & -i) { sum += bit[r][i]; }
		}
		return sum;
	}
 
	/** @returns suma de los puntos con fila en [r1, r2] y columna en [c1, c2] */
	T rect_sum(int r1, int c1, int r2, int c2) {
		return rect_sum(r2, c2) - rect_sum(r2, c1 - 1) - rect_sum(r1 - 1, c2) +
		       rect_sum(r1 - 1, c1 - 1);
	}
};

Y se podría usar así:

C++


#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
 
// BeginCodeSnip{Offline 2D BIT}
template <typename T> class OfflineBIT2D {
  private:
	const int n;
	vector<vector<int>> vals;
	vector<vector<T>> bit;
 
	int ind(const vector<int> &v, int x) {
		return upper_bound(begin(v), end(v), x) - begin(v) - 1;
	}
 
  public:
	OfflineBIT2D(int n, vector<array<int, 2>> &todo) : n(n), vals(n + 1), bit(n + 1) {
		sort(begin(todo), end(todo),
		     [](const array<int, 2> &a, const array<int, 2> &b) -> bool {
			     return a[1] < b[1];
		     });
 
		for (int i = 1; i <= n; i++) { vals[i].push_back(0); }
		for (auto [r, c] : todo) {
			r++, c++;
			for (; r <= n; r += r & -r) {
				if (vals[r].back() != c) { vals[r].push_back(c); }
			}
		}
		for (int i = 1; i <= n; i++) { bit[i].resize(vals[i].size()); }
	}
 
	void add(int r, int c, T val) {
		r++, c++;
		for (; r <= n; r += r & -r) {
			int i = ind(vals[r], c);
			for (; i < bit[r].size(); i += i & -i) { bit[r][i] += val; }
		}
	}
 
	T rect_sum(int r, int c) {
		r++, c++;
		T sum = 0;
		for (; r > 0; r -= r & -r) {
			int i = ind(vals[r], c);
			for (; i > 0; i -= i & -i) { sum += bit[r][i]; }
		}
		return sum;
	}
 
	T rect_sum(int r1, int c1, int r2, int c2) {
		return rect_sum(r2, c2) - rect_sum(r2, c1 - 1) - rect_sum(r1 - 1, c2) +
		       rect_sum(r1 - 1, c1 - 1);
	}
};
// EndCodeSnip
 
int main() {
	int n;
	cin >> n;
	vector<int> a(n), p(n);
	for (int &i : a) { cin >> i; }
	for (int &i : p) { cin >> i, i--; }
 
	vector<array<int, 2>> upd(n);
	for (int i = 0; i < n; i++) { upd[i] = {p[i], a[p[i]]}; }
	OfflineBIT2D<ll> bit(n, upd);
 
	ll res = 0;
	const int mx = *max_element(begin(a), end(a));
	for (int i = 0; i < n; i++) {
		res += bit.rect_sum(0, a[p[i]] + 1, p[i] - 1, mx);
		res += bit.rect_sum(p[i] + 1, 0, n - 1, a[p[i]] - 1);
		cout << res << '\n';
		bit.add(p[i], a[p[i]], 1);
	}
}

Es un poco difícil pasar el problema de arriba dentro del límite de tiempo. Hay que usar entrada rápida (y no endl).

implementación de thecodingwizard con el BIT 2D offline de arriba

BIT 1D + divide y vencerás

La forma más rápida.

mencionado en este artículo
implementación (desprolija) de thecodingwizard basada en lo de arriba

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
Platinum	Friendcross	Normal	2DRQ, BIT	Solución
Platinum	Mowing the Field	Normal	2DRQ, BIT	—
APIO	2019 - Street Lamps	Normal	2DRQ, BIT	Solución

Árbol de Segmentos 2D

Un árbol de segmentos de árboles de segmentos (tal vez dispersos).

Recursos
Fuente	Recurso	Notas
CPH	28.2 (Sparse SegTree), 28.4 (2D)	Descripción breve

Implementación

Recursos
Fuente	Recurso	Notas
USACO	Analysis - Mowing the Field	Código
cp-algo	Simple 2D Segment Tree	Más código

Nota - Uso de memoria

De forma naive, insertar $N$ elementos en un árbol de segmentos disperso requiere memoria $\mathcal{O}(N\log C)$ , lo que da una cota de $\mathcal{O}(N\log^2C)$ para la memoria del árbol de segmentos 2D. Esto suele ser demasiado para $N=C=10^5$ y 256 MB (aunque alcanzó para “Mowing the Field” por el límite de memoria de 512MB). Formas posibles de sortear esto:

Usar arreglos de tamaño fijo en vez de punteros.
Reducir el uso de memoria del árbol de segmentos disperso a $\mathcal{O}(N)$ manteniendo el mismo tiempo de inserción $\mathcal{O}(N\log C)$ (ver la solución de IOI Game más abajo para los detalles).
Usar BBST en vez de árboles de segmentos dispersos. Memoria $\mathcal{O}(N)$ , tiempo de inserción $\mathcal{O}(N\log N)$ .

Problemas

También se pueden intentar los problemas de USACO de arriba.

Fuente	Nombre	Dificultad	Tags	Solución
POI	2006 - Tetris 3D	Difícil	2DRQ, Lazy SegTree	Solución
IOI	2013 - Game	Difícil	2DRQ, Sparse SegTree, Treap	Solución
JOI	2017 - Golf	Muy difícil	2DRQ, SegTree	Solución