# Rangetree

**URL:** <https://forum.olinfo.it/t/rangetree/3832>\
**Category:** Aiuto\
**Created:** [11 Agosto 2014, 12:06pm UTC](https://forum.olinfo.it/t/rangetree/3832 "2014-08-11T12:06:03Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [11 Agosto 2014, 12:06pm UTC](https://forum.olinfo.it/t/rangetree/3832/1 "2014-08-11T12:06:03Z")

</div>

Sto cercando di risolvere il problema rangetree1.

Le mie intenzioni sarebbero utilizzare una struttura del genere:

struct nodo{

&nbsp; &nbsp; int s; &nbsp; //start

&nbsp; &nbsp;&nbsp;int e;&nbsp;&nbsp; //end

&nbsp; &nbsp;&nbsp;int lazy; // flag

&nbsp; &nbsp; int value &nbsp; &nbsp; // l’ho messo ma non saprei se/come usarlo  

};

  

  

nel main creo un array:

struct nodo tree[2_n];_  

  

e lo inizializzo con questo metodo:

void create(struct nodo tree[], int n, int index, int s, int e){

&nbsp; &nbsp; tree[index].value = 0;

&nbsp; &nbsp;&nbsp;tree[index].lazy = 0;

&nbsp; &nbsp;&nbsp;tree[index].s = s;

&nbsp; &nbsp;&nbsp;tree[index].e = e;

&nbsp; &nbsp;&nbsp;if(index2 \< n){

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;create(tree, n, index_2, s, s+(e-s-1)/2);_

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;create(tree, n, index2+1, s+(e-s+1)/2, e);

&nbsp; &nbsp;&nbsp;}

}

  

il metodo con cui aggiorno la struttura, in pseudocodice, sarebbe qualcosa del genere:

int aggiorna(struct nodo tree[], index, a, b){

&nbsp; &nbsp;&nbsp;se l’intervallo è esatto (la modifica coinvolge tutti i sottonodi) inverto il lazy del nodo

&nbsp; &nbsp;&nbsp;else{

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;se c’è il laxy

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;lo propago ai sottonodi (inverto sia quello del nodo sia quelli dei sotto-nodi, i quali esistono sicuramente altrimenti avrei fatto il primo if perchè l’intervallo sarebbe stato giusto)

  

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;aggiorno i due sottonodi (solo quelli che servono, quindi 1 o entrambi)

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;}

&nbsp; &nbsp;&nbsp;}

}

  

// fine

  

1) questo metodo funzionerebbe

2) se sì come devo fare il metodo query?

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [11 Agosto 2014, 12:55pm UTC](https://forum.olinfo.it/t/rangetree/3832/2 "2014-08-11T12:55:21Z")

</div>

Io non l’ho risolto così. Cioè portavo con me due flag: outdated, inverti. I nodi outdated erano tutti quelli coinvolti dalla radice fino al nodo da invertire (incluso). Quando facevo la query andavo a vedete se un nodo era outdated ed in caso affermativo andavo a cercare tutti i nodi figli che lo erano (controllando se era da invertire ed in caso propagando l’evento) e quando arrivavo ad un nodo che aveva figli !outdated sommavo i loro valori per metterli in quelli del padre e così ricorsivsmente fino a quando non settavo il nodo a !outdated (sommando i suoi figli che ormai non lo erano più). Non so se ho reso l’idea

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [11 Agosto 2014, 1:17pm UTC](https://forum.olinfo.it/t/rangetree/3832/3 "2014-08-11T13:17:57Z")

</div>

non ho capito la differenza fra il flag outdated e inverti…

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [11 Agosto 2014, 1:40pm UTC](https://forum.olinfo.it/t/rangetree/3832/4 "2014-08-11T13:40:57Z")

</div>

Mmm infatti non mi sono spiegato bene. Un nodo che ha il flag inverti ha anche il flag outdated, però non vale il contrario. Questo perché se ad esempio ho un flag inverti al nodo che gestisce il range [3,4] e faccio una query sul range [1,4], questo non sarà aggiornato però andrò a vedere lo stesso i suoi figli (e quindi trovare quello da invertire) grazie al flag outdated.

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [11 Agosto 2014, 1:50pm UTC](https://forum.olinfo.it/t/rangetree/3832/5 "2014-08-11T13:50:27Z")

</div>

Io l’ho risolto in un altro metodo. Per ogni nodo mi tengo il numero di teste e il numero di capovolgimenti. Quando faccio un update, se il range del nodo è completamente contenuto nel range del’update aumento il capovolgi di uno e ritorno, altrimenti richiamo i due figli e aggiorno il valore delle teste (Facendo una query per ciascun nodo) e ritorno. Per la ricerca,invece, se il range del nodo è completamente dentro ritorno il numero di teste(se capov%2==0) o fine-inizio-teste+1. Se il range non è completamente contenuto, ritorno la somma della ricerca sui due figli.

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [11 Agosto 2014, 1:51pm UTC](https://forum.olinfo.it/t/rangetree/3832/6 "2014-08-11T13:51:28Z")

</div>

ma… il flag inverti significa che tutto il range gestito dal nodo va invertito giusto? il flag outdated invece?

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [11 Agosto 2014, 1:59pm UTC](https://forum.olinfo.it/t/rangetree/3832/7 "2014-08-11T13:59:33Z")

</div>

Per dire se un nodo è aggiornato o meno. Infatti se c’è un nodo discendente da invertire, questo nodo non sarà aggiornato e io me lo segno col flag outdated.

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [11 Agosto 2014, 2:10pm UTC](https://forum.olinfo.it/t/rangetree/3832/8 "2014-08-11T14:10:51Z")

</div>

> Per dire se un nodo è aggiornato o meno. Infatti se c'è un nodo discendente da invertire, questo nodo non sarà aggiornato e io me lo segno col flag outdated.
> 
> Lawliet

  

Quindi per la query cerchi ricorsivamente i nodi con i ranges che ti servono e:

1) &nbsp;se sono aggiornati (ovvero !outdated) ritorni il loro valore (che sarebbe la somma delle teste che stanno nei nodi sotto)

2) se non sono&nbsp;aggiornati (ovvero outdated) scendi nei nodi più in basso fino a quando non ne trovi di aggiornati (intanto porti avanti anche le eventuali inversioni da fare).&nbsp;Poi man mano che "torni su" setti i nodi come aggiornati (!outdated) e aggiorni il valore delle teste che stanno sotto.

  

La query è giusta?

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [11 Agosto 2014, 2:27pm UTC](https://forum.olinfo.it/t/rangetree/3832/9 "2014-08-11T14:27:08Z")

</div>

Sì è giusto 🙂

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [11 Agosto 2014, 2:30pm UTC](https://forum.olinfo.it/t/rangetree/3832/10 "2014-08-11T14:30:30Z")

</div>

Mentre per il metodo per l'aggiornamento cerchi ricorsivamente i nodi che ti interessano, man mano che ci passi li setti come non aggiornati e quando ne trovi uno da invertire completamente gli cambi il flag inverted.

  

Giusto?

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [11 Agosto 2014, 3:40pm UTC](https://forum.olinfo.it/t/rangetree/3832/11 "2014-08-11T15:40:19Z")

</div>

questo codice fa giusto il primo test case, poi metà li sbaglia e per metà va fuori tempo…

cosa sbaglio?

  

[http://pastebin.com/ppJ7TFPJ](http://pastebin.com/ppJ7TFPJ)

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [11 Agosto 2014, 3:55pm UTC](https://forum.olinfo.it/t/rangetree/3832/12 "2014-08-11T15:55:38Z")

</div>

I controlli falli in questo modo:

```
if(a&nbsp;\>=&nbsp;tree[index].s&nbsp;&&&nbsp;b&nbsp;\<=tree[index].e)
```

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [11 Agosto 2014, 4:06pm UTC](https://forum.olinfo.it/t/rangetree/3832/13 "2014-08-11T16:06:32Z")

</div>

quali controlli? ce ne sono tanti…

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [11 Agosto 2014, 4:11pm UTC](https://forum.olinfo.it/t/rangetree/3832/14 "2014-08-11T16:11:28Z")

</div>

Forse fai prima a postare direttamente il tuo codice perché l’algoritmo l’ho capito ma c’è qualcosa che non va nella mia implementazione…

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [11 Agosto 2014, 5:06pm UTC](https://forum.olinfo.it/t/rangetree/3832/15 "2014-08-11T17:06:39Z")

</div>

Sbagli sia nell’implementazione del St, che nel change, che nella query.

Perchè aggiungi n ad a e b? Per creare il ST è sufficiente chiamare il create in questo modo:

```
create(tree, 1, 0, n-1); //la dimensione non ti serve
```

Ed inoltre dovresti anche correggere la procedura in questo modo:

```
1. 
&nbsp; &nbsp; &nbsp; &nbsp; tree[index].value&nbsp;=&nbsp;0;
2. 
&nbsp; &nbsp; &nbsp; &nbsp; tree[index].inverti&nbsp;=&nbsp;0;
3. 
&nbsp; &nbsp; &nbsp; &nbsp; tree[index].aggiornato&nbsp;=&nbsp;1;
4. 
&nbsp; &nbsp; &nbsp; &nbsp; tree[index].s&nbsp;=&nbsp;s;
5. 
&nbsp; &nbsp; &nbsp; &nbsp; tree[index].e&nbsp;=&nbsp;e;
6. 
&nbsp; &nbsp; &nbsp; &nbsp;
7. 
&nbsp; &nbsp; &nbsp; &nbsp; create(tree,&nbsp;n,&nbsp;index2,&nbsp;s,&nbsp;(s+e)/2);
8. 
&nbsp; &nbsp; &nbsp; &nbsp; create(tree,&nbsp;n,&nbsp;index2+1,&nbsp;(s+e)/2+1,&nbsp;e);
```

Poi nel change è sufficiente controllare all’inizio se si è fuori dal range, e nel caso fare un return.

```
if(tree[index].s>b || tree[index].e<a)
return;
```

Poi non devi dire di capovolgere il range solo se stai esattamente nel range, ma è sufficiente che il nodo che stai considerando ne copra una parte. Cioè se devi capovolgere tutte le monete da [1,3] (in un range totale che va da 1 a 4), devi capovolgere i segmenti [1,2] e [3,3], in quanto il segmento [1,3] nell’albero non esiste.

Quindi:

```
if(tree[index].s>=a && tree[index].e<=b){
tree[index].inverti = (tree[index].inverti+1)%2;
tree[index].aggiornato = 0;
return; //non hai altro da fare in questo nodo
}
```

Se non sei nè fuori, nè dentro al range, visiti entrambi i figli. Inoltre sbagli anche a fare le visite. Infatti unisci le due implementazioni di un segment Tree, cioè quella che prevede il passaggio per parametri di L ed R (left e right) del segmento che visiti e quella che invece li memorizza nel nodo stesso. Quindi dopo queste due condizioni continui così:

```
tree[index].aggiornato=0;  
change(tree, n, index_2, a, b);  
change(tree, n, index_2+1, a, b);
//devi lasciare a e b che è il range iniziale da considerare
```

E così hai terminato il change:

```
void change(struct nodo tree[], int index, int a, int b){ //n non serve

if(tree[index].s\>b || tree[index].e\<a)

return;

if(tree[index].s\>=a && tree[index].e\<=b){  
 tree[index].inverti = (tree[index].inverti+1)%2;  
 tree[index].aggiornato = 0;  
 return; //non hai altro da fare in questo nodo  
 }

tree[index].aggiornato=0;  
 change(tree, n, index\*2, a, b);  
 change(tree, n, index\*2+1, a, b);

}
```

Prova a correggere la query da solo, tanto gli errori sono più o meno gli stessi.

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [11 Agosto 2014, 6:38pm UTC](https://forum.olinfo.it/t/rangetree/3832/16 "2014-08-11T18:38:12Z")

</div>

Ho fatto la query in questo modo, ma non va ancora bene...

  

int query(struct nodo tree[], int index, int a, int b){

  

&nbsp; &nbsp; if(tree[index].s \> b || tree[index].e \< a)

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;return 0;

  

&nbsp; &nbsp;&nbsp;if(tree[index].s \>= a && tree[index].e \<= b){

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;if(tree[index].aggiornato)

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;return tree[index].value;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;else{ 

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;if(tree[index].inverti){

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;if(tree[index].s != tree[index].e){

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index].inverti = 0;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index\*2].inverti = (tree[index\*2].inverti+1)%2;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index\*2+1].inverti = (tree[index\*2+1].inverti+1)%2;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index\*2].aggiornato = 0;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index\*2+1].aggiornato = 0;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index].value = query(tree, index\*2, a, b) + query(tree, index\*2+1, a, b);

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index].aggiornato = 1;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;return tree[index].value;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;else{

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index].inverti = 0;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index].value = (tree[index].value+1)%2;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index].aggiornato = 1;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;return tree[index].value;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}

&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}

}

}

&nbsp; &nbsp; if(tree[index].inverti){

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index].inverti = 0;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index\*2].inverti = (tree[index\*2].inverti+1)%2;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index\*2+1].inverti = (tree[index\*2+1].inverti+1)%2;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index\*2].aggiornato = 0;

&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;tree[index\*2+1].aggiornato = 0;

&nbsp; &nbsp; }

&nbsp; &nbsp;&nbsp;tree[index].value = query(tree, index\*2, a, b) + query(tree, index\*2+1, a, b);

&nbsp; &nbsp;&nbsp;tree[index].aggiornato = 1;

&nbsp; &nbsp;&nbsp;return tree[index].value;

}

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [11 Agosto 2014, 6:48pm UTC](https://forum.olinfo.it/t/rangetree/3832/17 "2014-08-11T18:48:34Z")

</div>

Sembrerebbe corretto… Lento ma corretto. Il problema è che ti va in timeout o ci sono output non corretti anche?

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [11 Agosto 2014, 6:58pm UTC](https://forum.olinfo.it/t/rangetree/3832/18 "2014-08-11T18:58:28Z")

</div>

il secondo task è sbagliato, poi ci sono un po’ di&nbsp;Execution killed with signal 11&nbsp;e un po’ di timeout

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [11 Agosto 2014, 7:03pm UTC](https://forum.olinfo.it/t/rangetree/3832/19 "2014-08-11T19:03:58Z")

</div>

Il vettore tree dev’essere dimensionato a 4_n. Comunque se ancora non va, posta il codice completo per favore._

  

 
_EDIT:_
 
_cioè togli tutta questa parte, non serve. Dimensiona il vettore a 4n e stai tranquillo che basta:_
 
_```
1. 
int&nbsp;i&nbsp;=&nbsp;0;
2. 
&nbsp; &nbsp;&nbsp;while(n&nbsp;\>&nbsp;pow(2,i))
3. 
&nbsp; &nbsp; &nbsp; &nbsp; i++;
4. 
&nbsp; &nbsp; &nbsp; &nbsp;
5. 
&nbsp; &nbsp;&nbsp;while(n&nbsp;!=&nbsp;pow(2,i))
6. 
&nbsp; &nbsp; &nbsp; &nbsp; n++;
```_

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [11 Agosto 2014, 7:09pm UTC](https://forum.olinfo.it/t/rangetree/3832/20 "2014-08-11T19:09:39Z")

</div>

[http://pastebin.com/1GBXs5Q6](http://pastebin.com/1GBXs5Q6)

  

se metto 4\*n si blocca il programma

[Pagina seguente](https://forum.olinfo.it/t/rangetree/3832.md?page=2)