Calculadora de índices Fenwick
Digite um índice e veja como uma árvore de Fenwick se move a partir dele: o 13 é 1101 em binário, seu bit mais baixo vale 1, o passo de atualização leva ao 14 e o de consulta ao 12. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
Exemplo resolvido
- Índice
- 13
- Tamanho
- 16
- Bit ativo mais baixo
- 1
- Próximo da atualização
- 14
- Pai da consulta
- 12
- Binário
- 0b1101
Uma árvore de Fenwick, também chamada binary indexed tree, responde somas de prefixo e atualizações pontuais em tempo logarítmico ao armazenar intervalos parciais cujos comprimentos são potências de dois. Cada passo de navegação depende de um truque de bits: o bit menos significativo do índice 1-based atual, escrito lsb igual a i AND o negativo de i em complemento de dois. Somar esse lsb percorre a cadeia de atualização; subtraí-lo percorre a cadeia de consulta de prefixo. Estudantes, programadores competitivos e autores de bibliotecas precisam desses índices pai e próximo sem rederivar as identidades sob pressão de prova. Esta calculadora de índices da árvore de Fenwick aceita um índice positivo i e, opcionalmente, um tamanho de árvore n; devolve o lsb, o próximo de atualização e o pai de consulta em um passo, formas binárias para ensino e, quando n é informado, o caminho completo de atualização e de consulta do código BIT clássico.
Como os índices de Fenwick usam o bit menos significativo
Em uma binary indexed tree com índices 1-based, a célula no índice i é responsável por um segmento contíguo do array subjacente cujo comprimento é o bit menos significativo de i. Esse comprimento é calculado como lsb igual a i AND a negação em complemento de dois de i, frequentemente escrito i and minus i em linguagens com aritmética modular sobre inteiros de largura fixa.
Geometricamente, inverter todos os bits abaixo do um menos significativo isola essa potência de dois; o AND bit a bit com o índice original produz exatamente essa potência. O laço clássico de atualização começa no índice modificado e substitui i por i mais lsb enquanto i permanece dentro do tamanho n da árvore, de modo que cada passo salta para o próximo índice que deve absorver o delta.
O laço clássico de consulta de prefixo começa no extremo direito do prefixo e substitui i por i menos lsb enquanto i permanece positivo, somando as células responsáveis que recobrem o intervalo de um até o índice original. Juntos, esses dois percursos implementam somas de intervalo via inclusão de dois prefixos.
Compreender um único passo—próximo de atualização igual a i mais lsb, pai de consulta igual a i menos lsb—basta para depurar erros off-by-one, desenhar a árvore de responsabilidades no quadro e verificar se uma implementação coincide com as identidades do livro-texto antes de integrá-la em um template de competição ou em um pipeline analítico de produção.
Quando os passos de uma árvore de Fenwick ajudam
Treinadores de programação competitiva e juízes online usam uma calculadora de índices da árvore de Fenwick para que os alunos verifiquem passos pai e próximo enquanto escrevem à mão os laços de atualização e consulta. Ferramentas de preparação para entrevistas precisam de um oráculo determinístico que concorde com todo tutorial BIT padrão nas mesmas entradas inteiras, incluindo índices incômodos que são um a menos que uma potência de dois. Validação falha não consome saldo.
Mantenha os índices no intervalo positivo de trinta e dois bits, fixe os arrays de caminho nos testes quando size estiver definido, e você obtém navegação reproduzível para lições de casa, capturas de documentação e edge workers sem montar um sandbox completo de estruturas de dados próprio.
Casos de uso
Validação de entrevistas e templates
Compare implementações BIT candidatas com um oráculo determinístico de sequências de índices de atualização e consulta de prefixo para tamanhos fixos.
Perguntas frequentes
Os índices são 0-based ou 1-based?
1-based, como na formulação padrão de Fenwick / binary indexed tree. O índice deve ser um inteiro de 1 a 2147483647.
Por que usar i & -i para o bit menos significativo?
Em complemento de dois, -i inverte os bits abaixo do 1 menos significativo de i; o AND bit a bit isola essa potência de dois, que é exatamente o comprimento de responsabilidade da célula i.
Quais são os caminhos do índice 13 em uma árvore de tamanho 16?
Com tamanho 16, o caminho de atualização é 13, 14, 16: as células que absorvem uma mudança no 13. O caminho de consulta é 13, 12, 8: as células somadas para obter a soma acumulada até o 13.
Para que serve uma árvore de Fenwick?
Ela resolve somas acumuladas e atualizações de um único valor em tempo logarítmico. Cada célula guarda um trecho parcial cujo tamanho é uma potência de dois, então somar ou atualizar mexe em poucas células.
Quais índices posso digitar?
Qualquer inteiro de 1 a 2147483647, o maior valor positivo de 32 bits. Se você também informar o tamanho da árvore, ele precisa ser pelo menos igual ao índice e ficar dentro do mesmo limite.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
curl -X POST https://api.kit.forhosting.com/dev/fenwick-index \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"index":13}'const res = await fetch("https://api.kit.forhosting.com/dev/fenwick-index", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"index": 13
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/dev/fenwick-index",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"index": 13
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/fenwick-index", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"index":13}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"index":13}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/fenwick-index", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Exemplo de requisição
{
"index": 13
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.fenwick_index",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
A lógica pura e determinística coincide byte a byte entre o uso gratuito no navegador e as chamadas API pagas.
Contrato de entrada, campos de resposta e validação
Exemplo: o índice treze tem binário zero-b one one zero one, bit menos significativo um, próximo de atualização quatorze, pai de consulta doze; com size dezesseis o caminho de atualização é treze depois quatorze depois dezesseis, e o de consulta é treze depois doze depois oito. Envie um corpo JSON via POST com o campo obrigatório index: um inteiro positivo no intervalo fechado de um até dois elevado a trinta e um menos um, o máximo positivo com sinal de trinta e dois bits em que os operadores bit a bit de JavaScript permanecem fiéis. Os alias i, idx e position são aceitos. O campo opcional size (alias n, n_max, tree_size) é o índice máximo da árvore; quando presente deve ser um inteiro pelo menos tão grande quanto index e no máximo o mesmo limite superior. Valores ausentes, não inteiros, zero ou fora da faixa falham com invalid_input nomeando o campo e não são cobrados. Em caso de sucesso o corpo sempre inclui index, lowest_set_bit, update_next, query_parent, strings binary e lsb_binary com prefixo zero-b, e uma string formula curta reafirmando as identidades. Quando size é fornecido, o corpo também inclui size, update_path como lista ordenada de índices visitados pelo laço de atualização, query_path como lista ordenada visitada pelo laço de prefixo, e update_next_in_range como booleano indicando se o vizinho de atualização de um passo ainda está dentro da árvore. Combine a resposta com a sua própria visualização de arrays se precisar de um diagrama; este endpoint só calcula aritmética de índices e não armazena valores da árvore nem executa consultas de soma sobre arrays do usuário.
Onde uma API de índices Fenwick justifica o seu valor
Como a implementação é pure parse de nível A, cada chamada bem-sucedida custa o preço base publicado US$ 0,002 sem tokens de modelo e sem rede de saída.
Casos de integração
Exercícios BIT de competição e deveres
Forneça aos alunos o índice i e o size n opcional; verifique lowest_set_bit, update_next, query_parent e os caminhos completos frente a laços Fenwick escritos à mão.
Caminhos golden para docs e bibliotecas
Gere fixtures de update_path e query_path para documentação de binary indexed tree, testes unitários e checagens de portabilidade entre linguagens.
Perguntas técnicas
Como calcular os índices pai e próximo da árvore de Fenwick?
Envie um índice i positivo 1-based. A API devolve lsb = i & -i, update_next = i + lsb e query_parent = i - lsb, além das formas binárias de i e do lsb.
O que faz o parâmetro opcional size?
Quando size n está definido (n >= index), a resposta adiciona update_path (i += lsb enquanto i <= n) e query_path (i -= lsb enquanto i > 0), igual aos laços BIT clássicos.
Quanto custa a calculadora de índices da árvore de Fenwick?
A ferramenta no navegador é gratuita. Solicitações API usam saldo pré-pago KIT a US$ 0,002 por chamada bem-sucedida; entrada inválida não é cobrada.