Calcolatore indici Fenwick

Un albero di Fenwick, chiamato anche binary indexed tree, risponde a somme di prefisso e aggiornamenti puntuali in tempo logaritmico memorizzando intervalli parziali le cui lunghezze sono potenze di due. Ogni passo di navigazione dipende da un trucco sui bit: il bit meno significativo dell'indice 1-based corrente, scritto lsb uguale a i AND il negativo di i in complemento a due. Sommare quel lsb percorre la catena di aggiornamento; sottrarlo percorre la catena di query di prefisso. Studenti, programmatori competitivi e autori di librerie hanno bisogno di quegli indici padre e successivo senza riderivare le identità sotto la pressione di un esame. Questo calcolatore di indici dell'albero di Fenwick accetta un indice positivo i e, opzionalmente, una dimensione dell'albero n; restituisce il lsb, il successivo di aggiornamento e il padre di query in un passo, forme binarie per la didattica e, quando n è impostato, il percorso completo di aggiornamento e di query del codice BIT classico.

Come gli indici di Fenwick usano il bit meno significativo

In un binary indexed tree con indici 1-based, la cella all'indice i è responsabile di un segmento contiguo dell'array sottostante la cui lunghezza è uguale al bit meno significativo di i. Quella lunghezza si calcola come lsb uguale a i AND la negazione in complemento a due di i, spesso scritto i and minus i nei linguaggi con aritmetica modulare su interi a larghezza fissa. Geometricamente, invertire tutti i bit sotto l'uno meno significativo isola quella potenza di due; l'AND bit a bit con l'indice originale produce esattamente quella potenza.

Il ciclo classico di aggiornamento parte dall'indice modificato e sostituisce i con i più lsb finché i resta entro la dimensione n dell'albero, così ogni passo salta all'indice successivo che deve assorbire il delta. Il ciclo classico di query di prefisso parte dall'estremo destro del prefisso e sostituisce i con i meno lsb finché i resta positivo, sommando le celle responsabili che ricoprono l'intervallo da uno fino all'indice originale. Insieme, quei due percorsi implementano somme di intervallo tramite inclusione di due prefissi.

Capire un solo passo—successivo di aggiornamento uguale a i più lsb, padre di query uguale a i meno lsb—basta per debuggare errori off-by-one, disegnare l'albero delle responsabilità alla lavagna e verificare che un'implementazione corrisponda alle identità del manuale prima di integrarla in un template da gara o in una pipeline analitica di produzione.

Quando i passi di un albero di Fenwick aiutano

Coach di programmazione competitiva e judge online usano un calcolatore di indici dell'albero di Fenwick affinché gli allievi controllino passi padre e successivo mentre scrivono a mano i cicli di aggiornamento e query. Gli strumenti di preparazione ai colloqui necessitano di un oracolo deterministico che concordi con ogni tutorial BIT standard sulle stesse entrate intere, compresi indici scomodi che valgono una potenza di due meno uno. La validazione fallita non consuma il saldo.

Mantenga gli indici nell'intervallo positivo a trentadue bit, fissi gli array di percorso nei test quando size è impostato, e otterrà navigazione riproducibile per compiti, screenshot di documentazione e edge worker senza montare un sandbox completo di strutture dati proprio.