Estruturas de Dados 05 - Segment Tree com Lazy Propagation

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:

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]$

A solução mais eficaz proposta foi utilizar a Segment Tree da seguinte forma:

1. Iniciar com a raiz da Segment Tree.
2. Se o índice do vetor a ser atualizado não estiver no intervalo do nó atual, retorne.
3. 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:

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.

Problemas adicionais:

Segue alguns problemas interessantes que usam propagação em lazy:

• https://www.spoj.com/problems/LITE/
• https://www.spoj.com/problems/HORRIBLE/
• https://br.spoj.com/problems/HOMEM/
• https://codeforces.com/edu/course/2/lesson/5/1/practice/contest/279634/problem/C
• https://codeforces.com/edu/course/2/lesson/5/3/practice/contest/280799/problem/A