Implement a segment tree WA, TLE e Execution killed

Ciao a tutti, stavo provando a risolvere questo problema " Training - Implement a segment tree (olinfo.it) ", puntando a fare 60 punti (non ho implementato get_min e lower_bound, li farò in un altro momento), ma comunque, ottengo 0/100 con questo codice, nonostante l’esempio (da cui ho tolto le chiamate get_min e lower_bound) funzioni:

Questo è l'input dell'esempio senza get_min e lower bound

10 16
17 -15 13 27 -29 -6 -15 -29 1 -9
1 2 10
2 0 9 4
3 2 4 -22
3 6 7 3
1 0 6
3 1 9 1
3 5 10 22
3 9 10 0
1 7 10
2 0 7 -5
3 1 5 15
2 0 9 -15
1 1 10
1 7 10
1 7 8
1 0 10

output: -47 -61 44 18 14 7 19 (che è corretto, allego anche uno screen dell’output).

Output screen

Comunque, essendo una delle prime volte in cui implemento un segment tree, ho seguito quasi alla lettera questa guida Efficient and easy segment trees - Codeforces che spiega i segment tree iterativi (mi hanno detto che sono più efficienti e semplici da capire);
Nonostante questo, mi dà 0/100 e dopo svariate ore passate a provare a debuggarlo, nn riesco ancora a capire quale sia il problema…

Codice
#include <iostream>
#include <vector>
using namespace std;

#define _showTree 	cout<<"Segment Tree: "<<endl;for (auto it: SegTree)cout<<it.first<<"  ";cout<<endl;
#define _showLazy 	cout<<"Lazy propagation: "<<endl;for(auto it: Lazyprop)cout<<it<<"    "; cout<<endl;

int len, h;
vector<pair<long long, long long>> SegTree;
vector<long long> Lazyprop;

void init(vector<long long> a){
    len = a.size();
    SegTree.resize(2 * len);
    Lazyprop.resize(len+1, 0);
    for(int i = 0; i < len; i++){
        SegTree[i+len].first = a[i]; 
        //SegTree[i+len].second = a[i];
	}
    //store sums in the first segment tree
    for(int i = len-1; i > 0; i--)
        SegTree[i].first = SegTree[i << 1].first + SegTree[i << 1 | 1].first;
         
    //keep minimum in the 2^ segment tree
    //for(int i = len-1; i > 0; i--)
    	//SegTree[i].second=min(SegTree[i*2].second, SegTree[i*2 + 1].second);	
    //_showTree
}

//add value to the element in interval [l, r) --> l include, r not included.
void update(int pos, int value, int k) {
	SegTree[pos].first += (value * k);
	//if the node is a parent, we won't update the children but take note of the increment in order to do it later:
	if(pos < len)	
		Lazyprop[pos] += value;
}
void calculateValue (int pos, int k){
	SegTree[pos].first = SegTree[pos << 1].first + SegTree[pos << 1 | 1].first + Lazyprop[pos] * k;
}
void updateParents(int l, int r){
	//_showTree
	int k = 2; 
	l += len, r += len - 1;
	for(; l > 1; k <<= 1){
		l >>= 1, r >>= 1;
		for(int i = r; i >= l; i--){
			calculateValue(i, k);			
		}
	}
}

void push(int l, int r) {			//propagate to children only if needed (Lazyprop[pos] != 0)
	int he = h, k = 1 << (h-1);
	for(l += len, r += len - 1; he > 0; he--, k >>= 1){
		for(int i = (l >> he); i <= r >> he; i++){
			if(Lazyprop[i] != 0){
				update((i << 1), Lazyprop[i], k);
				update((i << 1 | 1), Lazyprop[i], k);
				Lazyprop[i] = 0;
				
			}
		}
	}
}
long long get_sum(int l, int r){  // the interval is [l, r) --> l included and r not included.
    long long sum=0;	
	push(l, l + 1); push(r - 1, r);		//propagates to children
	l +=len; r += len;
	//_showTree
	for(; l < r; l >>= 1, r >>= 1){
		/*if l (the node considered) is odd, it means you're processing the right child, so it must be taken.
		  however, you can take their sum from their parent (l/=2 and r/=2)*/
		if(l&1)	{
			sum += SegTree[l++].first; 
		} 		
		//only if r is odd (if you're processing both left and right childrens)											
		if(r&1) {
			sum += SegTree[--r].first; 	
		}	
	}
	//cout<<endl;
	//_showTree _showLazy
	return sum;
}
void add(int l, int r, long long value){
	if(value == 0) return;
	int lstart = l, rstart = r, k = 1;
	l += len;	r += len;
	for(; l < r; l >>= 1, r >>= 1, k <<= 1){
		if(l&1)
			update(l++, value, k);
		if(r&1)
			update(--r, value, k);
	}
	//_showTree cout<<endl;	 _showLazy
	//propagate only to the parents (propagating to parents is necessary, but it's not the same for children)
	updateParents(lstart, lstart + 1); updateParents(rstart - 1, rstart);		
	//_showTree cout<<endl; _showLazy
}

void set_range(int l, int r, long long x)
{
	int lstart = l, rstart = r;
	push(l, l + 1); push(r - 1, r);
	l += len; r += len; 
    for (int i = l; i < r; i++) {   		
        Lazyprop[i] = 0;
   		SegTree[i].first = x;
        for (int j = i >> 1; j > 0; j >>= 1) {
            SegTree[j].first = SegTree[j * 2].first + SegTree[j * 2 + 1].first;
        }
    }
}

long long get_min(int l, int r){
    return 0;
}
int lower_bound(int l, int r, long long x){
    return 0;
};
/*int main(int argc, char *argv[]) {
	int n, q;
	cin >> n >> q;
	h = sizeof(int) * 8 - __builtin_clz(n);
	vector<long long>a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	init(a);
	for (int i = 0; i < q; i++) {
		int op, l, r;
		long long x;
		cin >> op;
		cin >> l >> r;
		if (op == 2 or op == 3 or op == 5)
			cin >> x;
		if (op == 1) cout <<get_sum(l, r) << "\n";
		if (op == 2) add(l, r, x);
	    if (op == 3) set_range(l, r, x);
		//if (op == 4) cout <<"min "<< get_min(l, r) << "\n";
		//if (op == 5) cout << lower_bound(l, r, x) << "\n";
	    cout<<endl;
	}
		return 0;  }*/

Probabilmente, l’execution killed error si verifica all’interno del set_range pk in una soluzione precedente ottengo 20/100 e l’unica modifica è stata nel set_range (con queste modifiche il set_range fa 20/100, però sbaglia l’esempio, quindi è probabile che sia sbagliato):

set_range() che fa 20/100
void set_range(int l, int r, long long x)
{
	int lstart = l, rstart = r;
	l += len; r += len; 
	push(l - len, l - len + 1);
    for (int i = l; i < r; i++) {
   		SegTree[i].first = x;
        Lazyprop[i - len] = 0;
        for (int j = i >> 1; j > 0; j >>= 1) {
            SegTree[j].first = SegTree[j * 2].first + SegTree[j * 2 + 1].first;
        }
    }
}

Ringrazio in anticipo chi mi risponde e se avete dubbi sul codice che ho scritto fatemelo sapere.
Allego di sotto gli screen dei risultati degli output se vi possono essere utili.


Sinceramente penso non sia un’ottima idea imparare a usare i segment tree scrivendo la versione iterativa. Non è scontato il modo in cui funzionano e specialmente in questo problema dove ci sono molti tipi di query e due update su range le cose si complicano non poco. Detto questo non ti so aiutare nel debugging perché non ho idea di come funzioni un segment tree iterativo :grin:

1 Mi Piace

ah, okok haha.
Comunque per quanto riguarda il funzionamento dei segment tree iterativi ho compreso l’essenziale di base: come costruirli e come fare query e update (è ovvio che se mi trovo davanti esercizi in cui si usano segment tree modificati non sono sicuro di essere in grado di risolverli, ma col tempo ci prenderò la mano…).
Ma perchè te non consigli la versione iterativa? (è un motivo di difficoltà di comprensione oppure è meno efficiente? )
Grazie comunque per la risposta. : )

Non c’è dubbio sul fatto che siano più efficienti e più corti da scrivere. Semplicemente la differenza di prestazione non vale, a mio avviso, la difficoltà di adattamento. Ho letto il blog di codeforces che hai allegato e sicuramente si riescono a fare le query e gli update che richiede il problema, ma già dalla lazy propagation la faccenda si complica un pelo. Rimangono comunque meno righe rispetto a quello ricorsivo ma risulta più difficile capire cosa sta effettivamente succedendo.

Lo stesso ragionamento si può fare con il Fenwick tree. È molto più corto da scrivere ed è più efficiente. Tuttavia è meno versatile e non è così immediato capire perché funziona. Di conseguenza mi capita spesso di scrivere un segment (ricorsivo) anche se si può usare un Fenwick. Scrivendolo più frequentemente sono più sicuro nell’implementazione e altrettanto del suo funzionamento. Solo in un secondo momento scrivo il Fenwick, se dovessi ottimizzare ulteriormente il codice.

Capire a fondo come e perché funzionano le strutture dati e gli algoritmi è fondamentale per poterlo adattare e applicare in contesti differenti non banali, scrivere “a memoria” strutture dati più efficienti ha più svantaggi che vantaggi. Primo fra tutti, se c’è un bug in gara diventa infernale trovarlo.

Scusa per questo messaggio troppo lungo e forse inutile. Ricordo che questa è la mia opinione e sicuramente qualcuno la penserà diversamente.

1 Mi Piace

Essendo io ancora agli inizi mi fa veramente piacere leggere le opinioni di altre persone con più esperienza e ti ringrazio moltissimo; Ora ho compreso i pro e i contro di entrambi quindi guarderò i segment ricorsivi e sceglierò quelli che mi verranno più facili, grazie di tutto!
Ma intanto, se qualcuno che normalmente costruisce i segment iterativamente ha letto questo post e vuole aiutarmi, mi farebbe tantissimo piacere

1 Mi Piace

@MatteoArcari Comunque complimenti x la gara che hai svolto oggi! :tada:

1 Mi Piace