Segment Tree Query.cpp

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