Aula por Leonardo Paes

Segment Tree, ou Árvore de Segmentos, é uma das estruturas de dados mais utilizadas na programação competitiva por conta da sua eficiência e versatilidade. Ela é, basicamente, uma árvore binária utilizada para armazenar intervalos. Uma árvore binária é uma árvore em que cada nó contém no máximo 2 filhos, chamados por filho da esquerda e filho da direita. Cada nó da Segment Tree representa apenas um intervalo.

Vamos pensar no seguinte problema para entendermos as Segment Trees:

Dado um vetor de $n$ posições $vet[0, 1, ..., n-1]$, nós devemos conseguir efetuar as seguintes operações:

1. Mudar o valor de uma posição específica do vetor para $x$. Formalmente, precisamos que, para algum $i$, $vet[i] = x, 0 \leq i \leq n-1$.
2. Encontrar a soma dos elementos de índice $l$ até $r$, onde $0 \leq l \leq r \leq n-1$. Formalmente, queremos: $\sum_{i=l}^{r} vet[i]$

Solução intuitiva 1:

Para atualizarmos a posição $i$ do vetor basta fazermos $vet[i]=x$, sendo $x$ o valor dado na operação. Para calcularmos a soma de um intervalo de $l$  até $r$, basta rodar um loop de $l$ até $r$ e ir incrementando a resposta com $vet[i]$, pois $l \leq i \leq r$. Nesta solução a operação $1$ tem complexidade $O(1)$ e a operação $2$ tem complexidade $O(n)$.

Solução intuitiva 2:

Utilizaremos um vetor auxiliar $pref$ que guarda as somas de prefixos de cada intervalo de $0$ até $i$, $0 \leq i \leq n-1$. Agora, a operação $2$ pode ser feita com complexidade $O(1)$, basta utilizarmos $pref[r] - pref[l-1]$ como a soma do intervalo de $l$ até $r$. Porém, para atualizarmos o vetor, precisaremos atualizar todas as $n$ posições do vetor $pref$, custando $O(n)$.

Conclusão:

A solução 1 é efetiva caso haja muitas operações de tipo $1$ e muito poucas de tipo $2$.

A solução 2 é efetiva caso haja muitas operações de tipo $2$ e muito poucas de tipo $1$.

E se no nosso problema houver um número aleatório de operações dos tipos $1$ e $2$, é possível respondermos ambas mais rapidamente? Com as Segment Trees, conseguimos efetuar ambas as operações em $O(\log_{} N)$.

Representação da Segment Tree:

As folhas, ou seja, nós sem nenhum filho, representam os intervalos onde $l = r$, que são os próprios valores de $vet$ dados pelo problema. Todos os outros nós representam a junção de algumas folhas. Essa junção pode variar de problema em problema. No nosso caso, ela é apenas a soma das folhas que estão abaixo de um nó.

Para guardarmos os valores de todos os nós da Segment Tree, utilizaremos um vetor $tree$. Para cada nó com índice $i$, seu filho da esquerda está na posição $2*i+1$ e o seu filho da direita está na posição $2*i+2$. Essa é uma maneira comumente  utilizada para representar árvores binárias no geral, não somente as Árvores de Segmentos.

Por exemplo, dado o vetor $vet[6]=$ { $1, 2, 4, 3, 5, 10$ }, a sua Segment Tree seria:

 

Website utilizado: http://visualgo.net

Embaixo de cada nó da árvore, temos dois números escritos dentro de colchetes, que são o $l$ e o $r$ do intervalo representado por eles. Como dito anteriormente, para $l = r$, o nó guarda o valor de $vet[l]$ e qualquer outro nó guarda a soma de todas as folhas abaixo dele, ou seja, a soma do valor dos seus filhos. A raiz da Segment Tree, por exemplo, guarda o número $25$, pois $25 = 7 + 18$, a soma do valor do seu filho da esquerda com o da direita.

Como a Segment Tree se parece no nosso vetor $tree$?

O primeiro valor guardado é a soma de todos os valores de $vet$, ou seja, a soma de todos os elementos de $vet$ no intervalo de $0$ até $n-1$. A partir daí, como definido anteriormente, devemos ter que $tree[2*i+1]$ guarde o valor de seu filho da esquerda e $tree[2*i+2]$ guarde o valor de seu filho da direita. Aplicando a definição recursivamente, teremos:

$tree[] =${$25, 7, 18, 3, 4, 8, 10, 1, 2, \emptyset, \emptyset, 3, 5, \emptyset, \emptyset$}.

Note que o símbolo $\emptyset$ representa que tal nó não existe na nossa árvore!

Construção da Segment Tree:

Utilizaremos o vetor $vet$ para a construção de sua respectiva Segment Tree.

Inicialmente sabemos calcular o valor de todas as folhas pois elas só utilizam dos valores de $vet$. Começaremos com o vetor $vet$ inteiro, ou seja, com a construção do nó que representa o vetor inteiro, com $l=0$ e $r=n-1$. Para criarmos todas as folhas iremos, recursivamente, dividir o nosso intervalo atual em duas metades, até que $l=r$. Quando $l=r$, basta fazermos: $tree[node]=vet[l]$ e retornarmos a função. Enquanto estivermos no processo de desempilhamento, ou seja, na "volta" da recursão, criaremos os outros nós da árvore. Para criarmos eles, basta dizermos que o valor deles é a soma dos valores de seus respectivos filhos, pois eles já foram criados previamente: $tree[node] = tree[2*node+1] + tree[2*node+2]$.

Como a Segment Tree é uma árvore binária, se considerarmos que seu vetor de origem tenha $n$ posições, o número de posições que o vetor que a representa terá, no máximo, $2*x - 1$ posições, onde x é a menor potência de $2$ maior ou igual a $n$. Por exemplo, se $n=6$, o tamanho do vetor que representa a sua Segment Tree terá $2*8-1 = 15$.

Código de exemplo da função Build, que constrói a Segment Tree:

Atualizando a Segment Tree:

Dado um índice $idx$ de $vet$ e um valor $x$, queremos atualizar a nossa Seg, abreviação de Segment Tree. Vamos fazer isso recursivamente. Se o nó atual é uma folha, então só iremos atualizá-lo se ele representa o intervalo de $idx$ até $idx$. Caso contrário, o nó atual não é uma folha. Então, se $idx$ se encontra dentro do intervalo do nó atual, iremos chamar a função update ou para o seu filho da direita ou para o seu filho da esquerda. Seja $mid$ o índice que divide o nó atual em duas partes. Se $idx \leq mid$, faremos o "update" no filho da esquerda, pois ele abrange o intervalo de $l$ até $mid$ e $idx$ se encontra nele. Caso contrário, atualizaremos o filho da direita, já que ele abrange o intervalo de $mid+1$ até $r$ e $idx$ se encontra nele. Após termos atualizado o filho correto, basta atualizarmos o nó atual. Para fazer isso é só dizer que: $tree[node] = tree[2*node+1] + tree[2*node+2]$.

Código de exemplo da função Update, que atualiza a Segment Tree:

Consultando a Segment Tree:

Dado um intervalo de $l$ até $r$, queremos saber a soma de todas os elementos do vetor $vet$ com posições de $l$ até $r$. Como fizemos no Build e no Update, iremos calcular a soma recursivamente. Se o nó atual esta totalmente fora do intervalo de $l$ até $r$, então retornaremos $0$, pois esse nó não nos interessa e $0$ não alterará a nossa soma. Se o nó atual esta totalmente dentro do intervalo de $l$ até $r$, então retornaremos o seu valor: $tree[node]$, pois esse intervalo faz parte da resposta. Caso contrário, só nos restaram nós que cobrem parcialmente o intervalo de $l$ até $r$. Para resolvermos esses casos, basta chamarmos a função para os filhos do nó atual e retornarmos a soma delas como resposta. É importante notar que, recursivamente, a nossa resposta final será a soma de um conjunto de nós da Segment Tree que inteiramente fazem parte do intervalo de $l$ até $r$.

Código de exemplo da função Query, que consulta a Segment Tree:

Complexidade de tempo das funções:

A Complexidade de tempo para construção da árvore é $O(n)$. Existem no total $2*n-1$ nós, e o valor de cada nó é calculado apenas uma vez na construção da árvore.

A Complexidade de tempo para consulta é $O(\log_{} n)$. Para consultar uma soma, processamos no máximo quatro nós em cada nível e o número de níveis é $\log_{} n$.

A complexidade de tempo da atualização também é $O(\log_{} n)$. Para atualizar o valor de uma folha, nós processamos um nó em cada nível e o número de níveis é

$\log_{} n$.

Código de exemplo da Segment Tree, sem comentários: