Editorial
Con l’arrivo del quarto episodio della rubrica: permutazioni apro le discussioni relative a scavi presentandone una soluzione.
L’esercizio scavi richiede sostanzialmente di applicare Q update, ognuno dei quali consiste nell’incrementare di X le celle comprese in un certo rettangolo, per poi restituire la matrice aggiornata.
Nel caso in cui volessimo, iterare su ogni update dal primo all’ultimo ed aggiornare la matrice update per update, possiamo farlo in diversi modi: partendo dalla soluzione banale O(QRC) nella quale non facciamo altro che aggiornare ogni cella di ogni update in ordine, ed arrivando a soluzioni più complesse che richiedo strutture dati specifiche. Anche nel caso in cui utilizzassimo le strutture migliori per fare questo genere di ragionamento, come un Segment Tree 2D, il programma sarebbe troppo lento per rimanere nel tempo limite.
L’osservazione chiave è che non siamo obbligati ad aggiornare la matrice update per update ma basta salvare delle informazioni per ogni update che ci permettano poi di generare la matrice finale in un tempo minore.
Esiste infatti un piccolo trucco per “accumulare” gli update ed applicarli effettivamente solo una volta, Per semplicità spiego prima l’approccio su una sola dimensione.
Update Cumulativi 1D
Supponiamo di avere dunque un array V lungo N inizializzato a 0 sul quale dobbiamo fare Q update ognuno dei quali consiste di 3 interi L, R, X, per ogni update dobbiamo incrementare di X tutte le celle i | L \le i \le R .
input:
N=5 Q=3
0 3 5
1 4 1
2 2 3
output:
5 6 9 6 1
Ora vogliamo salvare per ogni update delle informazioni(pochi dati, l’update deve essere O(1)) che permettano poi di computare l’array finale in tempo lineare: O(N).
Supponendo che vogliamo ricostruire l’array finale con un ciclo nel quale per ogni i | 1 \le i \le N-1 V[i]=V[i-1]+diff[i] allora dovremo avere in diff[i] la differenza tra l’elemento i e l’elemento precedente.
Applicando un update L, R, X, a prescindere da quanto siano lontani L e R, solo 2 celle delle R-L+1 cambiano differenza dalle cella precedente: per esempio con q= 1, 3, 2 si passa da 0 0 0 0 0 a 0 2 2 2 0 e solo le celle i=1 ed i=4 cambiano differenza. Infatti se andiamo a vedere come cambiano le differenze da prima a dopo l’update: 0 0 0 0 0 diventa 0 2 0 0 0 -2 si può quindi notare che dato una query q=L, R, X ed un array delle differenze diff[] per applicare un update basta fare diff[L]+=X; diff[R+1]-=X; e successivamente
v[0]=diff[0];
for(int i=1;i<N;i++)
v[i]=diff[i]+v[i-1];
Questo tipo di ragionamento è cumulativo, infatti si possono applicare le varie query in O(1) per poi aggiornare solo alla fine, prendendo l’esempio di prima:
Aggiorniamo diff[]
q_0=0, 3, 5
5 0 0 0 -5
q_1=1, 4, 1
5 1 0 0 -5 Notare che non aggiorno le celle con indici maggiori di N.
q_2=2, 2, 3
5 1 3 -3 -5
Se poi calcolo in O(N) i valori di V[] ottengo appunto: 5 6 9 6 1
Update cumulativi 2D
Ora che sappiamo come fare gli update monodimensionali in O(Q+N) dobbiamo applicare la stessa strategia sulla matrice bidimensionale update del tipo X1, Y1, X2, Y2, P, un punto di partenza è: considerare ogni riga come array monodimensionale e fare gli update +P e -P rispettivamente nella colonne Y1 e Y2+1 delle righe che vanno da X1 a X2, in questo modo per applicare un update dobbiamo scorrere potenzialmente tutte le righe O(R), quindi in totale avremo O(QR) più la computazione dei singoli vettori partendo dalle differenze: O(RC) quindi in tutto O(QR+RC).
Guardando le assunzioni notiamo come quel QR sia un fattore troppo elevato, bisogna ridurlo, riuscendo comunque ad ottenere le nostre colonne di +P e -P, esempio:
input:
R=4 C=5 Q=1
1 1 2 3 5
output:
0 0 0 0 0
0 5 5 5 0
0 5 5 5 0
0 0 0 0 0
L’obiettivo è ottenere la relativa tabella delle differenze sulle righe:
0 0 0 0 0
0 5 0 0-5
0 5 0 0-5
0 0 0 0 0
Quello che si nota facilmente dall’ultima tabella è che per avere le differenze sulle righe non devo fare altro che 2 update monodimensionali sulle colonne, è quindi possibile utilizzare prima il metodo degli update cumulativi sulle colonne per ottenere le differenze sulle righe e poi il metodo degli update cumulativi sulle righe per ottenere la matrice finale.
Per fare gli update cumulativi 1D sulle colonne si ha complessità O(Q+RC) per fare gli update cumulativi 1D sulle righe si ha complessità O(RC) arrivando dunque ad una complessità finale O(Q+RC).