Salve a tutti, volevo esercitarmi un po’ sui segment tree e avevo letto da qualche parte sui forum che poteva aiutare provare a risolvere i problemi “rangetree”. Dopo aver provato rangetree3 e a non essere riuscito a trovare una soluzione con i segment tree (l’ho comunque risolto ma con un semplice vector), mi è sorto il dubbio che range tree e segment tree fossero due strutture diverse.
Sui forum ho trovato questa thread dalla quale mi pareva di aver capito fossero due cose diverse. Ho quindi cercato sul web cosa fossero questi fantomatici range tree ma con scarsi risultati, l’unica cosa che ho trovato è stata la pagina wikipedia che però non mi ha chiarito molto le idee. Ho anche letto questo documento PDF che era allegato a una risposta nella thread di cui ho già parlato: rangetree-wehrstedt.pdf (58,9 KB).
Questo però mi ha nuovamente messo il dubbio range trees e segment trees fossero la stessa cosa…
Forse i segment tree sono un particolare tipo di range tree? Qualcuno saprebbe schiarirmi le idee?
Grazie mille.
Sono la stessa cosa. Sono alberi in cui un nodo si riferisce a un range/segmento dell’array.
Per curiosità, cosa sarebbe questa soluzione?
Nella soluzione dove ho usato un vettore ho memorizzato all’interno del vettore gli elementi della sequenza che il testo chiama “A”.
Così facendo il tempo della prima operazione (modificare l’i-esimo elemento della sequenza) è costante e il tempo della seconda operazione (il maximum subarray problem) è lineare.
In particolare per la seconda operazione uso due variabili: “somma” inizializzata a 0 e “max” inizializzato a -10001 (somma infatti sarà sempre maggiore o uguale a -10000).
Partendo dall’indice più basso che mi è stato fornito (l’estremo inferiore dell’array per il quale devo trovare il subarray con la somma degli elementi massima) scorro la sequenza “A” fino ad arrivare all’indice più alto dato in input (l’estremo superiore dell’array appena descritto) ad ogni passo aggiungendo l’elemento attuale a “somma” e assegnando il valore di somma a “max” se somma>max.
Così facendo però dopo aver considerato anche l’ultimo elemento avrei memorizzata nella variabile max la somma massima dei subarray che iniziano al primo elemento dell’array, non necessariamente la risposta al nostro problema, per invece ottenere la somma massima del subarray generico basta l’accortezza di azzerare “somma” quando questa va in negativo. Questo solo dopo aver aggiornato max (il subarray potrebbe essere composto esclusivamente da elementi negativi, azzerare somma prima di aggiornare max in questo caso ci darebbe il risultato errato 0).
Spero la mia spiegazione sia stata abbastanza chiara, allego anche il codice se potesse interessare:
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main() {
ifstream cin("input.txt");
ofstream cout("output.txt");
int N, M, operazione, temp1, temp2, tot, max;
cin >>N;
vector<int> A(N);
for(int i=0; i<N; i++){
cin >>A[i];
}
cin >>M;
for(int i=0; i<M; i++){
cin >>operazione >>temp1 >>temp2;
temp1--;
if(operazione){ //operazione==1 (maximum subarray problem)
tot=0;
max=-10001;
for(int i=temp1; i<temp2; i++){
tot+=A[i];
if(tot>max){
max=tot;
}
if(tot<0){
tot=0;
}
}
cout <<max <<'\n';
}else{ //operazione==0 (modifica di un elemento)
A[temp1]=temp2;
}
}
return 0;
}
Sì ok, l’algoritmo classico per max subarray. Però il punto del problema non sarebbe fare gli update in \mathcal{O}(1) e e poi le query nel modo “normale”, perché questa cosa ha complessità \mathcal{O}(QN) e dovrebbe fare tle su casi forti.
La soluzione ottimale usa un segment tree per fare sia gli update sia le query in \mathcal{O}(\log N). Prova a pensare a in che modo tenerti informazione solo per alcuni segmenti può aiutarti a migliorare la complessità.
Teoricamente sono due cose diverse (infatti la pagina Wikipedia di Rangetree specifica che e’ una struttura per tenere punti in k dimensioni).
In pratica, nella comunita’ italiana di competitive programming (per qualche ragione strana) le persone usano sia il temine “rangetree” che il termine “segment tree” per riferirsi ad un segment tree.
Sapevo che la mia soluzione non fosse ottimale è che non sono riuscito a trovare un criterio secondo cui assegnare un valore ad un nodo padre, inizialmente avevo pensato ad assegnarli il massimo tra: il primo nodo figlio, il secondo nodo figlio e la somma di essi ma mi sono presto accorto che non avrebbe funzionato…
Cercherò di darti qualche suggerimento:
-
Assumendo di saper costruire un segment tree che ci permette di calcolare la risposta, l’update è facile: basta aggiornare la foglia corrispondente all’elemento da aggiornare e i nodi dalla foglia alla radice, unendo i figli allo stesso modo di come lo costruiamo.
-
Prima una considerazione generale. Se costruire un’informazione in un nodo richiede informazioni diverse dalla stessa, serve aggiornare anche questa altra informazione nel nodo padre, per poter poi aggiornare i nodi sopra. Dobbiamo trovare quindi un insieme di informazioni per ogni nodo che sia possibile calcolare a partire da quello stesso insieme di informazioni.
Ciò detto, se stiamo unendo due range contingui (uniamo i due figli di un nodo nel segment tree) come può variare la risposta a “sottoarray di somma massima”?
Risposta
Ci sono tre casi; il sottoarray di somma massima può essere:
- completamente incluso nella metà di sinistra
- completamente incluso nella metà di destra
- a cavallo delle due metà
Siamo interessati al massimo tra le tre opzioni. Le prime due sono banali perché la risposta sta nel figlio.
Come calcolamo il terzo caso?
Se il sottoarray di somma massima si trova a cavallo delle due metà, avrà somma pari al suffisso di somma massima della metà di sinistra + prefisso di somma massima della metà di destra.
Perché?
Supponiamo che il prefisso della metà di destra non sia quello di somma massima, tenendo invariato il suffisso della metà di sinistra, prendere il prefisso di somma massima migliorerebbe la somma. Analogamente per il suffisso di destra.
Come aggiorniamo il prefisso di somma massima?
Abbiamo due casi.
-
Il prefisso di somma massima finisce nella metà di sinistra: sarà uguale al prefisso di somma massima del figlio sinistro.
-
Il prefisso finisce nella metà di destra: sarà uguale alla somma del range sinistro + la somma del prefisso di somma massima del range destro.
Consideriamo la maggiore tra le due opzioni.
La somma del range di un nodo è, banalmente, la somma dei range dei figli.
Per il suffisso di somma massima l’operazione sarà analoga e speculare.