In questi giorni ho studiato il segment tree e la square root decomposition per la soluzione dei problemi:
Questo topic l’ho aperto per chiedere una mano su come ricercare, attraverso il segment tree o la sqrt dec. un elemento in O(\log N) oppure O(\sqrt N).
L’idea di entrambe le strutture dai che hai citato è quella di mantenere dei “rappresentanti”. Per esempio se hai un array di N elementi, con la sqrt decomposition manterrai un altro array di \sqrt N elementi, ognuno dei quali rappresenta una fetta lunga \sqrt N dell’array originale. Con un array lungo 1024, manterrai 32 elementi aggiuntivi (ognuno dei quali si occupa di rappresentare una fetta lunga 32 dell’array originale).
Per fare la ricerca di un singolo elemento, ti basta andarlo a leggere nell’array originale. Per fare la ricerca di un range di elementi, ti basta andare a leggere il valore memorizzato nei rappresentanti che vengono “toccati”. Se il range “si accavalla” su un rappresentante senza includere completamente tutti gli elementi originali da esso rappresentati, allora dovrai andare a leggere manualmente gli elementi di quel rappresentante.
Nota che, nell’esempio dell’array lungo 1024, questo significa (al caso peggiore) andare a leggere 31 elementi originali + 30 rappresentanti + 31 elementi originali. Se questa parte non è chiara, chiedi pure 
Con i segment tree, la storia si complica un po’ perché l’idea dei rappresentanti viene estesa anche ai rappresentanti stessi (la “lista” di rappresentanti ha a sua volta una lista di “super-rappresentanti”, e così via).
In questo vecchio topic puoi trovare alcune risorse utili:
Per quanto riguarda le due strutture dati, conosco il loro funzionamento. La mia domanda riguardava più precisamente il problema classifica. Andandomi a leggere la soluzione finale per capire il vero funzionamento del rangetree (segment tree), mi sono bloccato quando ho letto la seguente funzione che permette la ricerca del “pos-esimo 1”.
Parlando invece del problema vasi, volevo chiedere qual è l’utlizzo vero e proprio della square root decomposition per completare l’esercizio prendendo il massimo dei punteggi ottenibili da esso.
P.S: per chi magari ha già completato RangeTree2 volevo chiedere se potete guardare il codice in questo topic
Aldo
il rangetree non permette di cercare un elemento; bensì:
data una funzione f(l,r),tale che f(l,r) può essere calcolata in O(1) conoscendo f(l,m) e f(m+1,r) (con l\leqslant m<r), e f(i,i) è calcolabile in O(1), allora è possibile aggiornare f(i,i) in O(\log{}n) e calcolare f(l,r) in O(\log{}n).
Se vuoi cercare un elemento ti conviene orientarti su un BBST: Vasi1,Vasi2 si affrontano con strutture del genere, ed anche Classifica (seppur non per forza).
Scusa per la mia ignoranza ma non riesco a connettere ciò che hai detto con l’applicazione della sqrt decomposition in vasi1.
prima di risponderti: hai già risolto vasi, oppure devo stare attento a non spoilerarti la soluzione?
Non non l’ho ancora fatto.