Um pouco sobre Segment Tree’s

Segment Tree, ou Árvore de Segmentos para os Brazukas, é uma árvore binária de consulta muito útil para determinados tipos de problemas.

Vou dar uma introdução ao assunto neste post, então se você tem interesse, clique no link abaixo.

Motivação

Vamos montar um cenário. Imagine que você tem N valores inteiros, e de tempos em tempos você tem interesse em descobrir a soma de um intervalo desses valores.

Mais especificamente, você tem interesse em descobrir a soma de todos os números desde o i-ésimo até o j-ésimo inteiro, ou seja, N[i]+N[i+1]+…+N[j-1]+N[j], onde i <= j.

Por exemplo, seja N = 4, e os seguintes valores: 1, 5, 3 e 2.
Para i = 1 e j = 4, temos N[1]+N[2]+N[3]+N[4] = 1+5+3+2 = 11.
Para i = 2 e j = 3, temos N[2]+N[3] = 5+3 = 8.
Para i = 1 e j = 1, temos N[1] = 1.

É possível pensar em um algoritmo bem trivial para resolver esse problema, como se segue:

// (1) consulta trivial
int soma(int * N, int i, int j) {
    int res = 0;
    while(i <= j) {
        res += N[i];
        i++;
    }
    return res;
}

O nosso primeiro problema começa mesmo quando nos é dito que várias consultas serão efetuadas. Outras alternativas já foram pensadas para resolver o problema citado acima, tal como uma matriz de tamanho N por N contendo todas as possíveis respostas para todas as possíveis somas.

O nosso segundo problema aparece quando constantemente precisamos atualizar os valores da nossa sequência. A nossa matriz, por mais que tenha um tempo de resposta rápido para consultas, seria lenta para atualizações.

Apresento-lhes então a Segment Tree.

Insight

Alguns trechos da nossa consulta são tão comuns e repetitivos que talvez eu pudesse salvar algumas mini-consultas para ajudar na consulta final.

Por exemplo, imagine a seguinte sequência de inteiros:
segment_imagem1
Se eu fizesse uma consulta de 1 até 8, levaria 8 iterações no algoritmo citado acima (1).

Pra ajudar um pouco, eu poderia salvar algumas somas simples, tal como:
segment_imagem2

Agora, se eu fizesse uma consulta de 1 até 8, levaria apenas 4 iterações, se eu adaptasse o algoritmo acima de forma conveniente.

Bom, eu poderia fazer aquilo mais uma vez, e ficaria assim:
segment_imagem3

Agora, se eu fizesse uma consulta de 1 até 8, levaria apenas 2 iterações do nosso algoritmo modificado.

E, finalmente, mais uma modificação pra fechar com chave de ouro.
segment_imagem4

Eis a nossa Segment Tree  : )

Bom, nossos problemas com as consultas de 1 até 8 estão resolvidos. Generalizando, nossos problemas com consultas de 1 até N estão resolvidos. Antes precisávamos de N iterações, e agora só de 1.

Agora nos resta tratar os casos onde nossas consultas não são necessariamente de 1 até N. Na imagem acima, como eu faria pra consultar a soma de 2 até 7? Usaríamos o algoritmo trivial (1)?

Se explorarmos um pouco, vamos perceber que a nossa Segment Tree não apenas é útil para consultas do tipo 1 até N, mas sim para todas as possíveis consultas que você precisar. Vamos discutir isso abaixo.

Estrutura

Antes de mais nada, vamos convencionar os termos empregados nos elementos da nossa Segment Tree. É importante ter em mente que ela é uma árvore binária, logo aplica-se aqui termos semelhantes aos aplicados às árvores binárias.
segment_imagem5

[1] Nós: Elementos da árvore que representam um determinado segmento.
[2] Pai e Filho: Relacionamento direto entre dois nós. Um filho sempre cobre um segmento menor que o Pai.
[3] Raiz: O nó principal da árvore, que representa o segmento que inclui todas as posições da nossa sequência de valores.
[4] Folha: Nó que representa um único valor da nossa sequência de valores.

Representação

As imagens da Segment Tree que a gente viu acima nos mostrava os nós contendo os valores que cada segmento cobria, mas não deixava explícito o segmento em si. De modo geral, uma Segment Tree é explicitamente como mostra a imagem abaixo, com cada nó representando um segmento distinto. Vamos lá, passe o mouse.
Se você está lendo isso, por favor atualize seu navegador.

Essa representação deixa mais claro quais nós serão úteis para quais tipos de consultas.

Por exemplo, se desejamos realizar uma soma dos valores de 1 até 8, temos em mão o nó 1, como vimos anteriormente.
Se desejarmos realizar uma soma dos valores de 1 até 4, temos o nó 2.
Se desejarmos realizar uma soma dos valores de 3 até 4, temos o nó 5.

E se desejarmos a soma dos valores de 2 até 4? Essa consulta não tem um nó só pra ela, então aqui precisamos realmente somar alguns nós distintos, no caso o 9 e o 5. Ainda assim, são só 2 nós, no lugar de 3.

Consultas

Como vimos acima, algumas consultas são mais trabalhosas de serem feitas.

O algoritmo de consulta na Segment Tree tem um comportamento recursivo, e encontra três situações diferentes:
[1] O segmento do nó atual está completamente fora do intervalo da consulta.
[2] O segmento do nó atual está completamente contido no intervalo da consulta.
[3] O segmento do nó atual está parcialmente contido no intervalo da consulta.

Podemos rabiscar um algoritmo para capturar estas três situações (assuma que esta struct existe):

// (2) consulta quase completa
int consulta(struct No * atual, int i, int j) {
    // [1] completamente fora
    if(j < atual->esq || atual->dir < i) {
        //...
    }
    // [2] completamente contido
    else if(i <= atual->esq && atual->dir <= j) {
        //...
    }
    // [3] parcialmente contido
    else {
        //...
    }
}

Cada uma destas situações tem uma reação diferente do algoritmo, sendo elas:

[1] Completamente fora: Se entramos em um nó que não cobre nenhum elemento da consulta, então podemos supor que entramos ali “por engano”. Como resultado, podemos retornar um valor que indique que não há nada ali. No caso da soma, podemos retornar 0.

[2] Completamente contido: Se entramos em um nó, o qual os elementos que ele cobre são do interesse da consulta, então demos a sorte grande. Como resultado, podemos retornar o que aquele nó sabe sobre a soma abaixo dele.

[3] Parcialmente contido: Esse é o caso mais delicado. Se entramos em um nó que cobre apenas alguns elementos da consulta, então não podemos ignorar e retornar 0, assim como não podemos retornar a soma de todos os elementos abaixo. O resultado é um meio termo. Chamamos recursivamente ambos os filhos do nó em questão, os quais vão reagir de acordo com alguma dessas situações acima e nos dizer com precisão qual a soma que buscamos.

Podemos então incrementar nosso algoritmo anterior:

// (3) consulta completa
int consulta(struct No * atual, int i, int j) {
    // [1] completamente fora
    if(j < atual->esq || atual->dir < i) {
        return 0;
    }
    // [2] completamente contido
    else if(i <= atual->esq && atual->dir <= j) {
        return atual->soma;
    }
    // [3] parcialmente contido
    else {
        return consulta(atual->filho_esq, i, j) + consulta(atual->filho_dir, i, j);
    }
}

Já temos nosso algoritmo de consulta  : )

Construindo

No nosso último algoritmo (3) nós assumimos que uma certa struct existia, e esperançosamente assumimos que tudo estava em ordem (os valores, os ponteiros, etc). Agora vamos voltar um pouco e realmente fazer isso.

[Existem mil e uma maneiras de se montar essa árvore. A que eu vou mostrar aqui não necessariamente é a minha preferida, mas acredito que seja a mais intuitiva.]

O processo de construção será recursivo. Recebemos como parâmetro o intervalo que um nó vai cobrir, e devolvemos o ponteiro para este nó. Dentro de nossa função podemos encontrar duas situações:
[1] O nó que vamos criar será uma folha. Nesse caso, o segmento que esse nó cobre é de apenas um valor.
[2] O nó que vamos criar não será uma folha. Nesse caso, o segmento que esse nó cobre envolve mais de um valor. Como esse nó terá filhos, precisaremos chamar recursivamente nossa função para criar esses filhos, e então podemos completar o processo.

Nosso algoritmo ficará assim:

// (4) construindo a segment tree
struct No * constroi(int * vetor, int esq, int dir) {
    // lembre-se de incluir stdlib.h
    struct No * atual = (struct No *) malloc(sizeof(struct No));

    atual->esq = esq;
    atual->dir = dir;
    
    // [1] nó folha
    if(esq == dir) {
        atual->filho_esq = NULL;
        atual->filho_dir = NULL;
        
        // o intervalo é de um elemento, logo a soma é o elemento em si.
        atual->soma = vetor[esq];
    }
    // [2] nó não folha
    else {
        int meio = (esq+dir)/2;
        atual->filho_esq = constroi(vetor, esq, meio);
        atual->filho_dir = constroi(vetor, meio+1, dir);
        
        // a soma desse intervalo é igual a soma do intervalo dos filhos.
        atual->soma = atual->filho_esq->soma + atual->filho_dir->soma;
    }
    
    return atual;
}

...
int vetor[5] = {-1, 1, 3, 4, 2};
struct No * raiz = constroi(vetor, 1, 4);

// o primeiro valor de vetor, o -1, será ignorado =/
// idealmente deveríamos indexar tudo começando em 0,
// mas agora é tarde pra eu mudar tudo que eu escrevi :P

Vamos dar atençao à variável meio. Ela é crucial para que a nossa árvore seja o mais próximo possível de balanceada e completa. Dado um intervalo, a variável meio divide esse intervalo e atribui cada um desses menores intervalos para cada um dos filhos do nó atual.

Temos agora nosso algoritmo para construir a árvore  : )

[Se quiser testá-la, pode chamar esta função, também conhecida como Percurso Pós-Ordem.]

Atualizando

Estamos quase prontos. Nossa última preocupação com a árvore é: o que acontece com ela se eu quiser atualizar um valor?

Todos os nós que incluem o valor alterado no seu segmento devem ser alterados, e não apenas a folha. Logo, precisamos pensar em uma forma bacana de fazer tudo isso.

O interessante da Segment Tree é que o algoritmo para atualizar é muito semelhante ao algoritmo para Consultar (3). O algoritmo será recursivo, as três situações citadas no algoritmo (3) se repetem, e o que mudam são as reações.

[1] Como estamos atualizando a árvore, precisamos de tanta informação dos filhos quanto possível. Logo, mesmo que tenhamos entrado em um nó “por engano”, vamos retornar o valor dele para que o nó pai possa-o somar com os outros nós.

[2] Quando chegarmos no nó de destino, nós não somente o retornaremos, mas antes disso iremos atualizá-lo. O retorno é crucial para que os nós estritamente acima dele possam ser atualizados também.

[3] Essa situação continua mais delicada. Se o segmento do nosso nó cobre apenas um dos elementos que devem ser atualizados, então chamamos recursivamente o processo, e atualizamos a soma do nó para o retorno dos filhos.

// (5) atualiza o i-ésimo elemento para o valor v
int atualiza(struct No * atual, int i, int v) {
    // [1] completamente fora
    if(i < atual->esq || atual->dir < i) {
        return atual->soma;
    }
    // [2] completamente contido
    else if(i <= atual->esq && atual->dir <= i) {
        atual->soma = v;
        return atual->soma;
    }
    // [3] parcialmente contido
    else {
        atual->soma = atualiza(atual->filho_esq, i, v) + atualiza(atual->filho_dir, i, v);
        return atual->soma;
    }
}

Temos o nosso algoritmo para atualizar a árvore  : )

Conclusão

Eu não vou entrar em muitos detalhes, mas as consultas e atualizações aplicadas na Segment Tree tem complexidade O(lg N), onde N é o número de elementos no vetor. Essa complexidade é muito atraente, comparada à complexidade O(N) da consulta do algoritmo trivial, porém não muito atraente comparada à complexidade O(1) de atualização do algoritmo trivial.

Esse trade-off deve ser pensado conforme o contexto do problema que se deseja resolver. Posso adiantar que conforme o número de consultas sobe, mais vale a pena usar a Segment Tree.

Existem inúmeras variações de propósito e implementação da Segment Tree, que vão desde Multi-Dimensional Segment Tree’s até Lazy Propagation. Quem sabe um dia eu falo sobre eles aqui no blog.

 

Espero que esta introdução tenha sido útil.
Qualquer dúvida, sugestão ou crítica, por favor deixem um comentário abaixo.

5 ideias sobre “Um pouco sobre Segment Tree’s”

  1. Cara voce salvou minha vida em um trabalho, sua explicação e ótima, muito melhor que desses sites em ingles que usam operador de bits e ponteiros de outra forma. Parabéns. Explicação muito boa para quem está aprendendo.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *