Come consigliato ho iniziato a guardare alcuni algoritmi con gli alberi e sono partito dal segment tree.
Ho capito a pieno il modo in cui lavori, e le sue complessità (O(4n) per crearlo, O(4logn ) per trovare per esempio il valore minimo all’interno dell albero ed per la memoria la dimensione dell’array dovrebbe avere worst_case di 4n)
Per quanto riguarda invece l’implementazione ho cercato di “tradurre” il codice del tizio che l’ha spiegato (https://www.youtube.com/watch?v=ZBHKZF5w4YU) da java a c++ e credo di aver sbagliato qualcosa, infatti per provarlo ho cercato di scrivere in locale il codice che presi 6 valori restituisse il minimo degli intervalli (0,3)(1,4)(2,5), ma evidentemente ho sbagliato qualcosa in quanto in output ho 3 volta il valore di MAX_INT , questo è il codice: https://pastebin.com/TRn3CTMa (chiedo anticipatamente venia per l’/gli errore/i imbarazzanti probabilmente commessi)
Come hai detto tu, l’array segmentTree[] deve essere inizializzato a 4*N, quindi non 7, ma 24.
Risolto quello a me sembra che vada tutto, attento alla funzione createSegmentTree che è una void, non int 
in ogni caso, credo sia molto comodo scrivere una classe che allochi i propri nodi. In certi problemi sono richiesti più rangetree (ad esempio quando si usa l’HLD) e diventa complicatissimo scrivere funzioni che facciano un segment tree utilizzando un vettore heap. Con la classe diventa molto più comodo, il codice è ordinato, e tante cose belle. Poi ormai ci ho fatto l’abitudine, ma credo sia davvero più efficente in termini di fatica nella scrittura del codice.
esempio
class segmenttree
{
private:
public:
int _l,_r,_val;
segmenttree *left,*right;
segmenttree(){}
segmenttree(int l,int r)
{
if(l==r)
{
_val=-1;
_l=_r=l;
left=NULL;
right=NULL;
}
else
{
_l=l;
_r=r;
int _m=(l+r)/2;
_val=-1;
left=new segmenttree(_l,_m);
right=new segmenttree(_m+1,_r);
}
}
~segmenttree()
{
if(left)delete left;
if(right)delete right;
}
int maxquery(int s,int e)
{
if(s>e || _r<s || _l>e)return -1;
if(_l>=s && _r<=e)return _val;
return std::max(left->maxquery(s,e),right->maxquery(s,e));
}
void set(int p,int v)
{
if(_l>p || _r<p)return;
if(_l==_r){_val=v;return;}
left->set(p,v);
right->set(p,v);
_val=std::max(left->_val,right->_val);
}
};
Infatti bastava modificare quegli errori, come avevo già anticipato gli errori erano imbarazzanti 
Dal basso della mia ignoranza non ho capito 
[quote=“lukecavabarrett, post:3, topic:4687”]
(ad esempio quando si usa l’HLD)
[/quote]
Cosa sarebbe un HLD[quote=“lukecavabarrett, post:3, topic:4687”]
utilizzando un vettore heap
[/quote]
Per vettori heap intendi array dichiarati nel main()?
Non ho mai usato le classi(in c++), quindi non conosco i vantaggi che possiedono…
la Heavy Light Decomposition è una struttura dati che si utilizza sugli alberi, per rispondere a query particolari. Se ti interessa, qui puoi trovare un tutorial interessante. Senza entrare nel merito, quando usi la tecnica HLD hai bisogno di tanti segmenttree quante sono le foglie dell’albero, ma non sai quanto saranno grandi (sai soltanto che la somma delle grandezze di tutti i segmenttree sarà pari al numero di nodi).
per implementare un segment tree hai due modi:
- Allochi (dove vuoi) un vettore lungo 4N, e prendi il nodo 1 come radice, ed ogni nodo i avrà 2i come figlio sinistro e 2i+1 come figlio destro
- Usi una classe (o struct) per gestire ogni nodo. Ogni struct ha un puntatore al figlio sinistro ed uno al figlio destro; nel caso si tratti di una foglia quei valori saranno
NULL.
La prima versione è molto semplice, specialmente quando c’è un solo segmenttree nel programma e bisogna fare operazioni elementari; tuttavia quando le operazioni da fare sul segmenttree sono complesse, o addirittura dobbiamo creare segmenttree a piacere, senza sapere quanti, quanto grossi, dove o come, diventa molto più semplice scrivere una classe, in quanto scrivi piccoli moduli alla volta, e in testa rimane tutto più chiaro.
Se non hai mai usato le classi in C++, ti consiglio di farlo perchè sono molto utili. Utilizzi già la STL (std::vector,std::map,std::set ecc.)?
È quella che uso attualmente è concordo con te che per le operazioni basi è coveniente.[quote=“lukecavabarrett, post:5, topic:4687”]
Usi una classe (o struct) per gestire ogni nodo. Ogni struct ha un puntatore al figlio sinistro ed uno al figlio destro; nel caso si tratti di una foglia quei valori saranno NULL
[/quote]
Credo di aver capito cosa intendi, per quanto riguarda le struct la potrei implementare una soluzione con i puntatori, per quanto riguarda le classi non le ho mai usate[quote=“lukecavabarrett, post:5, topic:4687”]
Utilizzi già la STL
[/quote]
Tutte queste http://www.cplusplus.com/reference/stl/ tranne forward_list
okay. l’unica differenza tra class e struct è che in class gli attributi (ovvero i dati contenuti) ed i metodi (ovvero le funzioni che quella classe/struct può fare) possono essere privati oppure pubblici, mentre nelle struct è tutto pubblico. Nel competitive programming -per quanto ne sappia- non serve avere cose private, quindi metto tutto pubblico, ma scrivo class per abitudine. Quando leggi il codice sopra, ignora le righe con scritto private: e public:, e pensa che al posto di class ci sia scritto struct: è davvero lo stesso.
Un altra cosa comoda di usare le classi è la seguente: immagino tu abbia notato che se vuoi un std::vector di qualsiasi tipo (int,char,float, o addirittura strutture create da te) ti basta scrivere std::vector<T> vet; dove T è un tipo qualsiasi. magico, vero? ora, se fai gare online dove puoi tenere sottomano codice già scritto, ti capiterà spesso di dover scrivere un segment tree dove fare le seguenti operazioni:
- mettere un certo elemento in una certa posizione
- fare una domanda su un certo range
il tipo dei valori contenuti nel segment tree potrebbe essere qualsiasi cosa, così come l’operazione che unisce i due figli: se vuoi chiedere le somme su un certo range, ogni nodo terrà la somma dei valori dei figli, mentre se vuoi chiedere il minore su un certo range, è chiaro che ogni nodo terrà il minore dei valori dei figli.
se fai scrivi una cosa del genere
#include <bits/stdc++.h>
template<class T,T Join(T,T)> class segment_tree
{
private:
public:
int _l,_m,_r;
T _val;
segment_tree *_left,*_right;
segment_tree(int l,int r,T k=T())
{
if(l==r)
{
_l=_r=_m=l;
_val=k;
_left=_right=NULL;
}
else
{
_l=l;
_r=r;
_m=(_l+_r)/2;
_left=new segment_tree(_l,_m,k);
_right=new segment_tree(_m+1,_r,k);
_val=Join(_left->_val,_right->_val);
}
}
void set(int p,T v)
{
#ifdef SAFE
if(p<_l||p>_r)throw "index out of bounds";
#endif
if(_l==_r){_val=v;return;}
if(p>_m)_right->set(p,v);else _left->set(p,v);
_val=Join(_left->_val,_right->_val);
}
T query(int s,int e)
{
#ifdef SAFE
if(_l>e||_r<s)throw "index out of bounds";
#endif
if(_l>=s&&_r<=e)return _val;
if(s>_m)return _right->query(s,e);
if(e<=_m)return _left->query(s,e);
return Join(_left->query(s,e),_right->query(s,e));
}
};
using namespace std;
int prodotto(int a,int b)
{
return a*b;
}
int main()
{
segment_tree<int,prodotto> V(0,7,1);
V.set(4,6);V.set(5,-7);
cout<<V.query(3,5)<<endl;
}
hai un oggetto che usi in maniera simile a come useresti un std::vector, e nel momento in cui lo dichiari puoi dirgli che tipo deve contenere, e che operazione deve fare sull’intervallo richiesto.
ad esempio per risolvere rangetree3 basta un codice del genere
struct interval
{
int somma,massimo,max_left,max_right;
interval(){}
interval(int v){somma=massimo=max_left=max_right=v;}
interval(int s,int m,int l,int r){somma=s;massimo=m;max_left=l;max_right=r;}
};
interval unisci(interval a,interval b)
{
return interval(a.somma+b.somma,std::max(std::max(a.massimo,b.massimo),a.max_right+b.max_left),std::max(a.max_left,a.somma+b.max_left),std::max(b.max_right,b.somma+a.max_right));
}
int main()
{
int N=II();
segment_tree<interval,unisci> V(1,N);
for(int i=1;i<=N;i++)V.set(i,interval(II()));
int Q=II();
while(Q--)
{
int t=II(),x=II(),y=II();
if(t)IIn(V.query(x,y).massimo);
else V.set(x,interval(y));
}
}
Ok allora sono identiche alle classi in java.[quote=“lukecavabarrett, post:7, topic:4687”]
dove T è un tipo qualsiasi. magico, vero?
[/quote]
Si ci avevo fatto caso ed è molto comodo.
Per quanto riguarda il codice sono a capire in cosa consiste dal punto di vista teorico, mentre non mi è chiara del tutto la sintassi dell’albero.[quote=“lukecavabarrett, post:8, topic:4687”]
ad esempio per risolvere rangetree3 basta un codice del genere
[/quote]
Non ho ancora provato a svolgere nessuno dei 3 esercizi
Per quanto riguarda il codice non capisco a cosa si riferisca:[quote=“lukecavabarrett, post:7, topic:4687”]
T
[/quote]
T corrisponde al tipo che verrà scelto successivamente in base all’esigenza?
Serve a specificare che la variabile k sia del tipo passato scelto in precedenza?[quote=“lukecavabarrett, post:7, topic:4687”]
_m
[/quote]
la variabile m corrisponde a?
Si sono un po di incomprensioni hahaha?
Esattamente; quando compili, per ogni tipo diverso con cui hai costruito quella classe, il compilatore ricopia tutto ed ogni volta che vede T lo sostituisce con il tipo richiesto.
Immagino tu ti riferisca a
segment_tree(int l,int r,T k=T())
è un parametro di default. quando tu scrivi una funzione, puoi decidere che alcuni parametri, se non specificati, siano settati in un certo modo. per fare un esempio:
void stampanumero(int numero=42)
{
printf("stampa %d\n",numero);
}
int main()
{
stampanumero(7);//output: stampa 7
stampanumero();//output: stampa 42
}
nello specifico, questa classe segmenttree ha un costruttore che vuole tre parametri: i margini (cioè, quale range deve rappresentare il rangetree) e il valore con cui riempire il rangetree. nel caso non viene specificato tale valore, il costruttore riempie tutti gli elementi del segment tree con l’istanza di default T().
in C++, ogni tipo o classe ha dei costruttori, e tutti hanno il costruttore di default, cioè un costruttore che non accetta nessun parametro. Ad esempio posso fare
int main()
{
int pippo;
pippo=int(); //il valore di default degli int è 0
std::string pluto;
pluto=std::string(); //il valore di defaulut delle string è ""
//e così via.
}
Scrivendo il rangetree senza sapere che tipo ci sarà dentro, ho scelto che ogni elemento, se non specificato altrimenti, conterrà il valore di default di quel tipo.
La variabile _m corrisponde alla metà del range gestito da un nodo. Nell’implementazione del segment tree che ho sempre usato, quando un nodo gestisce l’intervallo [l,r], o l=r e quindi il nodo è una foglia, oppure definiamo m = \lfloor \frac{l+r}{2} \rfloor e avremo il figlio sinistro che gestirà [l,m] ed il figlio destro che gestirà [m+1,r]. Gli attributi _l,_m ed _r altro non sono che questi tre valori.
Ok credo di aver afferrato abbastanza il concetto , quale esercizio posso provare qui su cms per il segmenttree? Perchè ho letto https://cms.di.unipi.it/#/task/rangetree1/statement ma non credo io possa svolgerlo con il segmenttree o mi sbaglio?
si può fare con il segment tree (in italia dicono tutti rangetree al posto di segment tree), solo che devi usare la lazy propagation, una tecnica che permette di fare alcune cose
Ok mi sono visto la Lazy Propagation e dovrei aver capito come funziona (dimmi se sbaglio, quando devo aggiornare le foglie da a a b aggiorno solamente il nodo n che rappresenta l’intervallo (a,b), potrebbero esserci più nodi n1,n2,...ni nel caso in cui l’intervallo a b non sia rappresentabile in un solo nodo salvandomi in un altro albero a quali nodi dovranno essere svolte le modifiche e quali modifiche , nel momento in cui svolgo altri update devo controllare che i nodi che si trovano al disopra di quello che devo aggiornare siano stati propagati, altrimenti li devo propagare ed infine quando ho una query q su un intervallo (a,b)_1 devo assicurarmi che i nodi sui cui lavoro siano stati propagati altrimenti propagarli, spero di aver capito bene 
)
Ho seguito questa spiegazione : https://www.youtube.com/watch?v=xuoQdt5pHj0 , ma rimane il problema che il codice è in java (che non è del tutto un problema in quanto è facilmente traducibile questo sarebbe il codice: https://github.com/mission-peace/interview/blob/master/src/com/interview/tree/SegmentTreeMinimumRangeQuery.java )ma soprattutto non è “pensato” da usare su una classe creata da me ma su degli array avendo quindi un utilizzo molto vincolato, hai per caso l’implementazione in una classe?
Per ora magari ti viene più semplice se continui ad usare il vettore heap. Prova ad implementare la lazy propagation da te.
Sono riuscito ad ottenere 100/100 anche se comunque credo di non essere ancora capace di implementare un rangetree in base a varie esigenze e non solo con problemi basilari, cerco altre fonti e implementazioni cercando di prendere una maggiore confidenza
Molto buono! Magari prova problemi leggermente più intricati