Problemi range tree

Aiuto
1

Sto provando a risolvere i problemi rangetree.
Questo è il mio codice, costruisco un albero, e quando devo girare un determinato intervallo, lo faccio girando le foglie più in alto possibile(per comodità gli elementi vanno da 1 a N e non da 0 a N-1):

//L e R sono i valori di input, i e j sono i valori degli estremi del //intervallo rappresentato dal nodo p_esimo
       int gira(int L,int R,int i,int j,int p){
          if(p<2*N)
            if(L>j || R<i)  return 0;
            else if(L<=i && R>=j) memo[p]+=1;
            else{
              gira(L,R,i,i+(j-i)/2,p*2);
              gira(L,R,i+(j-i)/2+1,j,p*2+1);
            }
        }
    ...
    
    if(tipo==0){
               gira(A,B,1,N,1);
          }
          else{
              int sol=0,p,S;
              //quando devo capire che stato ha un determinato elemento, //risalgo da esso fino alla radice
              for(int i=A;i<=B;i++){ 
                  p=N-1+i;
                  S=0;
                  while(p>0){
                      S+=memo[p];
                      p=(int)p/2;
                  }
                  sol+=(S%2);
              }
              printf("%d\n",sol);
          }

Prendo solo 40/100 e nei resto dei test case va in execution timed out, cosa ho sbagliato/dimenticato?

2

A che ti serve un Range Tree se tanto poi la query la esegui in O(NlogN) ? :stuck_out_tongue:
Quando tu cerchi la soluzione per il range [A;B] impieghi sì O(logN) per per il singolo elemento, ma poi questo lo fai per ogni elemento in quell’intervallo!
Alla peggio il tuo algoritmo gira in O(QNlogN) dove Q è il numero di query del problema.

Devi pensare ad un modo per sfruttare il Range Tree anche anche in risposta alle query e non solo per gli update.

3

per sapere lo stato di un determinato nodo devo per forza partire da quello 1 e arrivare fino in fondo, che alla peggio, se tengo in memoria i valori ogni volta che passo da un livello a quello successivo, a costo N. Non mi viene in mente niente di meglio :confused:

4

I nodi del tuo albero tengono in memoria il numero di giri da effettuare per un determinato range: questa è l’unica informazione utile che possono tenere?

5

Posso tenere anche il numero di monete che indicano croce, e il numero di quelle che indicano testa. Risolto, grazie!

1 Mi Piace