Rechercher une valeur maximale inférieure à V dans un tableau composé de K fonctions linéaires

Question

Désolé pour le manque de clarté dans la description de la question.

J'ai un tableau composé de longueur $N$ composé de $K$ sous-réseaux linéaires.Nous définissons un sous-tableau linéaire comme un sous-tableau contigu du tableau $[l,r]$ où $A[i]-A[i-1] = CAD, une constante, pour tout $l<i<=r$.(Note: $CAN$ peut être différent pour différents sous-réseaux ;les éléments du tableau sont des entiers.) Veuillez noter que les sous-tableaux linéaires ne sont pas disjoints (il existe une intersection d'éléments entre n'importe quelle paire de sous-tableaux linéaires adjacents).Par exemple, [1,3,5,4,3,2] a deux sous-tableaux linéaires :[1,3,5] et [5,4,3,2].[1,3,5,1,2,3] en aurait trois :[1,3,5], [5,1], [1,2,3].

Je souhaite trouver plusieurs requêtes pour la valeur maximale inférieure à une valeur interrogée $V$, dans $o(K)$ et $o(N)$ temps par requête, avec $o(K^2)$ et $o(N)$ prétraitement.(Supposons que le tableau ait déjà été stocké en termes de K sous-réseaux linéaires, peut-être en termes de constante C et la longueur de chaque sous-tableau, les sous-tableaux étant ordonnés.Par conséquent, vous recevez le tableau avec les points de début et de fin de tous les sous-tableaux linéaires, ainsi que la constante linéaire C, comme décrit précédemment.Il n'est donc pas nécessaire de dériver les sous-tableaux linéaires en premier lieu.) Sinon, une preuve (formelle ou non) qu'il n'est pas possible de le faire serait appréciée.

Bien sûr, un arbre de recherche binaire équilibré (BBST) ou simplement un tri permet d'atteindre l'objectif, mais cela nécessite $O(NlogN)$ prétraitement, ce qui est trop.La vérification de la plus grande valeur valide dans chaque sous-tableau prend $O(K)$ par requête, ce qui est encore une fois trop.Serait-il possible de combiner les deux, peut-être ?

Les algorithmes aléatoires sont acceptables à condition qu’ils obtiennent toujours la bonne réponse et qu’ils fonctionnent assez rapidement dans le cas moyen, bien que les algorithmes déterministes soient préférés.

Merci pour toutes les réponses.Je me demandais s'il y avait eu des recherches sur la question, peut-être ?Cela ne semble pas être un sujet trop obscur, mais malheureusement mes recherches n'ont pas été suffisamment approfondies.

MODIFIER:Une méthode qui semble utile.

Voici ma réflexion après avoir posé la question ;Je me demande si cela aiderait d'une manière ou d'une autre.Il utilise également l'idée de modulo.Initialiser V=0, et permettent à chaque sous-tableau linéaire d'être stocké sous forme L,R;où L est la valeur minimale du sous-tableau et R est la valeur maximale.Lorsqu'on nous demande une requête pour V, nous excluons en quelque sorte les éléments où L>V et R<V (peut-être en utilisant plusieurs dimensions ?) Une structure de données supplémentaire stocke la différence théorique minimale de l'élément dans le tableau, ce qui ressemble à L - V mod c[i].Donc, essentiellement, nous devons maintenant pouvoir exécuter un ajout de plage sur cette structure de données, mais si la valeur d'un élément devient <0 ou >=c[i] il doit être réinitialisé (par ex.si un élément devient égal à -1 avec c[i]=5 il sera réinitialisé à 4 ;si un élément devenant égal à 6 avec le même c[i] serait remis à 1) ;et exécutez également des requêtes de plage minimale.

Si une telle structure de données peut être créée, le problème est résolu.Le problème est le modulo, car l'ajout de plage et la requête minimale de plage peuvent être facilement effectués avec une arborescence de segments et une propagation paresseuse ;ainsi que la suppression de certains éléments.

Answer 1

Il n'est pas possible de garantir la recherche d'une valeur maximale inférieure à une valeur recherchée. $V$ dans $o(K)$ temps avec prétraitement dans $o(N)$ temps.

Cela se voit facilement dans le cas extrême suivant.Laisser $A$ être n'importe quel tableau de $N$ entiers, qui est composé des éléments suivants $K=N-1$ sous-réseaux linéaires.

• le sous-tableau $A[0], A[1]$ avec $C=A[1]-A[0]$.
• le sous-tableau $A[1], A[2]$ avec $C=UNE[2]-UNE[1]$.
• $\cdots$
• le sous-tableau $A[N-2], A[N-1]$ avec $C=UNE[N-1]-UNE[N-2]$.

Avec $o(N)$ temps de prétraitement et $o(K)=o(N)$ traitement du temps, un algorithme ne sera même pas capable de lire un nombre dans $A$ quand $N$ est assez grand.(En fait, la plupart des chiffres $A$.) Donc, pour une valeur interrogée $q$, l'algorithme ne parviendra pas à reconnaître que $q+1$ apparaît dans $A$.

(L'explication ci-dessus pourrait être rendue plus rigoureuse, par exemple en utilisant la méthode formelle de l'adversaire et un modèle de calcul bien défini.)

---

Il semble que la question la plus intéressante à poser devrait être de savoir s’il existe un algorithme avec $o(N\log N)$ prétraitement et $o(K)$ par requête.Ou s'il existe un algorithme avec $o(N)$ prétraitement et $o(K)$ par requête donnée $K=o(N)$.Cela ressemble de toute façon à une autre question.