Informática BIT - Solução Arranhã-Céu

Arranha-céu

Solução escrita por Caique Paiva

Conhecimento prévio necessário:

• Binary Indexed Tree

Esse problema é uma aplicação simples de BIT. Vamos codar uma BIT de soma, igual a feita na aula colocada no link acima, e nós sabemos que ela responde a query e faz o update em $O(log n)$. Além disso, vamos guardar o vetor atual, que guarda a quantidade de pessoas em cada apartamento. Na query, retornamos o valor de $query(pos)$ que ele nos dá, e no update, fazemos $update(pos, val - v[pos])$ com o valor e posição que eles no dá na query, e fazemos $v[pos] = val$.

Clique aqui para conferir o código