Ciao, volevo chiedere se conoscete qualche referenza per i range trees, perchè nel sito ci sono alcuni problemi che ne richiedono l’utilizzo ma io non riesco a trovare nessun libro o risorsa in cui studiarli. Cercando sul web ho trovato praticamente solo wikipedia che ti dà una descrizione abbastanza generale ma poco pratica, e per esempio nel libro Introduction to algorithms e altri non se ne parla. Oppure è possibile che per caso siano conosciuti piu comunemente con un altro nome ed è per questo che non trovo niente? grazie in anticipo 
Generalmente per quanto riguarda i problemi, la struttura che si usa è quasi sempre il segment-tree. Su topcoder c’è una guida carina sui segment tree. Applicazioni comuni dei segment tree sono il RSQ (Range Sum Query) e il RMQ (Range Minimum/Maximum Query), ma l’idea dietro il segment tree può essere estesa per risolvere molti altri problemi.
Aggiungo anche questa dispensa, scritta da Luca Wehrstedt, che è un ottimo ausilio alla lettura del tutorial postato da Mazzetto:
rangetree-wehrstedt.pdf (58,9 KB)
La sezione 1.3 Soluzione migliorata corrisponde alla sezione An <O(N), O(sqrt(N))> solution
Le sezioni 1.4 Soluzione ottima e 1.5 Implementazione corrispondono alla sezione Segment trees
P.S.: attenzione alla confusione che si genera tra i termini segment tree, range tree, interval tree. Topcoder contribuisce alla confusione, chiamando segment tree ciò che andrebbe chiamato in realtà range tree.
Grazie mille ragazzi, ho già un’infarinatura base dei segment trees perchè li avevo guardati su “Competitive Programming”, adesso anche grazie al materiale che mi avete dato li studio piu seriamente e almeno sapendo che si usano questi per le soluzioni dei cosiddetti “range trees” posso sperimentarli su un po di problemi concreti
Ho provato il problema “Range tree 1”, quello delle monete testa o croce usando un segment tree. Solo che la mia idea supporta una query in lg N ma l’aggiornamento è lineare, infatti prendo i soliti 40 punti… Nel mio segment tree ho nella posizione che gestisce gli indici fra i,j (inclusi) le monete che mostrano testa in quell’intervallo. A questo punto una query che chiede le monete che mostrano testa può essere risolta facilmente in lg N , ma per aggiornare, devo aggiornare tutti gli intervalli che contengono anche solo un elemento che è stato capovolto, quindi tutte le posizioni che gesticono i,j con i=j che è un elemento aggiornato piu tutti i loro “genitori”…Idee migliori?
È necessaria una tecnica nota come lazy propagation
Thanks!!
Guardandomi la lazy propagation sono riuscito a implementare questo ma continua a darmi execution timed out…
int update_tree(int p, int L, int R, int i, int j) {
if(L > R || L > j || R < i) // Current segment is not within range [i, j]
return INF;
if(L == R) { // Leaf node
int d= 1-2st[p];
st[p] = 1 - st[p];
return d;
}
int s = update_tree(p2, L, (L+R)/2, i, j); // Updating left child
int s2 = update_tree(1+p*2, 1+(L+R)/2, R, i, j); // Updating right child
int d2 = ( (s!=INF ? s : 0) + (s2!=INF ? s2 : 0) );
st[p] += d2; // Updating root with max value
return d2;
}
In pratica arrivo alle foglie dentro l’intervallo, nelle quali scambio il valore( da 0 1 o viceversa, cioè da testa o croce o viceversa) e poi ritorno la differenza del loro valore ai genitori e cosi via fino alla radice, però bho mi sembra lineare con l’intervallo che vado a modificare, infatti è praticamente identica alla funzione che avevo utilizzato prima di guardare la lazy propagation, dov’è che toppo clamorosamente?
Ho trovato adesso il concetto di “Flag”… adesso ci do un’occhiata
Sì, l’idea della lazy propagation è di tenere appunto un flag, o comunque un indicatore, che ti fa capire che in un certo nodo “è necessario applicare un’operazione all’intero intervallo che rappresenta”, però non lo fai subito… dato che la strategia è lazy = pigra. Quindi, quando un nodo ha l’indicatore lazy, tutti i discendenti hanno dei valori “outdated”, che non sono più corretti. Come si fa quindi quando ti si chiede un valore che però è “outdated”?
Semplicemente nella funzione di ricerca, man mano che scendi nell’albero, su tutti i nodi che incontri che hanno l’indicatore lazy effettui una propagazione dell’indicatore lazy ai due suoi figli diretti (e non a tutti i discendenti), in questo modo da 1 indicatore lazy ora ne hai 2, però in compenso hai dei valori “outdated” in meno.
Quindi, riassumendo, esegui l’update solo “dove ti serve” e “man mano che ti serve”.
Si, ieri avevo letto un po sul web e sono riuscito a fare il problema La chiave è appunto fare l’update effettivamente solo dove e quando ti serve e usare una flag per segnarti dove non è outdated!