Lazy Propagation
Come promesso, ecco la seconda parte dell’introduzione ai segment tree.
Negli episodi precedenti…
Abbiamo visto che un segment tree “base” permette query su range e update su un solo elemento o viceversa.
Ma se il problema fosse: “ci è dato un array A di N interi (N\le10^6) e dobbiamo eseguire Q operazioni (Q\le10^6) che possono essere una query sulla somma del range [l,r[ o aggiungere X agli elementi nel range [l,r[” possiamo ancora usare un segment tree?
Prime considerazioni
Se manteniamo un segment tree che permette solo point update, aumentare tutti gli elementi di un range costerebbe O(N) update da O(\log(N)) ciascuno, ovvero O(N\log(N)). Ma abbiamo detto che costruire da capo il segment tree impiega O(N). C’è qualcosa che non va: se facciamo gli update in O(N) allora possiamo tenere la prefix sum dell’array, che permette di sommare un range in O(1).
Possiamo fare di meglio? Ovviamente sì.
Perché “lazy”?
Un update su range modifica O(N) nodi ma abbiamo detto che ogni query ne visita al massimo O(\log(N)), possiamo quindi di pensare di modificare i nodi man mano che questi vengono visitati da una query.
Se un range è rappresentato da un insieme di segmenti, allo stesso modo di una query, per un update raggiungiamo i nodi corrispondenti con una DFS e modifichiamo il valore di quel nodo secondo quanto richiesto: se ad esempio stiamo incrementando di 5 e raggiungiamo un nodo corrispondente a un range totalmente incluso nell’intervallo dell’update, possiamo stabilire che il valore di quel nodo dovrà essere incrementato di 5 moltiplicato per la lunghezza del range, visto che ogni elemento viene incrementato di 5.
Nell’immagine, i nodi interessati dall’update sono colorati in rosso. È stato aggiunto un indicatore a ciascun nodo, quando è “acceso” significa che quel nodo è stato modificato e quando verrà visitato, l’update dovrà essere propagato ai figli.
Nel frattempo, ogni volta che termina la chiamata ricorsiva sui figli, il valore del nodo viene aggiornato alla somma dei figli, in modo che anche i nodi sopra vengano aggiornati.
Come per le query, la complessità dell’update sarà O(\log(N)).
Quando una query utilizzerà il valore di quel nodo non ci sono problemi, ma cosa succede se vengono visitati nodi nel suo sottoalbero, che quindi non sono ancora stati modificati?
Propagazione dell’update
Visitare un nodo implica aver visitato quelli che stanno sopra. Di conseguenza, quando incontiramo un nodo ancora da aggionare, modifichiamo il suo valore e propaghiamo sui figli l’update, controllando prima di non essere in una foglia. Questa operazione richiede tempo costante perché il numero di figli è sempre 2 e siccome ciascuna query visita O(\log(N)) nodi, dovremo effettuare al massimo O(\log(N)) update ogni volta. Questo garantisce la stessa efficienza di un segment tree “normale” ma permettendo di fare update su range.
Nell’esempio sopra la query interessa i nodi evidenziati in rosso. Quello a sinistra era già stato modificato durante l’update, mentre nell’altro caso per arrivare al nodo che ci interessa dobbiamo passare per un nodo modificato. Quello che facciamo allora è propagare l’update ai due figli e proseguire con la visita.
Come detto in precedenza, propagare l’update ha complessità O(1), quindi la complessità della query rimane invariata.
Implementazione
Una prima differenza è che siccome per ogni nodo dovremo tenere più informazioni (la somma e l’eventuale update da propagare) risulta conveniente creare una struct node come segue:
struct node {
ll sum = 0;
ll lazy_update = 0;
};
quindi modificheremo leggermente anche il costruttore e la funzione build. Per il primo dovremo ricordarci di creare un vector<node> mentre quando costruiamo l’albero andremo a modificare l’attributo sum (ad esempio st[i].sum = A[left]).
La vera novità è la procedura propagate.
void propagate (int i, int left, int right) {
// riceve un nodo e propaga l'update
if (st[i].lazy_update == 0) return; // nulla da propagare
// si aggiorna il valore del nodo
// aggiungiamo l'incremento moltiplicato per la lunghezza del range
st[i].sum += (right - left) * st[i].lazy_update;
if (right - left > 1) { // se non è una foglia si propaga ai figli l'update
st[2*i].lazy_update += st[i].lazy_update;
st[2*i+1].lazy_update += st[i].lazy_update;
// l'update viene sommato a quello dei figli in caso fossero già presenti altri update da propagare in quei nodi
}
// si resetta l'update lazy del nodo
st[i].lazy_update = 0;
}
Questa procedura verrà chiamata ogni volta che si accede a un nodo facendo una query o un update. Quello che fa è aggiornare un nodo al valore corretto dopo l’update e propagare ai figli il valore da aggiungere.
Per le query ci basterà chiamare propagate (i, left, right) come prima cosa, mentre l’update deve essere modificato e reso più simile a una query:
void update (int i, int left, int right, int update_left, int update_right, ll val) {
// prima di guardare il nodo propago eventuali update
propagate (i, left, right);
if (update_left >= right || update_right <= left) {
return; // fuori dal range
}
if (left >= update_left && right <= update_right) {
// range è totalmente incluso
// aggiungo l'update lazy e lo propago in modo da aggiornare il valore del nodo
st[i].lazy_update = val;
propagate(i, left, right);
return;
}
// nel caso generico ricorro sui figli
int mid = (left + right) / 2;
update (2*i, left, mid, update_left, update_right, val);
update (2*i+1, mid, right, update_left, update_right, val);
// aggiorno alla somma dei figli
st[i].sum = st[2*i].sum + st[2*i+1].sum;
}
Implementazione completa
Implementazione in C++
struct segtree {
struct node {
ll sum = 0;
ll lazy_update = 0;
};
int N;
vector<node> st;
ll build (int i, int left, int right, vector<ll> &A) {
if (right - left == 1) {
return st[i].sum = A[left];
}
int mid = (left + right) / 2;
st[i].sum = build(2*i, left, mid, A) +
build(2*i+1, mid, right, A);
return st[i].sum;
}
segtree (vector<ll> &A) {
N = A.size();
st.resize (4*N);
build(1,0,N,A);
}
void propagate (int i, int left, int right) {
if (st[i].lazy_update == 0) return;
st[i].sum += (right - left) * st[i].lazy_update;
if (right - left > 1) {
st[2*i].lazy_update += st[i].lazy_update;
st[2*i+1].lazy_update += st[i].lazy_update;
}
st[i].lazy_update = 0;
}
void update (int i, int left, int right, int update_left, int update_right, ll val) {
propagate (i, left, right);
if (update_left >= right || update_right <= left) {
return;
}
if (left >= update_left && right <= update_right) {
st[i].lazy_update = val;
propagate(i, left, right);
return;
}
int mid = (left + right) / 2;
update (2*i, left, mid, update_left, update_right, val);
update (2*i+1, mid, right, update_left, update_right, val);
st[i].sum = st[2*i].sum + st[2*i+1].sum;
}
void update (int update_left, int update_right, ll val) {
update (1, 0, N, update_left, update_right, val);
}
ll query (int i, int left, int right, int query_left, int query_right) {
propagate (i, left, right);
if (query_left >= right || query_right <= left) {
return 0;
}
if (left >= query_left && right <= query_right) {
return st[i].sum;
}
int mid = (left + right) / 2;
return query (2*i, left, mid, query_left, query_right)+
query (2*i+1, mid, right, query_left, query_right);
}
ll query (int query_left, int query_right) {
return query (1, 0, N, query_left, query_right);
}
};
Per mettere in pratica
Infine
Ringrazio @nicholasbamber e @fve5 per aver revisionato il testo, evitando che diffondessi false informazioni.
Se notate errori o imprecisioni, sono ben accette segnalazioni.
Nella speranza che questi post possano essere d’aiuto per qualcuno, buona lettura.
ps. non garantisco nulla ma potrebbero arrivare in futuro approfondimenti su altri tipi di segment tree.