Informática – Ideia 01

Escrito por Lúcio Cardoso:

A técnica de compressão de coordenadas consiste, essencialmente, em mapear valores grandes dados em um problema para valores menores, a fim de reduzir gastos de memória e tempo. Vamos ilustrar a ideia com os seguintes exemplos:

Exemplo 1

Dado um vetor $$V$$ de $$N$$ números inteiros, calcule a quantidade de inversões em $$V$$, isto é, a quantidade de pares $$(i, j)$$ tais que $$i < j$$ e $$V[i] > V[j]$$.

Restrições: $$N \leq 10^5$$ e $$1 \leq V[i] \leq 10^9, \forall i \leq N$$.

Solução: Perceba que a quantidade total de inversões em $$V$$ é o mesmo que o somatório, para cada índice $$i$$, da quantidade de inversões que $$i$$ participa, ou seja, a quantidade de índices $$j$$ tais que $$i < j$$ e $$V[i] > V[j]$$. Para calcular isso, usaremos a estrutura de dados BIT (ou Binary Indexed Tree) da seguinte maneira: Criamos uma BIT onde cada um de seus índices guardará a quantidade de números em $$V$$ com valor igual a tal índice. De início, deixamos a BIT vazia e iteramos por cada posição $$i$$ do vetor, começando de $$N$$ e indo até 1. Assim, para descobrir de quantas inversões $$i$$ participa, basta calcular a soma dos valores desde o índice 1 ao $$V[i]-1$$ na BIT (o total de números menores que $$V[i]$$ até o momento). Depois, acrescentamos 1 ao índice $$V[i]$$ da estrutura, realizando o mesmo procedimento nos índices seguintes. Como a BIT realiza as duas operações de soma e atualização em $$O(\log{}n)$$, a complexidade final será $$O(n\log{}n)$$. Porém, a BIT precisa de uma posição reservada para cada um dos valores em $$V$$, que podem ser muito grandes (até $$10^9$$), e já que criar uma BIT com $$10^9$$ elementos é muito custoso, precisamos de outra solução.

Observe que como a quantidade de números distintos em $$V$$ é no máximo $$N$$, o vetor da BIT possui muitos “espaços vazios”. Além disso, o valor de cada elemento em $$V$$ é irrelevante; o que nos interessa ao calcular as inversões são apenas as relações ($$>$$ ou $$<$$) entre tais valores. Queremos então reduzir (comprimir) os números no vetor sem modificar as relações entre eles.

Para isso, vamos inserir cada valor de $$V$$ em um vetor auxiliar e então ordená-lo. Depois, mapeamos cada número neste vetor para um número menor de acordo com a ordem presente (ou seja, o menor número será mapeado para 1, o segundo menor para 2, etc.), comprimindo, assim, os valores de $$V$$. Podemos, assim, substituir cada um dos números no vetor original pelos seus respectivos valores mapeados, pois como o vetor auxiliar foi ordenado, as relações entre os números foram mantidas. Utilizando o próprio map do C++, é possível realizar a compressão desejada em $$O(N\log{}N)$$, e já que o maior valor comprimido de um número em $$V$$ será $$N$$, podemos usar a BIT seguindo o mesmo algoritmo descrito acima. A complexidade final será $$O(N\log{}N)$$. Confira o código para melhor entendimento:

https://gist.github.com/luciocf/6194e1ee84611ef45a13bfdd02ee5e84

Exemplo 2

Temos um vetor $$V$$ de $$N$$ inteiros com seus valores inicialmente iguais a 0. São dados $$M$$ pares $$(i, x)$$ $$(x \in \mathbb{Z}_+^*)$$ indicando que o valor de $$V[i]$$ foi atualizado para $$x$$. Os pares são dados em ordem estritamente crescente de $$i$$. Após isso, $$K$$ perguntas serão feitas, sendo representandas por um par $$(l, r)$$. Para cada pergunta, calcule a soma dos valores em $$V$$ com índices entre (e incluindo) $$l$$ e $$r$$.

Restrições: $$N \leq 10^9, M \leq 10^5, K \leq 10^5$$.

Solução: Novamente, não é eficiente guardar o vetor $$V$$, já que o valor de $$N$$ pode ser muito grande. No entanto, há muitos números iguais a 0 no vetor, e como nenhum deles irá contribuir para a resposta das perguntas, podemos enxergá-los como “gaps”. Vamos então fazer uma compressão apenas com as posições dadas nos $$M$$ pares, inserindo cada um deles em um vetor $$C$$ na ordem em que são dados. Note, assim, que $$C$$ já estará ordenado pelo valor $$i$$ (o primeiro elemento) de cada par. Feito isso, comprimimos as $$M$$ posições dadas, já que pela descrição do problema, são todas distintas (considere que o valor mapeado do índice $$i$$ num par em $$C$$ é a própria posição do par neste vetor).

Porém, os números nos índices $$l$$ e $$r$$ dados nas perguntas podem ser 0, e, consequentemente, não serão considerados na compressão; logo, a ordem relativa de tais índices com aqueles em $$C$$ será perdida. Apesar disso, note que se o valor no índice $$l$$ de uma pergunta, de fato, for 0, a soma no intervalo $$[l…r]$$ será a mesma que no intervalo $$[a…r]$$, onde $$a$$ é o primeiro índice em $$V$$ — maior ou igual a $$l$$ —, cujo valor no vetor é positivo. Isso vale porque todos os números entre $$a$$ e $$l$$ são 0. De maneira similar para $$r$$, se o valor em $$r$$ é 0, a soma em $$[l…r]$$ será a mesma que em $$[l…b]$$, onde $$b$$ é último índice em $$V$$ — menor ou igual a $$r$$ —, cujo valor no vetor é positivo. É possível encontrar os valores mapeados de $$a$$ e $$b$$ em $$O(\log{}M)$$ fazendo-se uma busca binária no vetor $$C$$, para cada uma das perguntas (mais detalhes no código abaixo). De tal forma, conseguimos respondê-las trabalhando apenas com índices do vetor $$C$$.

A fim de finalizar o problema, precisamos calcular a soma dos valores entre dois índices $$l$$ e $$r$$ quaisquer em $$C$$. Se $$x_i$$ for o valor $$x$$ do $$i$$-ésimo par em $$C$$, então observe que

\[\sum_{i=l}^r x_i = \sum_{i=1}^r x_i – \sum_{i=1}^{l-1} x_i\]

Portanto, se $$soma[i]$$ é igual à soma dos valores $$x$$ desde a posição 1 até $$i$$,

\[\sum_{i=l}^r x_i = soma[r] – soma[l-1]\]

Logo, é possível calcular a soma referida acima em $$O(1)$$, precalculando o vetor $$soma$$ para cada posição no vetor com complexidade $$O(M)$$ (basta ver que $$soma[i] = soma[i-1] + x_i)$$. Esta técnica é bastante útil e é conhecida como soma de prefixos. A complexidade final do problema será $$O(K\log{}M)$$, devido à busca binária realizada em cada uma das $$K$$ perguntas. Confira o código abaixo para melhor entendimento:

https://gist.github.com/luciocf/8c680e048c6efc9f05b84b80aa3ef8d9

&nbsp

Problemas para praticar

Obs.: Os problemas acima utilizam compressão de coordenadas de alguma maneira, porém podem precisar de alguma estrutura de dados (como BIT ou Segment Tree) ou outra técnica.