Muraglia (aiuto con segment tree)

Aiuto
1

Ciao, sto cercando di risolvere il problema con un segment tree, è la prima volta che li utilizzo e ho capito più o meno come funziona per fare la somma o trovare il valore massimo ad esemio. Credo di aver implementato bene le funzioni inizializza e cambia (correggetemi se c’è qualcosa di sbagliato), ma non so come impostare la funzione chiedi, non ci so proprio mettere mano.

#include <utility>
#include <vector>

using namespace std;

vector <int> segtree;
int segtree_size;

pair<int, int> chiedi(int x) 
{
	
    return { };
}

void cambia(int x, int h) 
{
	x=x+(segtree_size/2);
	segtree[x]=h;
	while (x>0) 
	{
	    x=(x-1)/2;
	    segtree[x]=max(segtree[x*2+1], segtree[x*2+2]);
	}
}

void inizializza(int N, vector<int> H) 
{
	segtree_size=1;
	while (segtree_size<N)
		segtree_size=segtree_size*2;
	segtree_size=segtree_size*2-1;
	segtree.resize(segtree_size, 0);
	
	for (int i=0; i<N; i++)
	{
		segtree[segtree_size/2+i]=H[i];
	}
	
	for (int i=segtree_size/2-1; i>=0; i--) 
	{
	    segtree[i]=max(segtree[i*2+1], segtree[i*2+2]);
	}
}
2

Ciao, intanto pensa a un modo semplice di implementare le query in \mathcal{O}(\log^2N). Hint: puoi fare una binary search sul primo range che contiene un numero più grande di H[x]. Già così forse si riesce a farlo passare scrivendolo abbastanza bene.
Tuttavia esiste anche un modo per rispondere alle query in \mathcal{O}(\log N), per trovarlo può essere utile considerare che un range corrisponde a \mathcal{O}(\log N) nodi del segment tree, e che trovare il primo valore più maggiore di H[x] in un sottoalbero del segment si fa facilmente in \mathcal{O}(\log N) migliorando l’idea di prima.

3

Grazie mille per la risposta, non molto sicura di aver capito come procedere, potresti farmi un esempio partico?

4

Per la \mathcal{O}(\log^2 N), quello che vuoi fare è trovare il primo elemento maggiore di H[x] a destra di x. Sia x + k l’indice di questo elemento, allora \max H[x+1..x+\delta] \le H[x] \iff \delta < k. Fissato \delta puoi trovare Q=\max H[x+1..x+\delta] in \mathcal{O}(\log N) con una query sul segment. Ora se Q \le H[x] sai che k > \delta e viceversa quindi puoi fare una binsearch per trovare k.
Per la \mathcal{O}(\log N) quello che succede è che hai \mathcal{O}(\log N) nodi sul segment che corrispondono all’intervallo ]x, N[ (puoi provare a convincertene disegnando il segment), e a te interessa quello più a sinistra il cui massimo sia >H[x], cosa che puoi trovare in \mathcal{O}(\log N) semplicemente scorrendoli tutti. Una volta che hai trovato questo range ti interessa trovare l’elemento più a sinistra di quel range che sia >k, e questa cosa puoi farla semplicemente controllando il massimo M del figlio sinistro del nodo corrente e ricorrendo sul figlio sinistro se M>H[x] e sul figlio destro altrimenti. Quando arrivi in una foglia hai trovato l’elemento cercato.

1 Mi Piace