Rangetree

Aiuto
1

Sto cercando di risolvere il problema rangetree1.

Le mie intenzioni sarebbero utilizzare una struttura del genere:
struct nodo{
    int s;   //start
    int e;   //end
    int lazy; // flag
    int value     // l’ho messo ma non saprei se/come usarlo
};


nel main creo un array:
struct nodo tree[2n];

e lo inizializzo con questo metodo:
void create(struct nodo tree[], int n, int index, int s, int e){
    tree[index].value = 0;
    tree[index].lazy = 0;
    tree[index].s = s;
    tree[index].e = e;
    if(index2 < n){
        create(tree, n, index2, s, s+(e-s-1)/2);
        create(tree, n, index2+1, s+(e-s+1)/2, e);
    }
}

il metodo con cui aggiorno la struttura, in pseudocodice, sarebbe qualcosa del genere:
int aggiorna(struct nodo tree[], index, a, b){
    se l’intervallo è esatto (la modifica coinvolge tutti i sottonodi) inverto il lazy del nodo
    else{
            se c’è il laxy
                    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)

            aggiorno i due sottonodi (solo quelli che servono, quindi 1 o entrambi)
            }
    }
}

// fine

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

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

3

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

4

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.

5

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.

6

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

7

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.

8
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)  se sono aggiornati (ovvero !outdated) ritorni il loro valore (che sarebbe la somma delle teste che stanno nei nodi sotto)
2) se non sono 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). Poi man mano che "torni su" setti i nodi come aggiornati (!outdated) e aggiorni il valore delle teste che stanno sotto.

La query è giusta?
9

Sì è giusto :slight_smile:

10
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?
11

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

cosa sbaglio?

http://pastebin.com/ppJ7TFPJ
12

I controlli falli in questo modo:

if(a >= tree[index].s && b <=tree[index].e)
13

quali controlli? ce ne sono tanti…

14

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

15

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.         tree[index].value = 0;

    2. 

  2.         tree[index].inverti = 0;

    3. 

  3.         tree[index].aggiornato = 1;

    4. 

  4.         tree[index].s = s;

    5. 

  5.         tree[index].e = e;

    6. 

  6.        
    7. 

  7.         create(tree, n, index2, s, (s+e)/2);

    8. 

  8.         create(tree, n, index2+1, (s+e)/2+1, e);

    9.
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, index2, a, b);

change(tree, n, index2+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.

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

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

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

    if(tree[index].s >= a && tree[index].e <= b){
        if(tree[index].aggiornato)
                return tree[index].value;
        else{
                if(tree[index].inverti){
                        if(tree[index].s != tree[index].e){
                                tree[index].inverti = 0;
                                tree[index*2].inverti = (tree[index*2].inverti+1)%2;
                                tree[index*2+1].inverti = (tree[index*2+1].inverti+1)%2;
                                tree[index*2].aggiornato = 0;
                                tree[index*2+1].aggiornato = 0;
                                tree[index].value = query(tree, index*2, a, b) + query(tree, index*2+1, a, b);
                                tree[index].aggiornato = 1;
                                return tree[index].value;
                           }
                           else{
                                tree[index].inverti = 0;
                                tree[index].value = (tree[index].value+1)%2;
                                tree[index].aggiornato = 1;
                                return tree[index].value;
                           }
                   }
}
}
    if(tree[index].inverti){
        tree[index].inverti = 0;
        tree[index*2].inverti = (tree[index*2].inverti+1)%2;
        tree[index*2+1].inverti = (tree[index*2+1].inverti+1)%2;
        tree[index*2].aggiornato = 0;
        tree[index*2+1].aggiornato = 0;
    }
    tree[index].value = query(tree, index*2, a, b) + query(tree, index*2+1, a, b);
    tree[index].aggiornato = 1;
    return tree[index].value;
}
17

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

18

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

19

Il vettore tree dev’essere dimensionato a 4n. 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 i = 0;

    2. 

  2.     while(n > pow(2,i))

    3. 

  3.         i++;

    4. 

  4.        
    5. 

  5.     while(n != pow(2,i))

    6. 

  6.         n++;

    7.

20

http://pastebin.com/1GBXs5Q6


se metto 4*n si blocca il programma