seglazyprob2.cpp

// 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);
}