Vai al contenuto principale

Informatica · Strutture dati

Fenwick tree: quante celle legge query(2023)?

In un Fenwick tree (binary indexed tree) con $n \ge 2023$ celle indicizzate da 1, definisci lowbit(x) come la potenza di 2 corrispondente al bit a 1 meno significativo di x (es. lowbit(12) = 4). L'operazione query(j), che calcola la somma dei prefissi 1..j, legge la cella j e poi pone $j = j$ - lowbit(j), ripetendo finché j è maggiore di 0. Quante celle vengono lette in totale da query(2023)?

La tua risposta

Vanno bene sia 3,14 sia 3.14.