Cerca il valore massima inferiore a V in un array composto da funzioni lineari K

Question

Scusa per la mancanza di chiarezza nella domanda Descrizione.

Ho un array composto da lunghezza $ N $ composto da $ k $ Subarray lineari. Definiamo un sottoarray lineare come un sottotatore contiguo dell'array $ [l, r] $ dove $ A [i] - A [I-1]= c $ , una costante, per tutti $ l . (Nota: $ c $ potrebbe essere diverso per diversi sottodischi; gli elementi dell'array sono numeri interi). Si noti che i sottoarray lineari non sono disgiunti (c'è un intersezione di elementi tra qualsiasi coppia di sottocayer lineari adiacenti). Ad esempio, [1,3,5,4,3,2] ha due sottouria lineari: [1,3,5] e [5,4,3,2]. [1,3,5,1,2,3] avrebbe tre: [1,3,5], [5,1], [1,2,3].

Desidero trovare più interrogazioni per il valore massimo per il valore massimo che è inferiore a un valore di query $ V $ , in $ o (k) $ e $ o (n) $ tempo per query, con $ o (k ^ 2) $ e $ o (n) $ Preprocessing. (Supponiamo che l'array sia già stato memorizzato in termini di sottocayer k lineare, forse in termini di costante c e lunghezza di ciascuna sottoarray, con i sottouria ordinati. Pertanto , ti viene data l'array con i punti di partenza e finale di tutti i sottoarraggi lineari, nonché la costante lineare c , come descritto in precedenza. Quindi, non è necessario ricavare i sottoarraggi lineari nel primo posto.) Altrimenti, una prova (formale o meno) che non è possibile farlo sarebbe apprezzata.

Naturalmente, un albero di ricerca binario equilibrato (BBST) o semplicemente l'ordinamento raggiunge lo scopo, ma richiede $ o (nlogn) $ Preprocessing, che è troppo . Controllo del più grande valore valido all'interno di ciascun sottotay prende $ o (k) $ per query, che è ancora troppo. Sarebbe possibile che qualcosa combini entrambi, forse?

Gli algoritmi randomizzati vanno bene finché raggiungono sempre la risposta corretta e funzionano abbastanza velocemente nel caso medio, anche se gli algoritmi deterministici sono preferiti.

Grazie per tutte le risposte. Mi stavo chiedendo se ci fosse qualche ricerca nella domanda, forse? Non sembra troppo oscurare un argomento, ma sfortunatamente la mia ricerca non è stata abbastanza competente.

Modifica: un metodo che sembra utile.

Ecco la mia linea di pensiero dopo aver fatto la domanda; Mi chiedo se questo avrebbe aiutato in qualche modo. Usa anche l'idea di Modulo. Inizializzato V=0 e consentire a ciascuna Subarray lineare di essere memorizzata come L,R; Dove L è il valore minimo del sottoarray e R è il valore massimale. Quando ci viene data una query per V, in qualche modo ininclude gli elementi in cui L>V e R<V (forse utilizzando più dimensioni?) Una struttura dei dati supplementari memorizza la differenza teorica minima dell'elemento nell'array, che è qualcosa come L - V mod c[i]. Così essenzialmente, ora dobbiamo essere in grado di eseguire un intervallo aggiungere questa struttura dati, ma se il valore di qualsiasi elemento diventa <0 o >=c[i] deve essere ripristinato (ad esempio se un elemento diventa uguale a -1 con c [i ]= 5 sarebbe stato ripristinato a 4; se un elemento che diventa uguale a 6 con lo stesso C [I] sarebbe stato ripristinato a 1); e anche eseguire interrogazioni minime della gamma.

Se è possibile effettuare tale struttura dei dati, il problema è risolto. Il problema è il modulo, come intervallo Aggiungi e intervallo di query minima può essere facilmente eseguito con un albero di segmento e una propagazione pigra; così come la disinclusione di alcuni elementi.

Answer 1

Non è possibile garantire di trovare il valore massimo che è inferiore a un valore di query $ V $ in $ o (k) $ tempo con pre-elaborazione in $ o (n) $ tempo.

Questo può essere visto facilmente nel seguente caso estremo. Let $ A $ Sii qualsiasi array di $ N $ interi, composti dalla seguente $ k= n-1 $ Subarray lineari.

.
• il sottoarray $ A [0], a [1] $ con $ c= a [1] -a [0] $ .
• il sottoarray $ a [1], a [2] $ con $ c= a [2] -a [1] $ .
• $ \ cdots $
• il sottoarray $ A [N-2], A [N-1] $ con $ c= a [ N-1] -a [n-2] $ .

con $ o (n) $ preprocessing temporale e $ o (k)= o (n) $ Elaborazione del tempo, un algoritmo non sarà in grado di leggere anche un certo numero in $ a $ quando $ N $ è abbastanza grande. (Infatti, la maggior parte dei numeri in $ A $ .) Quindi, per alcuni valore interrogato $ q $ , l'algoritmo non riesce a riconoscerire che $ Q + 1 $ appare in $ a $ .

(la spiegazione sopra potrebbe essere resa più rigorosa, ad esempio utilizzando il metodo formale del avversario e un modello di calcolo ben definito.)

---

.

Sembra che la domanda più interessante che chieda dovrebbe essere se c'è un algoritmo con $ o (n \ log n) $ preprocessing e $ o (k) $ per query. O se c'è un algoritmo con $ o (n) $ preprocessing e $ o (k) $ per query Dato $ k= o (n) $ . Sembra un'altra domanda, comunque.