Ideia 08 - Sparse Table

Escrito por Thiago Mota

Pense no seguinte problema, dado um vetor de $N$ elementos iremos fazer $Q$ perguntas no vetor do tipo $[l, r]$ perguntando qual o menor valor do vetor no intervalo de $l$ até $r$ . Esse problema pode ser facilmente resolvido utilizando uma Segment Tree com a complexidade de $O(q \log n)$ para cada pergunta, mas nesse problema não temos update logo não é necessário o uso da Segment Tree, logo iremos resolver utilizando uma técnica de "programação dinâmica".

Iremos definir uma tabela $tab$ de tal forma que $tab(i, j)$ seja o menor valor no intervalo que começa em $i$ e tem tamanho $2^j$ , ou seja, para o vetor $v = [1, 5, 3, 6, 2]$ teremos a seguinte tabela:

$tab(1, 0) = 1 \: [1, 1]$

$tab(1, 1) = 1 \: [1, 2]$

$tab(1, 2) = 1 \: [1, 4]$

$tab(2, 0) = 5 \: [2, 2]$

$tab(2, 1) = 3 \: [2, 3]$

$tab(2, 2) = 2 \: [2, 5]$

$tab(3, 0) = 3 \: [3, 3]$

$tab(3, 1) = 3 \: [3, 4]$

$tab(4, 0) = 6 \: [4, 4]$

$tab(4, 1) = 2 \: [4, 5]$

$tab(5, 0) = 2 \: [5, 5]$

O tamanho dessa tabela será por volta de $O(n \log n)$ de memória, pois o segundo argumento só vai até o logaritmo do tamanho total.

Para computar essa tabela, iremos olhar paras os valores calculados anteriormente, olhe para a imagem:

Com isso, notamos que para calcular a $tab(i, j)$ podemos olhar o menor entre $tab(i, j-1)$ e $tab(k, j-1)$ , sendo $k$ o início do próximo intervalo, como o tamanho do intervalo é $2^{j-1}$ , o $k$ vai ser $i + 2^{j-1}$ , logo:

$tab(i, j) = min(tab(i, j-1), tab(i + 2^{j-1}, j-1))$

	// (n) é o tamanho do vetor
	// (log_n) é o log na base 2 de n
	// (v) é o vetor

	void computa() {
	// Caso inicial (tamanho 1, j = 0)
	for (int i = 1; i <= n; i++)
	tab[i][0] = v[i]; // Intervalo [i, i]

	for (int j = 1; j <= log_n; j++) {
	// Note que o for do j vem primeiro, isso é necessário pois
	// o jeito que tab(i, j) é calculado necessita que todos os i's
	// para j-1 estejam calculados.

	for (int i = 1; i <= n; i++) {
	// Checando se o intervalo que começa em i e tem tamanho 2^j existe.
	// Para isso basta checar se o fim do intervalo é menor ou igual a n
	if (i + (1<<j) - 1 > n) break;

	tab[i][j] = min(tab[i][j-1], tab[i + (1<<(j-1))][j-1]);
	}
	}
	}

view raw

ideia_08_01.cpp

hosted with ❤ by GitHub

Agora para calcular o mínimo de qualquer intervalo $[l, r]$ iremos simplesmente calcular o $k = \left \lfloor{\log_2 tam}\right \rfloor$ sendo $tam$ o tamanho do intervalo e pegar o mínimo dos intervalos que começam em $l$ e tem tamanho $2^k$ , ou seja, $tab(l, k)$ e outro que termina e $r$ e tem tamanho $2^k$ , ou seja, $tab(r - 2^k + 1, k)$ , tendo assim o mínimo do intervalo todo.

Segue o código:

	// (n) é o tamanho do vetor
	// (v) é o vetor

	int flog(int x) { // Calcula a parte inteira do log2 de x em O(1) ( para int )
	return 31 - __builtin_clz(x);
	}

	int flog(long long x) { // Calcula a parte inteira do log2 de x em O(1) ( para long long )
	return 63 - __builtin_clzll(x);
	}

	int query(int l, int r) {
	int k = flog(r - l + 1);

	return min(tab[l][k], tab[r - (1<<k) + 1][k]);
	}

view raw

ideia_08_02.cpp

hosted with ❤ by GitHub

Note que essa tabela só funciona pois o menor entre $x$ e $x$ é o próprio $x$ , pois existe sobreposição de intervalos na hora de fazer a query, ou seja, não funcionaria caso a pergunta fosse a soma do intervalo.

Essa ideia de montar uma tabela nas potências de dois tem o nome de Sparse Table e é muito utilizada na hora de calcular valores em uma árvore como no Menor Ancestral Comum, uma questão que usa uma ideia similar é a Crayfish Scrivener dá IOI 2012 caso você queira exercitar a ideia.