Questa tecnica non c'entra con "Sweep line Mo" (che è qualcosa di ancora più avanzato).
Dato un array , rispondi a query in cui devi determinare la massima frequenza di un elemento nel subarray . Le query sono online.
Soluzione offline: Mo, tenendo in ogni momento la frequenza di tutti gli elementi e, per ogni frequenza , la sua frequenza (cioè quanti elementi appaiono volte).
Nell'algoritmo di Mo, ordini le query in modo comodo e rispondi offline. In realtà puoi rispondere in modo simile partendo da "checkpoint" calcolati online! Ogni possibile query deve essere abbastanza vicina a un checkpoint.
Dato che la lezione è su square root, ovviamente i checkpoint sono i subarray con estremi multipli di (dove ).
Conviene prendere intervalli semiaperti. In questo modo, ad esempio, gli intervalli e sono disgiunti.
In questo modo, ogni sottoarray può essere approssimato a un checkpoint, e l'obiettivo è saper passare dalla risposta del checkpoint alla risposta di qualsiasi. I checkpoint sono .
Per comodità, puoi sempre approssimare per difetto (cioè cercare un checkpoint corto), quindi per passare da un checkpoint a devi solo supportare l'aggiunta di elementi, e non la rimozione. In altri casi potrebbe essere più comodo approssimare solo per eccesso e supportare solo la rimozione.
Purtroppo c'è un problema:
Per completare una query, impieghi . Quindi la complessità totale è . Se , la complessità è minima per , quindi ottieni una soluzione in (che usa tantissima memoria). In realtà si fa di meglio!
Da ora in poi, sempre.
La parte fastidiosa è il precalcolo, ma puoi sfruttare il fatto che per rispondere a una query non rimuovi mai elementi. Cosa succede se per ogni checkpoint salvi solo la frequenza massima?
Adesso, per estendere il sottoarray devi conoscere la frequenza dell'elemento che stai aggiungendo. Invece di precalcolarla, puoi semplicemente calcolarla ogni volta in (con una binary search su un vettore con le posizioni dell'elemento).
In questo caso non serve, ma sarebbe possibile rimuovere elementi? Per rimuovere un elemento, andrebbe eventualmente abbassata la sua frequenza massima, quindi bisogna sapere altre frequenze massime. In realtà basta conoscere frequenze massime.
Quindi puoi precalcolare la frequenza massima per ogni checkpoint in (risolvendo per ognuno degli estremi sinistri in ), e rispondere alle query in . La complessità finale è .
Nel calcolo dei checkpoint, stai automaticamente calcolando la risposta anche per i subarray tali che l'estremo sinistro è un multiplo di ma l'estremo destro no. Volendo, potresti usare anche questi come checkpoint, e per ogni query arrotondare solo , ma sprecheresti memoria.
In realtà esiste anche una . Per calcolare la frequenza di un elemento in in , basta saperla in e . Quindi è sufficiente salvare le frequenze in con multiplo di . In pratica questa soluzione non va meglio della precedente perché richiede molta memoria. C'è un modo per ottimizzare la memoria a (Sweep line Mo) ma funziona solo se le query sono offline, e rende l'implementazione un po' più difficile.
Dato un array , rispondi a query in cui devi determinare il numero di elementi distinti nel subarray . Le query sono online.
Soluzione offline: ordini le query per e mantieni un segment tree con nelle posizioni tali che è l'occorrenza più a destra di un elemento in . La risposta a ogni query è la range sum in .
Quando fai sweep line di questo tipo, è comodo visualizzarle in 2D (mettendo ad esempio sull'asse orizzontale e su quello verticale). In questo caso:
- point add: disegna un punto sul piano 2D, con peso uguale a quanto fai variare l'elemento;
- range sum: calcola la somma dei pesi dei punti in (cioè di tutti gli aggiornamenti fatti finora in .
In altre parole, puoi riscrivere le range query 1D online come range query 2D offline (e viceversa). Tra poco vedrai che in questo problema è più utile vederle come range query 2D offline.
Soluzione online: uguale alla precedente, ma con un segment tree persistente. La complessità è .
Il segment tree persistente ha una costante alta. Adesso vediamo una soluzione in che in pratica è altrettanto veloce.
Intanto puoi trovare una soluzione in . Puoi riciclare la soluzione precedente, e stavolta quando espandi il subarray inserendo un nuovo elemento non ti serve trovare la frequenza di , ma ti basta sapere se è già presente nel subarray. In particolare, è sufficiente precalcolare per ogni elemento la precedente occorrenza di un elemento uguale (prev[i]) e la successiva (next[i]). Quindi ogni query richiede solo invece di .
Stavolta puoi ottimizzare anche il precalcolo! Ricorda che stai precalcolando la risposta per checkpoint in tempo , e magari in questo caso (in cui il problema è un po' più facile) riesci a togliere il fattore .
Puoi riciclare l'idea della soluzione con il segment tree. Il problema attuale è "rispondi a tutte le query della forma ", e puoi farlo anche offline in . Quindi il problema iniziale è risolto in .
In realtà il segment tree non serve! Se guardi il problema come range query 2D offline, puoi notare che tutti i rettangoli su cui devi calcolare la somma hanno coordinate multiple di , e dividono il piano in regioni, quindi per ogni punto ti interessa sapere solo in quale regione sta, e non le coordinate esatte: puoi "rimpicciolire" il problema.
Il modo più semplice per rispondere alle query è quindi usare brutalmente le prefix sum 2D su questo problema rimpicciolito. Questa ottimizzazione toglie il fastidioso fattore .
L'ultima ottimizzazione si poteva notare anche senza passare dalle query 2D, ma la trovo più intuitiva in 2D.
C'è un altro modo (braindead, e con costante molto più alta) per ottenere una . Ricordiamo che nella soluzione in realtà stiamo facendo update e query sul segment tree. Se vogliamo una soluzione più veloce, , quindi le query sono più degli update. Dato che il problema è "sbilanciato", possiamo modificare l'altezza del segment tree (e ogni nodo ha figli) sperando di migliorare la complessità. corrisponde alla square root decomposition "standard".
In realtà, in questo modo un point update richiede , e una range query richiede , che è il contrario di quello che volevamo. Ma passando alle prefix sum i point update diventano range update in e le range query diventano point query in . Scegliendo , la complessità è .