Informática - Ideia 10

Escrito por Sofhia de Souza

As técnicas de busca binária na BIT (ou Binary Indexed Tree) e busca binária na SegTree (ou Segment Tree) são bastante úteis, uma vez que conseguem reduzir operações de complexidade $O(log^2N)$ para $O(logN)$. Para esse Noic Ideias, são necessário conhecimentos prévios de BIT e Segment Tree.

Busca Binária na BIT

Iremos iniciar com o seguinte problema:

Dado um vetor $V$, com $N$ valores inteiros positivos. Nós queremos realizar três tipos de operação:

1. Atualizar o valor de determinada posição.

2. Computar a soma de prefixos da posição $i$, sendo $i \leq N$.

3. Procurar por certa soma de prefixos no vetor.

É possível notar que podemos resolver o problema com uma BIT normal, onde as operações terão as seguintes complexidades:

1. $O(logN)$

2. $O(logN)$

3. $O(log^2N)$

Sendo as operações 1 e 2 operações normais de update e query na BIT, e a operação 3 uma busca binária, onde chamamos no máximo $logN$ queries para encontrar a soma de prefixos desejada. No entanto, dependendo do tempo limite da questão, a complexidade da operação 3 pode ser muito lenta. Para resolvermos esse problema, usaremos da técnica de Busca Binária na  BIT:

Faremos uma espécie de binary lifting na BIT. No binary lifting, nós adicionamos na nossa posição (ou "pulamos") em potências de 2, sempre da mais alta possível ($2^{logN}$) até a mais baixa possível ($2^0$), sem exceder o valor que queremos encontrar.

Vamos para um exemplo prático. Queremos encontrar a soma de prefixos $v$, que está na posição $pos$ da BIT. Para isso, iremos iniciar nossa busca com $pos = 0$ e $sum = 0$, sendo $sum$ o valor da minha soma de prefixos, e iremos incrementar essa posição em potências de 2, sempre começando da mais alta até a mais baixa, tendo certeza de que não estamos excedendo o valor de $v$. Ou seja, sempre que incrementamos, nós adicionamos à $pos$ a potência atual, e depois adicionamos à $sum$ o valor existente na $bit[pos]$ (só faremos isso caso $sum + bit[pos] <= v$). No fim, chegaremos exatamente na posição $pos$ desejada. Segue a implementação  para melhor entendimento:

Busca Binária na Segment Tree

Temos o seguinte problema:

Dado um vetor $V$ de tamanho $N$ e uma série de operações do tipo:

1. Atualizar a posição $p$ com o valor $x$

2. Imprimir o $k$-ésimo menor valor do vetor

Vemos que podemos resolver esse problema utilizando uma segtree de frequência normalmente, onde pra cada operação do tipo 1, fazemos normalmente o update em $O(logN)$, e pra cada operação do tipo 2, fazemos uma busca binária nos valores, e para cada um fazemos uma query para descobrir se esse valor corresponde ou não ao $k$-ésimo menor, dando uma complexidade de $O(log^2N)$. Dependendo do tempo limite do problema, essa complexidade da operação do tipo 2 pode ser um pouco lenta. Para resolver isso, usaremos a técnica que chamamos de Busca Binária na Segtree.

Suponha que, para cada nó da segtree, você saiba o número de valores presentes nesse determinado intervalo [$l$, $r$]. Você deseja encontrar o $k$-ésimo menor valor para esse intervalo. Se a contagem de elementos em seu filho esquerdo for pelo menos $k$, o $k$-ésimo menor elemento no intervalo [$l$, $r$] estará obrigatoriamente no filho esquerdo. Senão, ele estará no filho direito e será o ($k-qtd [esq]$)-ésimo menor valor do intervalo do filho direito, em que $qtd[esq]$ é o número de valores no intervalo correspondente ao filho esquerdo.

A ideia da Busca Binária na Segtree acaba sendo mais intuitiva do que a na BIT, e é bastante útil em vários tipos de problemas. Segue a implementação para melhor entendimento:

Ambas as técnicas são bastante utilizadas e aplicadas de várias formas diferentes. Um problema bastante interessante que engloba as duas técnicas é o Fila, da OBI 2015. Recomendamos que tentem pensar e resolver o problema, e caso não consigam, vejam a solução no Comentário Noic da OBi 2015.