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:

	int bit[N];

	int busca_bit(int v)
	{
	int sum = 0;
	int pos = 0;

	for(int i = 30 ; i >= 0 ; i--)
	{
	if(pos + (1 << i) < N && sum + bit[pos + (1 << i)] <= v)
	{
	sum += bit[pos + (1 << i)];
	pos += (1 << i);
	}
	}

	return pos;
	}

view raw

busca_bit.cpp

hosted with

by GitHub

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:

	int st[4*maxn]; //minha segtree de frequencia

	int busca_seg(int p, int l, int r, int k)
	{
	if(l == r) return l; //se l e r são iguais, cheguei no valor que eu queria

	int meio = (l+r)/2;

	if(st[p*2] >= k) //se meu filho da esquerda tiver pelo menos k valores, o k-esimo esta nele
	{
	return busca_seg(p*2, l, meio, k);
	}

	else //senao, o k-esimo esta no meu filho da direita
	{
	return busca_seg(p2+1, meio+1, r, k-st[p2]);
	}
	}

view raw

busca_seg.cpp

hosted with

by GitHub

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.