Busque el valor máximo menor que V en una matriz compuesta por K funciones lineales

Question

Perdón por la falta de claridad en la descripción de la pregunta.

Tengo una matriz compuesta de longitud. $N$ compuesto de $k$ subarreglos lineales.Definimos un subarreglo lineal como un subarreglo contiguo del arreglo $[l,r]$ dónde $A[i]-A[i-1] = C$, una constante, para todos $l<i<=r$.(Nota: $C$ puede ser diferente para diferentes subarreglos;los elementos de la matriz son números enteros.) Tenga en cuenta que los subarreglos lineales no son separados (hay una intersección de elementos entre cualquier par de subarreglos lineales adyacentes).Por ejemplo, [1,3,5,4,3,2] tiene dos subarreglos lineales:[1,3,5] y [5,4,3,2].[1,3,5,1,2,3] tendría tres:[1,3,5], [5,1], [1,2,3].

Deseo encontrar varias consultas para el valor máximo que sea menor que un valor consultado $v$, en $o(K)$ y $o(N)$ tiempo por consulta, con $o(K^2)$ y $o(N)$ preprocesamiento.(Supongamos que la matriz ya se ha almacenado en términos de k subarreglos lineales, tal vez en términos de la constante C y longitud de cada subarreglo, con los subarreglos ordenados.Por lo tanto, se le proporciona la matriz con los puntos inicial y final de todos los subarreglos lineales, así como la constante lineal. C, como se describió anteriormente.Por lo tanto, no es necesario derivar los subarreglos lineales en primer lugar). De lo contrario, se agradecería una prueba (formal o no) de que no es posible hacerlo.

Por supuesto, un árbol de búsqueda binario equilibrado (BBST) o simplemente una clasificación logra el propósito, pero requiere $O(NlogN)$ preprocesamiento, que es demasiado.Verificar el valor válido más grande dentro de cada submatriz requiere $O(K)$ por consulta, lo cual nuevamente es demasiado.¿Sería posible que algo combinara ambos, tal vez?

Los algoritmos aleatorios están bien siempre que siempre obtengan la respuesta correcta y funcionen lo suficientemente rápido en el caso promedio, aunque se prefieren los algoritmos deterministas.

Gracias por cada una de las respuestas.Me preguntaba si tal vez hubo alguna investigación en la pregunta.No parece un tema demasiado oscuro, pero lamentablemente mi búsqueda no ha sido lo suficientemente competente.

EDITAR:Un método que parece útil.

Esta fue mi línea de pensamiento después de hacer la pregunta;Me pregunto si esto ayudaría de alguna manera.También utiliza la idea de módulo.Inicializar V=0, y permitir que cada subarreglo lineal se almacene como L,R;dónde L es el valor mínimo del subarreglo y R es el valor máximo.Cuando nos hacen una consulta de V, de alguna manera desincluimos elementos donde L>V y R<V (¿quizás usando múltiples dimensiones?) Una estructura de datos suplementaria almacena la diferencia teórica mínima del elemento en la matriz, que es algo así como L - V mod c[i].Básicamente, ahora necesitamos poder ejecutar una adición de rango en esta estructura de datos, pero si el valor de cualquier elemento se vuelve <0 o >=c[i] es necesario restablecerlo (por ej.si un elemento se vuelve igual a -1 con c[i]=5, se restablecerá a 4;si un elemento que llega a ser igual a 6 con el mismo c[i] se restablecería a 1);y también ejecutar consultas de rango mínimo.

Si se puede crear una estructura de datos de este tipo, el problema está resuelto.El problema es el módulo, ya que la adición de rango y la consulta de rango mínimo se pueden realizar fácilmente con un árbol de segmentos y una propagación diferida;así como la desinclusión de ciertos elementos.

Answer 1

No es posible garantizar que se encontrará el valor máximo que sea menor que un valor consultado. $v$ en $o(K)$ tiempo con preprocesamiento en $o(N)$ tiempo.

Esto se puede ver fácilmente en el siguiente caso extremo.Dejar $A$ ser cualquier conjunto de $N$ números enteros, que se compone de lo siguiente $K=N-1$ subarreglos lineales.

• el subarreglo $A[0], A[1]$ con $C=A[1]-A[0]$.
• el subarreglo $A[1], A[2]$ con $C=A[2]-A[1]$.
• $\cpuntos$
• el subarreglo $A[N-2], A[N-1]$ con $C=A[N-1]-A[N-2]$.

Con $o(N)$ preprocesamiento de tiempo y $o(K)=o(N)$ procesamiento del tiempo, un algoritmo no podrá ni siquiera leer algún número en $A$ cuando $N$ es lo suficientemente grande.(De hecho, la mayoría de los números en $A$.) Entonces, para algún valor consultado $q$, el algoritmo no podrá reconocer que $q+1$ aparece en $A$.

(La explicación anterior podría hacerse más rigurosa, por ejemplo, utilizando el método formal del adversario y un modelo de cálculo bien definido).

---

Parece que la pregunta más interesante debería ser si existe un algoritmo con $o(N\log N)$ preprocesamiento y $o(K)$ por consulta.O si hay un algoritmo con $o(N)$ preprocesamiento y $o(K)$ por consulta dada $K=o(N)$.De todos modos, eso suena como otra pregunta.