Por Samyra Almeida
Para resolver esse problema é necessário conhecimento sobre a estrutura da segmente tree com lazy propagation e saber linearizar uma árvore usando os tempos de entrada e saída da DFS.
Vamos definir o nível de um nó o número de arestas no caminho da raiz para o nó. Raiz (nó 1) está no nível 1, os filhos da raiz estão no nível 2, os filhos dos filhos da raiz estão no nível 3 e assim por diante.
Agora, suponha que você queira fazer uma operação do tipo 1 para um nó $$x$$. Quais nós da subárvore de $$x$$ serão adicionados $$+val$$ (um valor positivo)? Obviamente, $$x$$ será o primeiro, sendo localizado no nível $$H$$. Filhos de $$x$$, localizado no nível $$H + 1$$, será adicionado $$-val$$. Filhos de filhos, localizados no nível $$H + 2$$, serão adicionados valor + val novamente. Assim, os nós da subárvore de $$x$$ localizados nos níveis $$H, H + 2, H + 4,$$ $$…$$ serão adicionados a $$+val$$ e os nós localizados nos níveis $$H + 1, H + 3, H + 5,$$ $$…$$ serão adicionados $$-val$$. Note que para um $$x$$ fixo, em um nível $$H$$, e y um nó da subárvore de $$x$$, no nível $$H2$$. Se $$H$$ e $$H2$$ tiverem a mesma paridade, $$+val$$ será adicionado a $$y$$. Caso contrário, $$-val$$ será adicionado a $$y$$.
A partir daqui, temos a ideia de dividir os nós da árvore em dois conjuntos – os que estão localizados no nível par e os que estão localizados no nível ímpar. O que ainda torna o problema difícil de resolver? O fato de termos uma árvore. Se os nós de uma subárvore fossem uma sequência contígua em vez de alguns nós de uma árvore, o problema seria mais simples: o problema reduziria para adicionar/subtrair valores a todos os elementos de um subarray e consultar um valor atual de um elemento de matriz. Então, como podemos transformar árvore em um array, como para um nó $$x$$, todos os nós da subárvore de $$x$$ para ser um subarray de array?
A resposta é sim. Podemos fazer isso utilizando as propriedades de busca na DFS. Antes de continuar lendo, verifique se você sabe o que é o tempo de descoberta e o horário de término em uma busca na DFS. Vamos construir 3 arrays agora – $$descoberta[]$$, representando nós na ordem de seus tempos de descoberta, $$entrada[]$$ $$=$$ para um nó, tempo em que foi descoberto e $$saida[]$$ $$=$$ qual é a última vez que um nó da de sua subárvore foi descoberto antes que esse nó seja concluído. Para uma subárvore de $$x$$, todos os nós na subárvore são nós em descoberta estão entre as posições de $$entrada[x]$$ a $$saida[x]$$.
Exemplo: suponha que você tenha árvore $$1$$ $$-$$ $$5;$$ $$1$$ $$-$$ $$6;$$ $$6$$ $$-$$ $$7;$$ $$6$$ $$-$$ $$4;$$ $$4$$ $$-$$ $$2;$$ $$4$$ $$-$$ $$3$$.
- $$descoberta$$ é {$$1, 5, 6, 7, 4, 2, 3$$}.
- $$entrada$$ é {$$1, 6, 7, 5, 2, 3, 4$$}.
- $$saida$$ é {$$7, 6, 7, 7, 2, 7, 4$$}.
Qual é a subárvore do nó 6? elementos de descoberta da posição $$entrada[6]$$ ao $$saida[6]$$. Neste caso, de $$3$$ a $$7$$, os elementos $${6, 7, 4, 2, 3}$$.
Agora, reduzimos o problema para: você recebe um vetor $$A$$. você pode executar duas operações:
- $$1$$ $$-$$ aumenta todos os elementos de um intervalo $$[x,$$ $$y]$$ para um valor $$val$$ ($$val$$ pode ser negativo, para tratar subtrações)
- $$2$$ $$-$$ consulta o valor atual de um elemento da posição $$pos$$.
Podemos realizar essas operações utilizando a estrutura da segment tree com lazy propagation, se você não conhece essa estrutura, leia sobre elas antes de prosseguir.
Iremos criar duas segment tree de soma uma para os nós de nível par e outra para os de nível ímpar. Na função $$update$$ atualizamos um intervalo $$[x$$, $$y]$$ iremos realizar a atualização nas duas segs e nas duas lazys simultanealmente, definindo $$+val$$ para a seg ímpar e $$-val$$ para a par, e ao consultar o valor de um nó ao chegar em uma folha da seg, basta checarmos a paridade do nível do nó e então retornamos seu o valor em sua respectiva seg.
Para maior compreensão leia atentamente o código solução abaixo:
https://gist.github.com/samyravitoria/c7361285d569a13617b0f1ab42bf6d84
Deixe um comentário