Segtree

Árvore de Segmento

A primeira utilização óbvia de uma árvore de segmento é uma RMQ, discutida de forma bacana no famoso artigo do Topcoder: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

(aqui deveria ter uma explicação sobre isso)

Problemas de árvore de segmento:

Lazy Propagation (ou Lazy Evaluation, como chamava o Andrey em Campinas):

Lazy propagation é uma técnica para você fazer range update em árvores de segmento, sem que seja O(n log n), como seria se você usasse o point update explicado acima. A ideia da técnica é você fazer o update do intervalo e marcar os filhos como "precisam de atualização". Aí, toda vez que você lê um nó, você verifica a flag de "precisa de update" antes e faz os updates necessários – TODA vez mesmo (veja o código do HORRIBLE, toda vez que eu leio tree[r], eu faço propagate(r…); antes). Existe uma variante da flag que indica que os filhos precisam ser atualizados, em vez do próprio nó, mas não é a que será usada nesse texto nem no código exemplo.

Então, o update quebra o intervalo de query até que o nó que você está estiver completamente dentro do intervalo de query. Quando você chega nesse ponto, você dá o update nesse nó e marca que os filhos precisam dar update.
Na hora que você lê o valor de um nó, você precisa propagar ele, ou seja, atualizar ele com o que faltava da flag e mover a flag para os filhos.

Duas coisas importantes para se ter na cabeça:
1. Quando o flag está diferente de 0, todos os nós da subárvore enraízada naquele nó precisam ser atualizados.
2. Toda vez que você precisar ler o valor de um nó, propague ele primeiro

Acho que está muito enrolado, vou dar um exemplo, segtree de [1,10]:

Update em [2,5]:
[1,10] quebra em: [1,5], [6,10], como não tem subintervalos em [6,10], desce só pra [1,5]
[1,5] quebra em: [1,2], [3,5].
O intervalo [3,5] está todo dentro do intervalo de query, então ele recebe o update e marcamos os dois filhos, [3,4] e [5,5], com a flag.
[1,2] quebra em: [1,1], [2,2]
O intervalo [2,2] recebe o update e não marca ninguém porque não tem filhos

Nós marcados: [3,4], [5,5]

Read no intervalo [4,5]:
[1,10] não tem flag, então não precisa de atualização
[1,10] quebra em: [1,5], [6,10], desce só pra [1,5]

[1,5] não tem flag
[1,5] quebra em [1,2], [3,5], desce só pra [3,5]

[3,5] não tem flag
[3,5] quebra em [3,4] e [5,5]

[5,5] deve receber atualização, por estar marcado com isso. Como ele não tem filhos, ele não precisa marcar ninguém e retorna o valor atualizado.

[3,4] tem flag, então deve ser atualizado e marcar os filhos [3,3] e [4,4]
[3,4] quebra em [3,3], [4,4], mas [3,3] está fora do intervalo de query, então é descartado

[4,4] tem flag, então recebe uma atualização, mas não move a flag pra ninguém (por não ter filhos) e retorna.

Nós marcados: [3,3]

Update em [3,4] (exemplo de update quando flags começam a interferir):
[1,10] não tem flag, então não precisa de atualização
[1,10] quebra em: [1,5], [6,10], desce só pra [1,5]

[1,5] não tem flag
[1,5] quebra em [1,2], [3,5], desce só pra [3,5]

[3,5] não tem flag
[3,5] quebra em [3,4] e [5,5]

[3,4] não tem flag
[3,4] é o intervalo que queremos atualizar, que depende do valor de [3,3] e [4,4],
então precisamos atualizar ambos os filhos (se eles tiverem flag) para fazer update nele.

[3,3] faz atualização e não marca ninguém por não ter filhos
[4,4] não tem flag

//Começa a percorrer a árvore em pós-ordem atualizando os intervalos maiores:
[3,4] = [3,3]+[4,4]
[3,5] = [3,4]+[5,5]
[1,5] = [1,2]+[3,5]
[1,10] = [1,5]+[6,10]

Problemas de árvore de segmento com lazy propagation:

Minha solução para o HORRIBLE: http://pastebin.com/TuvpPMBp
Solução do Maurício para o HORRIBLE: http://ideone.com/KeXgz

Minha solução para o HOMEM, que dá TL, mas é legível: http://pastebin.com/EK0mCpz6
Minha solução AC para o HOMEM: http://pastebin.com/mbMcSgp4

Segtree 2D (ou com mais dimensões):

A implementação de uma pode ser meio tricky, e me tomou uma semana e alguns emails pro Maurício para get it right (com o problema NKMOBILE, da IOI01). Vou deixar aqui meus códigos com os comentários do Maurício sobre para que, se vocês estiverem cometendo os mesmos erros, poderem saber o porquê.
Minha primeira implementação foi http://pastebin.com/2nSjQu9S

Emails do Maurício em relação a ela:
"Você parece estar dividindo os intervalos em lockstep (i.e. os dois
intervalos ao mesmo tempo). Segtree 2D não funciona assim, porque isso
daria complexidade muito alta: imagine, por exemplo, que um dos
intervalos tem tamanho 1 e o outro tem tamanho total; eu acho que seu
código tem complexidade linear pra essa consulta, e você pode
instrumentar o código pra descobrir você mesma. Você tem que rodar uma
query só na coordenada x, e iniciar uma query na coorenada y ao notar
que ql<=l && qr>=r na query original."
E
"Outra alternativa com boa complexidade eh fazer duas queries
unidimensionais (uma funcao so, chamada duas vezes) pra calcular os
indices dos O(log n) intervalos que decompoem cada um dos dois
intervalos da query, e depois fazer dois for aninhados pra somar todas
as celulas com os indices calculados no passo anterior. Up to you."

Minha segunda implementação foi: http://pastebin.com/mEDTWHwz
(pelo menos a segunda que eu mostrei pra ele, tiveram muitas in between).

Email de resposta:
" x, y;
l, b, r, t;

Remova isso pra conseguir 5 pontos. O resto dos pontos vem do fato de
que você está fazendo os updates em lockstep, e isso acaba não
atualizando as células todas: Pense no caso S = 4, e que você está
atualizando a célula (0,0); seu código atualiza os intervalos [0,3] x
[0,3], [0,1] x [0,1] e [0, 0] x [0, 0], mas certamente o intervalo
[0,3]x[0,0] também contém a célula (0,0), por exemplo."

Uma implementação de exemplo que o Maurício fez para me mostrar uma técnica: http://ideone.com/2xyB5
"Maurício: Eu usei uma técnica que eu acho que facilita a implementação bidimensional
A ideia é decompor cada um dos intervalos em separado
E depois loopar no produto cartesiano de tudo"

"Maurício: Tem duas coisas independentes a se copiar desse código e que eu aprendi da pior maneira possível
Maurício: Uma é a ideia de fazer uma rotina pra emitir os intervalos da decomposição
Funciona até pra segtree 1D, mas não é vantagem no caso 1D
Mas a mais importante, que é vantagem no caso 1D, é remover aqueles max() e min() da função recursiva
Aquilo só dá dor de cabeça na hora de ler o código
É menos line noise
É mais fácil de debugar também, especialmente se remover os parâmetros que são sempre passados iguais
Maurício: (Note que minha função recursiva tem três argumentos, ao invés de 1 mol deles)"

Nota: depois conferimos que a implementação comentada está correta, mas toma TLE nos últimos casos porque o TL do SPOJ está um bocado apertado (e possivelmente esperando uma solução usando BIT)

Aí a gente começou a discutir a implementação no Gtalk:

"me: nesse código estou dividindo os dois?

Maurício: No update sim

me: o.o
ah, sim, true
é porque eu codei uma versão com update e updateY
que eu não sabia como somar de volta
se você quiser, ainda tenho ela

Maurício: Você vai precisar dela sim
No updateY, você só soma tree[x][y] = tree[x][2*y+1] + tree[x][2*y+2]
E no update x faz tree[x][y] = tree[2*x+1][y] + tree[2*x+2][y]"

Minha terceira implementação: http://pastebin.com/GMZrsBHN

"Maurício: if (l==r) {
updateY(rootX,rootY,b,t,y,val);
return;
}
Você tem que chamar updateY incondicionalmente
Não só if(l==r)"

E a quarta, que dá só 10 pontos no NKMOBILE, mas está correta (dá TLE em grande parte dos casos), com a alteração acima: http://pastebin.com/eVu7SSzs

Discussão sobre o número de nós na segtree:
"me: ah, uma pergunta idiota
porque só tree[2*1024][2*1024]?
o tamanho, i mean
achei que o tamanho deveria ser n*log n

Maurício: Não, 2*proxima_potencia_de_2
A segtree só tem O(n) nós
(n folhas e portanto n-1 nós internos)
(2n-1 no total, mas eles podem estar indexados de um jeito estranho se o tamanho não for potência de 2)

me: po, mas aí não deveria ser 4?
Maurício: Desculpa
primeira_potencia_de_2_maior_ou_igual_a_n :P"

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License