Sabendo isso eu recomendo a leitura do artigo do Topcoder sobre BITs (em inglês). Não considero que seja necessário saber com detalhes por que ela funciona, o importante é saber como usá-la e quando usá-la, por isso eu não vou entrar nesse mérito. Mas se você tiver interesse em entender exatamente o funcionamento é importante saber como inteiros são representados em binário (complemento de 2).
Quem costuma usar árvores de intervalos completas deve se perguntar qual a vantagem de usar uma BIT, já que uma árvore pode fazer muito mais operações e que não dependem de começar do início. A resposta é basicamente uma: tamanho do código, o código inteiro da BIT tem umas 10 linhas, enquanto o código de uma árvore de intervalos tem bem mais do que isso. O código inteiro dela é (copiado do artigo do Topcoder):
int read(int idx){ int sum = 0; while (idx > 0){ sum += tree[idx]; idx -= (idx & -idx); } return sum; }
void update(int idx ,int val){ while (idx <= MaxVal){ tree[idx] += val; idx += (idx & -idx); } }
Começou a achar interessante a BIT agora? Acho que a maneira mais fácil de se pensar em uma BIT quando você está trabalhando com soma acumulada é imaginar realmente que ela é um vetor de soma acumulada. Ou seja, suponha que você tenha o seguinte vetor v={0, -1, 4, 2, 1, 2}, o vetor de soma acumulada seria sum={0, -1, 3, 5, 6, 8}.
Para inicializar a BIT é preciso zerar todas posições do vetor tree. Importante: Você não pode usar a posição 0 da BIT, pois ela não é capaz de lidar com esse valor (0 & -0 = 0, ou seja, ela entra em loop infinito).
Depois, é preciso adicionar cada elemento no vetor, chamando update(i, v[i]) para assim criar o vetor de soma acumulada. Depois disso, para saber a soma acumulada até um determinado ponto basta chamar read(i), ou então, se você quiser saber a soma de um intervalo[i,j] basta fazer read(j)-read(i-1).
Se você quiser trocar o valor de uma dada posição i de a para b basta chamar update(i, -a) e update(i, b), assim o valor anterior que estava naquela posição é removido e o novo valor é inserido.
Acredito que esse é o essencial. Vamos ver a aplicação dela no problema Interval Product da final brasileira da Maratona de 2012 então? O enunciado está aqui. Recomendo a leitura com calma para entender exatamente o que o problema pede.
A solução do problema começa com a identificação de que propriedade é interessante de ser usada: não é preciso saber o valor dos números para saber se o produto é positivo ou negativo, basta saber o sinal deles, se houver um número par de números ímpares no produto então o resultado vai ser positivo, caso contrário ele vai ser negativo. Além de perceber que o produto vai ser zero se algum dos valores multiplicados for zero.
Sendo assim a ideia é usar 2 BITs, uma para guardar o número acumulado de números ímpares e outra para guardar o número acumulado de zeros.
Para cada consulta deve-se então pegar o número de ímpares no intervalo e o número de zeros, usando a ideia explicada anteriormente, e fazer a verificação se o número é positivo, negativo ou zero.
Para atualizar também é bem simples, basta manter armazenado o valor de cada posição e quando uma posição é atualizada seguir a ideia explicada para mudar o valor de um elemento na BIT. Ou seja, se o valor anterior naquela posição tinha o mesmo sinal do novo então nada muda, mas se o valor mudou de negativo pra positivo é necessário subtrair 1 na BIT de negativos, se o valor mudar de positivo pra negativo então deve ser adicionado 1 na mesma BIT. Para atualizar a BIT de zeros uma ideia similar deve ser adotada.
Bom, espero que essa breve explicação da funcionalidade da BIT possa ajudar alguém, não ficou tão bom quanto eu queria que tivesse ficado, mas serve como mais um texto a respeito.
