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:
- 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$$.
- 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:
https://gist.github.com/Rockbet/ec0be28a4a4530359aafdb6496f05a86
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:
https://gist.github.com/Rockbet/c2f7a15927bf686bec7b4b285ec1be56
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:
https://gist.github.com/Rockbet/306d29ecf172a0890ec167b4f0227636
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:
https://gist.github.com/Rockbet/7a310c4c38e31f3c45f65566064fab3f