Escrito por Anita Almeida e Pedro Racchetti
A estrutura de dados Segment Tree já foi introduzida em uma aula anterior aqui em nosso curso que você pode conferir aqui. Nessa aula citada, para apresentar a estrutura, o seguinte problema foi utilizado:
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]$$
A solução mais eficaz proposta foi utilizar a Segment Tree da seguinte forma:
- Iniciar com a raiz da Segment Tree.
- Se o índice do vetor a ser atualizado não estiver no intervalo do nó atual, retorne.
- Caso contrário, atualize o nó atual e repita a ação para os filhos desse nó.
Assim, a função $$update()$$ foi chamada para atualizar apenas um único valor no vetor, apesar dessa ação poder gerar várias atualizações na Segment Tree.
E se agora precisássemos atualizar um determinado intervalo de índices no vetor? Por exemplo, imagine adicionar 2 a todos os valores no intervalo dos índices 2 a 7 do vetor abaixo.
Obtemos:
Esse problema pode ser resolvido com Lazy Propagation, uma otimização para atualizar valores de um intervalo rapidamente.
Quando precisamos fazer muitas atualizações em um vetor e estas são feitas em um intervalo, podemos adiar algumas atualizações e realizá-las apenas quando necessárias. Considere o vetor $$V = \{1,3,5,7,9\}$$, temos a seguinte Segment Tree:
Considere agora o nó com valor 9 que representa a soma do intervalo $$[0,2] = {1,3,5}$$. Se precisarmos atualizar o intervalo [0,2], então precisamos atualizar esse nó com valor 9 e todos seus descendentes. A partir da Lazy Propagation, atualizamos apenas o nó com valor 9 e adiamos as atualizações de seus filhos, armazenando as informações de atualização em um vetor chamado $$lz[]$$. Iniciamos esse vetor com todos valores como 0. Conforme vamos atualizando os intervalos, se $$lz[i]=0$$ quer dizer que não há atualizações pendentes no nó $$i$$ da Segment Tree. Caso contrário, o valor de $$lz[i]$$ precisa ser adicionado ao nó $$i$$ na Segment Tree antes de consultar a soma do nó. Assim, antes de cada $$query()$$ temos que checar se tem algum nó que precisa ser atualizado.
Implementação
A implementação de uma Segment Tree com Propagação em Lazy, é de fato bastante parecida com a implementação de uma Segment Tree normal, exceto por algumas modificações. A primeira, e mais importante é que, como as operações de $$Update$$ são em um intervalo, temos que chamar sua recursão de forma parecida com a $$Query$$, atualizando ambos os filhos do nó atual. Além disso, temos que lidar com a propagação e manter o que foi propagado, e para isso, precisaremos de um novo vetor da árvore além do que já temos, nessa aula, o chamaremos de $$lz$$, e para de fato ocorrer a propagação usaremos a função $$Unlazy(no, tl, tr)$$, que irá atualizar o nó atual com o que foi. Essa função variará muito de problema a problema, mas possui um padrão que praticamente sempre será usado:
- Primeiro, verificamos que existe algo a ser propagado no nó
- Se não houver valores a serem propagados, podemos retornar
- Se houver algum valor, temos que diretamente atualizar o valor na Seg, seja lá como o problema pedir (analisaremos algumas situações posteriormente).
- Propagamos o valor para o $$lz$$ dos filhos do nó, quando existirem (podemos verificar isso com o tamanho do intervalo de $$no$$, sendo maior que 1, com certeza existirá filhos).
- Indicamos que em $$no$$, não há valor a ser propagado.
Note que como essa função atualiza o vetor principal da árvore, podemos apenas modificar $$lz$$ na $$Update$$, e chamar a função $$Unlazy$$. Além disso, um dos erros mais comuns quando implementando problemas de $$Lazy Propagation$$ é um nó não ser devidamente atualizado, logo é importante propagar sempre que se entrar em uma função de $$Update$$ e de $$Query$$.
Para melhor compreensão, iremos analisar dois problemas, e mostrar suas soluções e implementações:
Problema 1: Dado um vetor inicialmente zerado de $$n$$ posições, efetue as seguintes operações:
- Operação 1: troque todos os valores nas posições do vetor no intervalo de $$l$$ à $$r$$ para o inteiro $$x$$, com $$1 \leq x \leq 10^9$$ .
- Operação 2: imprima o valor máximo do vetor no intervalo de $$l$$ à $$r$$.
Para esse problema, podemos ver que em cada nó da árvore, precisamos apenas guardar o valor máximo que o intervalo representa. Então, como só atualizamos o $$lz$$ quando esse intervalo está inteiramente contido em um intervalo atualizado, a função $$Unlazy$$ é relativamente simples: basta mudar o vetor para o valor sendo propagado e propagar para os filhos. Segue o código com a implementação de cada função, para melhor compreensão desse ideia:
| // Os parametros da função unlazy são: | |
| // O nó atual, tl e tr, o intervalo que o nó atual abrange, | |
| void unlazy(int node, int tl, int tr){ | |
| // Se não houver valor a ser propagado, não precisamos propagar | |
| if(lz[node] == 0) return; | |
| // Primeiro, atualizamos a árvore com o novo valor | |
| tree[node] = lz[node]; | |
| // Se houver filhos, propagamos o vaor para eles | |
| if(tl != tr){ | |
| lz[2*node+1] = lz[node]; | |
| lz[2*node+2] = lz[node]; | |
| } | |
| // Indicamos que não há mais valores a serem propagados em node | |
| lz[node] = 0; | |
| } | |
| // Os parametros da função Update são: | |
| // O nó atual, tl e tr, o intervalo que o nó atual abrange, l e r, o intervalo que está sendo atualizado | |
| // e x, o o valor a ser atualizado. | |
| void update(int node, int tl, int tr, int l, int r, int v){ | |
| //LEMBRE-SE: Sempre chame a unlazy quando entrar numa função de update | |
| unlazy(node, tl, tr) | |
| // Se o intervalo abrangido pelo nó atual estiver completamente fora do intervalo a ser atualizado, | |
| // não temos que atualizá-lo. | |
| if(tl > r || tr < l) return; | |
| // Se o intervalo abrangido pelo nó estiver inteiramente contido no intervalo atualizado, | |
| // atualizaremos o nó. | |
| if(tl >= l && tr <= r){ | |
| lz[node] = x; | |
| unlazy(node, tl, tr); | |
| return; | |
| } | |
| // Caso contrário, declararemos mid como o índice que divide o nó atual em duas metades. | |
| int mid = (tl+tr)/2; | |
| //Agora, atualizaremos os filhos. | |
| update(2*node+1,tl,mid,l, r ,v); | |
| update(2*node+2,mid+1,tr,l,r,v); | |
| // Após termos atualizado os dois filhos, atualizaremos o valor do nó atual. | |
| tree[node] = max(tree[2*node + 1], tree[2*node + 2]); | |
| } | |
| // Os parametros da função Query são: | |
| // O nó atual, tl e tr, o intervalo que o nó atual abrange, l e r, o intervalo que queremos calcular. | |
| int query(int node, int tl, int tr, int l, int r){ | |
| //LEMBRE-SE: Sempre chame a unlazy quando entrar numa função de query | |
| unlazy(node, tl, tr) | |
| // Se o intervalo que o nó atual abrange estiver totalmente fora do intervalo de l até r, retornaremos 0. | |
| // Então, ou o início do intervalo do nó atual é maior que o fim dp intervalo que queremos calcular, ou | |
| // o fim do intervalo do nó atual é menor que o início do intervalo que queremos calcular. | |
| if(r<tl or l>tr) return 0; | |
| // Se o intervalo que o nó atual representa estiver totalmente dentro do intervalo de l até r, então | |
| // retornaremos o valor do nó atual. | |
| if(l<=tl and r>=tr) return tree[node]; | |
| // Caso contrário, declararemos mid como o índice que divide o nó atual em duas metades. | |
| int mid = (tl+tr)>>1; | |
| // Retornamos como resposta o máximo da resposta dos filhos do nó atual. | |
| return max(query(2*node+1, tl, mid, l, r),query(2*node+2, mid+1, tr, l, r)); | |
| } |
Problema 2: Dado um vetor inicialmente zerado de $$n$$ posições, efetuar as seguintes operações:
- Operação 1: Adicione $$x$$ a todos os valores nas posições do vetor no intervalo de $$l$$ à $$r$$.
- Operação 2: imprima a soma dos valores do vetor no intervalo de $$l$$ à $$r$$.
Nesse problema, devemos guardar o valor da soma do intervalo de cada nó, portanto não basta apenas somar diretamente o valor ao nó, já que se fizéssemos da forma lenta, atualizando valor por valor, sem propagação em lazy, o valor seria somado várias vezes no intervalo. Isso porém, é resolvível, já que sabemos que ele será somado exatamente o tamanho do intervalo vezes ao valor, ou seja, na função $$unlazy$$, iremos somar $$(r-l+1)\cdot x$$ ao valor real na árvore, propagando apenas $$x$$. Segue a implementação de cada função da árvore para esse problema.
| // Os parametros da função unlazy são: | |
| // O nó atual, tl e tr, o intervalo que o nó atual abrange, | |
| void unlazy(int node, int tl, int tr){ | |
| // Se não houver valor a ser propagado, não precisamos propagar | |
| if(lz[node] == 0) return; | |
| // Primeiro, atualizamos a árvore com o novo valor, somando ele vezes o número de vezes que aparecerá no intervalo | |
| tree[node] += (tr-tl+1)*lz[node]; | |
| // Se houver filhos, propagamos o vaor para eles, somando ao que já existe, pois pode ser que os filhos não | |
| // tenham sido atualizados desde a última vez que essa função foi chamada em node | |
| if(tl != tr){ | |
| lz[2*node+1] += lz[node]; | |
| lz[2*node+2] += lz[node]; | |
| } | |
| // Indicamos que não há mais valores a serem propagados em node | |
| lz[node] = 0; | |
| } | |
| // Os parametros da função Update são: | |
| // O nó atual, tl e tr, o intervalo que o nó atual abrange, l e r, o intervalo que está sendo atualizado | |
| // e v, o o valor a ser atualizado. | |
| void update(int node, int tl, int tr, int l, int r, int v){ | |
| //LEMBRE-SE: Sempre chame a unlazy quando entrar numa função de update | |
| unlazy(node, tl, tr) | |
| // Se o intervalo abrangido pelo nó atual estiver completamente fora do intervalo a ser atualizado, | |
| // não temos que atualizá-lo. | |
| if(tl > r || tr < l) return; | |
| // Se o intervalo abrangido pelo nó estiver inteiramente contido no intervalo atualizado, | |
| // atualizaremos o nó. | |
| if(tl >= l && tr <= r){ | |
| lz[node] += x; | |
| unlazy(node, tl, tr); | |
| return; | |
| } | |
| // Caso contrário, declararemos mid como o índice que divide o nó atual em duas metades. | |
| int mid = (tl+tr)/2; | |
| //Agora, atualizaremos os filhos. | |
| update(2*node+1,tl,mid,l, r ,v); | |
| update(2*node+2,mid+1,tr,l,r,v); | |
| // Após termos atualizado os dois filhos, atualizaremos o valor do nó atual. | |
| tree[node] = tree[2*node + 1] + tree[2*node + 2]; | |
| } | |
| // Os parametros da função Query são: | |
| // O nó atual, tl e tr, o intervalo que o nó atual abrange, l e r, o intervalo que queremos calcular. | |
| int query(int node, int tl, int tr, int l, int r){ | |
| //LEMBRE-SE: Sempre chame a unlazy quando entrar numa função de query | |
| unlazy(node, tl, tr) | |
| // Se o intervalo que o nó atual abrange estiver totalmente fora do intervalo de l até r, retornaremos 0. | |
| // Então, ou o início do intervalo do nó atual é maior que o fim dp intervalo que queremos calcular, ou | |
| // o fim do intervalo do nó atual é menor que o início do intervalo que queremos calcular. | |
| if(r<tl or l>tr) return 0; | |
| // Se o intervalo que o nó atual representa estiver totalmente dentro do intervalo de l até r, então | |
| // retornaremos o valor do nó atual. | |
| if(l<=tl and r>=tr) return tree[node]; | |
| // Caso contrário, declararemos mid como o índice que divide o nó atual em duas metades. | |
| int mid = (tl+tr)>>1; | |
| // Retornamos como resposta a soma da resposta dos filhos do nó atual. | |
| return query(2*node+1, tl, mid, l, r) + query(2*node+2, mid+1, tr, l, r); | |
| } |
Problemas adicionais:
Segue alguns problemas interessantes que usam propagação em lazy: