Árvore de segmentos com RMQ

Uma árvore de segmentos é uma representação de segmentos de um vetor em uma árvore binária para que consultas em um dado segmento possam ser feitas de forma eficiente com complexidade de tempo O(log(N)), uma vantagem importante, visto que N pode ser excessivamente grande.

Mas é importante deixar claro que:

O custo de sua implementação só compensa os seus ganhos se o vetor for frequentemente atualizado e várias consultas sejam requeridas.

Para entender minha implementação, considere que:

• Nos foi dado um vetor arr de tamanho N.
• A árvore binária é armazenada como um vetor bt com tamanho de até 4*N, onde 0 é o índice da raiz, bt[v] o valor do vértice v, e bt[v*2+1] e bt[v*2+2] o valor de seus filhos à esquerda e à direita, respectivamente.

Está confuso? Calma! Abaixo vamos aplicá-la à uma RMQ para entender seu funcionamento de forma visual antes de ir para o código.

Range Minimum Query (RMQ)

Encontre o menor valor no sub-vetor {arr[i], …, arr[j]}, sendo 0 < i ≤ j< N.

build bt

A raiz, bt[0], representa o segmento [0 .. N-1] de arr. Para cada vértice representante de um segmento [l .. r], divide-o em dois segmentos menores: [l .. (l+r)/2] e [(l+r)/2+1 .. r].

Abaixo um exemplo da árvore de segmentos, após buildBT, com arr = {18, 17, 13, 19, 15, 11, 20} e N = 7.

Executamos bt.assign(4*N,0) e, em seguida, chamamos buildBT(0, 0, N-1) para construir os valores iniciais da nossa árvore de segmentos em O(N*log(N)).

range query

Como o algoritmo divide intervalos sucessivamente, conseguimos consultar um intervalo qualquer em complexidade de tempo O(log(N)).

Por exemplo, observe que rangeQuery(0, 0, N-1, 1, 3) nos retornará 13, como descrito no diagrama abaixo.

point update

Caso o vetor arr mude em alguma posição i, basta usar as mesmas ideias utilizadas acima para atualizar bt em O(log(N)).

Considerações finais

Por hoje é só. Vimos que uma árvore de segmentos nos permite fazer consultas eficientes, mas sua implementação é recursiva e, por isso, é preciso estar atento à muitos detalhes.

Agradeço a sua leitura, e espero que eu tenha contribuído em, pelo menos, colocar dúvidas na sua cabeça.

Referências bibliográficas:

• HALIM, Steven. HALIM, Felix. Competitive Programming 3: "the new lower bound of programming contests". Chapter 2.4.3. 2013.