Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
// 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==tr){
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment