Aiuto per Place (fenwick1)

Aiuto
1

All’inizio mi sembrava banale, ma in realtà non lo è. La prima soluzione buona che ho mandato totalizza 69 punti, ma non utilizza i Fenwick Tree (suppongo sia per questo motivo che non totalizza 100/100).

Quindi li ho studiati ma sinceramente non ho capito bene come fare ad implementarne uno per questo problema. Il concetto è simile, ma i FT utilizzano delle operazioni sui bit per trovare gli indici. In questo caso come posso fare ad utilizzare queste stesse operazioni per trovare gli indici del mio albero? Anche perché se faccio in altro modo non credo si possa mantenere la complessità O(logN)
2

Come hai notato, sei davanti ad un albero. Il problema è che i dipendenti sono numerati in un modo tale che i discendenti un certo nodo non hanno una numerazione contigua. 

Però si può trovare un modo per rinumerare i nodi dell’albero in modo che, dato un nodo, tutti i suoi discendenti occupino una posizione contigua all’interno di un vettore. Una volta che è stata fatta questa operazione, allora il problema si può tradurre in update in un intervallo contiguo in un vettore e query di un elemento, che può essere fatto con un fenwick tree (o un segment tree).
3

Risolto, grazie.