Segment tree e la square root decomposition


#1

Ho provato a fare il problema “multiples of 3” con risultato un 40/100. non avendo idea di come renderlo più efficiente sono venuto a cercare nel forum topic sul problema e quelli che ho trovato parlano di argomenti (che sono, mi sembra di aver capito, indispensabili da sapere per fare questo e altri problemi) quali segment tree e la square root decomposition ecc La domanda è dove posso trovare il materiale per studiarli?


#2

In questo topic se ne è parlato un po’:

(sì, assumiamo che range tree e segment tree siano la stessa cosa :sweat_smile:)

Nel topic sopra trovi anche la sqrt decomposition, che è diciamo uno “step” arrivare alla soluzione logaritmica…


#3

In che senso “nel topic sopra”? e la sqrt decomposition sarebbe lo step successivo del segment tree o precedente?


#4

Nel topic “Range trees”, linkato nel mio messaggio.

Precedente (anche se in realtà a essere pignoli la sqrt decomposition è un’idea più generale e si può usare in più situazioni diverse dove il segment tree non sarebbe utilizzabile)


#5

Un libro in cui reperire la maggior parte degli algoritmi / strutture dati utili nelle gare è il Competitive Programming 3, che puoi scaricare in pdf comprare tranquillamente online

Altrimenti, puoi utilizzare alcuni dei numerosi tutorial online

Segment Tree

  1. Video-tutorial del magico Tushar (hello friends)
  2. Una “guida” su GeeksForGeeks
  3. “Blog post” su codeforces

Sqrt Decomposition

  1. Video-tutorial su youtube