Así que aquí hay un problema, me dan una matriz de enteros, cuyo número es distinto, digamos que es
int[] data = {21, 34, 12, 88, 54, 73}; ahora que me gustaría ver si un subarreglo, o un rango, contiene un número que está en un rango (que también se da). En otras palabras, quiero ver si un rango de la matriz contiene un número que está en un rango. Por ejemplo, si tengo una función check(int a, int b, int l, int r) donde a y b son el rango de la matriz y l y r son el rango del número.
Entonces, para la matriz anterior, check(0, 2, 20, 50) debería devolver true ya que del index = 0 to 2 , hay 21, 34, 12 y hay dos números, 21, 34 , está en el rango de 20 to 50 .
Entonces, otro ejemplo sería check(2, 3, 20, 80) debería devolver false ya que, 12, 88 , no hay un número en el rango de 20, 80.
Estoy pensando en usar Segment Tree, ya que, como sé, RMQ (consulta mínima de rango) se puede resolver usando Segment Tree, por lo tanto, creo que Segment Tree también funcionaría en este problema; sin embargo, toda la "get" function del árbol de segmentos es "single" (quizás no sea la mejor palabra), por lo que me gustaría saber qué nodos debe contener el árbol de segmentos. ¿Hay algún algoritmo que pueda responder cada consulta en O(log(n)) mientras que el tiempo de "build" time no es O(n^2) , donde n es el tamaño de la matriz?
Nota: El uso de Segment Tree es solo una idea mía, se agradece cualquier otro enfoque.
O(N) es fácil:
public static boolean check(int[] data, int a, int b, int l, int r) { return Arrays.stream(data, a, b + 1).anyMatch(n -> n >= l && n <= r); }Sospecho que cualquier enfoque más eficiente de O grande dedicaría suficiente tiempo a construir la estructura de datos necesaria para que no valga la pena el esfuerzo a menos que esté haciendo muchas búsquedas en un conjunto de datos enorme. Incluso entonces, tal vez una versión paralela de la anterior podría ser lo suficientemente buena.
Es un poco exótico, pero un árbol rojo-negro persistente, o una variante persistente de cualquier otro árbol autoequilibrado, funcionaría.
Una estructura de datos persistente le permite a uno (tiempo y espacio) tomar "instantáneas" de la estructura de manera eficiente en diferentes momentos, y luego consultar esas instantáneas más tarde, recibiendo resultados basados en el estado de la estructura en el momento de la instantánea. Para este caso de uso, la consulta particular que querríamos hacer sería contar todos los elementos contenidos dentro de un rango dado (que se puede realizar en O(log n) si cada nodo se anota con el número de sus descendientes).
En este caso, comenzaría con una estructura vacía y, en el momento i , insertaría data[i] y luego almacenaría una instantánea como snapshot[i] . Entonces, check(a,b,l,r) se implementaría como return snapshot[b].countInRange(l,r) > snapshot[a].countInRange(l,r) . Es decir, si había más elementos en el rango de destino en el momento b que en el momento a , entonces se debe haber agregado algún elemento en el rango de destino entre a y b y, por lo tanto, satisface sus restricciones.
Si se implementa de manera óptima, el cálculo previo tomaría el tiempo O(n log n) y el espacio O(n) , y las consultas tomarían el tiempo O(log n) .
Si estuviera dispuesto a relajar el requisito de O(log n) para las consultas, un enfoque más simple y potencialmente más práctico sería un árbol kD bidimensional. Simplemente inserte cada data[i] como el punto (i, data[i]) , y luego realice una búsqueda de rango para a<=x<b, l<=y<r . Esto le da un tiempo de consulta de O(sqrt(n)) , que no es tan eficiente, pero mucho más fácil de codificar (o encontrar el código existente).