Árvores de Segmentos

Começamos uma série de artigos de estruturas de querying (um nome um pouco vago que ficará mais concreto com o tempo) com uma estrutura de dados muito importante e poderosa, mas ao mesmo tempo extremamente simples. Com esta estrutura, conhecida como árvore de segmentos (ou do mais comum, em inglês, "segment tree"), vamos visitar um tipo de problema muito comum, mas também um tipo de primitiva que é muito útil em vários problemas.

Querying

A palavra query significa perguntar ou questionar. A ideia é dado um estado de uma estrutura ou sistema, pretende-se perguntar por alguma informação sobre ele. Vamos concretizar isto com um tipo de primitiva muito comum.

No problema do range minimum query é dada uma sequência de $N$ inteiros e é pedido o inteiro mínimo num dado intervalo da sequência original (também chamado de uma subarray). A solução trivial é simplesmente iterar por todos os elementos do intervalo e assim determinar o mínimo (uma solução $O(N)$ por query no pior caso), mas é possível fazer melhor fazendo algum tipo de pre-cálculo inteligente. Isto compensará a solução trivial se em vez de ser pedido o inteiro mínimo num só dado intervalo, forem pedidos de vários intervalos e além disso forem feitas alterações à sequência original.

É fácil descrever variações deste problema usando diferentes operações. Por exemplo, se em vez de querermos o mínimo querermos a soma de todos os elementos num dado intervalo, então temos um problema semelhante, conhecido por range sum query, cuja solução é muito parecida. De facto, desde que a operação a ser efetuada no intervalo seja associativa é possível usar árvores de segmentos, apesar de outros métodos terem restrições diferentes.

Este problema é recorrente como subproblema de vários outros problemas e é por isso muito importante e comum em provas de programação competitiva.

Árvore de Segmentos

Vamos então estudar uma possível solução que consiste em usar árvores de segmentos. Esta estrutura de dados guarda o resultado da operação a efetuar (o mínimo por exemplo) em diferentes intervalos (os segmentos) da sequência original. Para responder a uma query é feita uma decomposição do intervalo em subintervalos contidos na árvore de segmentos. Com a escolha certa de subintervalos, é possível gerar uma árvore que decompõe qualquer intervalo num máximo de $O(\log(N))$ intervalos.

Vamos então ver com mais detalhe como funciona a árvore de segmentos:

Com esta leitura já devem ter uma boa ideia de como funciona e de como se implementa uma árvore de segmentos. O código apresentado (na edição 1 do livro) mostra como construir e aceder à estrutura de dados. A função para atualizar um elemento da sequência é muito semelhante e pode ser facilmente implementável. Se quiserem ver um exemplo de uma implementação completa (que inclui atualização), podem experimentar este link, mas notem que há várias alternativas e esta não é necessariamente a melhor (nem a mais eficiente).

Se quiserem um reforço da informação anterior, o próximo artigo apresenta o mesmo com alguns detalhes diferentes:

Implementação

Agora que já têm as ferramentas base para trabalhar, vamos aplicá-las nalguns problemas e ver o seu poder.

Vamos começar com um problema de aplicação direta de uma árvore de segmentos, cuja operação base é o máximo (Range Maximum Query), que requer apenas queries. Atenção aos detalhes do problema, nomeadamente a solução requer que pensem um bocado antes de partirem logo para uma implementação. Se quiserem uma dica leiam este (artigo)[http://www.algorithmist.com/index.php/UVa_11235].

Agora que já experimentaram um problema usando árvores de segmentos, podem tentar um problema semelhante que apareceu na qualificação das ONI em 2009:

Variações

A árvore de segmentos base deve ser bastante óbvia agora, assim como a sua aplicação. Porém, como foi referido logo no início do artigo, é possível alterar a estrutura para suportar, por exemplo, operações diferentes. No artigo seguinte são referidas algumas propriedades gerais de árvores de segmentos assim como que tipos de operações suporta (nota: o código do artigo é um pouco confuso por isso é aconselhado que não se preocupem muito com ele).

Além do que o artigo indica, é possível fazer muito mais. Aglomerando informação diferente em cada nó da árvore, possivelmente de diferente naturezas, é possível obter funções complexas que se apliquem a tipos de queries e atualizações diferentes. Vejamos um exemplo simples com o próximo problema.

Se tiverem alguma dificuldade ou dúvida no problema podem sempre tentar ver o editorial do concurso onde o problema apareceu (link), mas antes de o fazerem tentem pensar como podem alterar a árvore de segmentos que já conhecem para incluir operações diferentes dependendo do nível.

Aplicações

Falta então ver como é que podemos usar estes conceitos em problemas "reais" de concursos. Vejamos dois problemas que podem ser resolvidos com estes conceitos, mas cujo uso de uma árvore de segmentos pode não ser evidente à primeira vista.

Caso seja necessário, fica o link do editorial do concurso onde surgiu o problema.

À medida que vão vendo mais problemas e que vão pensando em mais usos e modificações de árvores de segmentos, a sua utilização tornar-se-á cada vez mais evidente. Para terminar, vejamos um problema um pouco mais complexo (e por isso opcional) que pode ser resolvido modificando uma árvore de segmentos.

Se tiverem dúvidas, o editorial deste problema está um pouco confuso, mas o artigo seguinte apresenta, no início, uma solução mais concisa do problema, link.

O que se segue

Vimos o que são problemas de querying e uma possível solução para um subconjunto de problemas: a árvore de segmentos. Além de algumas variações, vimos como a aplicar em diferentes problemas. Além de outras variações possíveis, veremos em artigos futuros outras adaptações importantes (por exemplo, atualização de intervalos de elementos, em vez de simplesmente um único elemento) além de outras estruturas de dados que podem ser usadas em contextos diferentes (veremos árvores binárias indexadas, também conhecidas por Fenwick Trees, a técnica dos "baldes", ou buckets, entre outras).

Em artigos mais avançados, possivelmente do nível Olímpico, veremos também diferentes árvores de segmentos construídas de forma a serem usadas em problemas de tipos diferentes. Falaremos de estruturas persistentes, que são estruturas com "memória" das atualizações, mas também estruturas dinâmicas, entre outras.