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:
https://gist.github.com/sofhiasouza/f97dcfd495136b5f0ec2b296975f5326
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:
https://gist.github.com/sofhiasouza/5bb58dfe86ba0a40a5ceeff9a8322716
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.