¿Qué son las preguntas basadas en consultas en línea y fuera de línea en la programación competitiva?

Las preguntas basadas en consultas de la programación competitiva son principalmente de dos tipos:

1. Consulta fuera de línea.
2. Consulta en línea.
    

Consulta fuera de línea

Un algoritmo fuera de línea nos permite manipular los datos a consultar antes de que se imprima cualquier respuesta. Por lo general, esto solo es posible cuando las consultas no actualizan el conjunto de elementos original antes de imprimir el resultado.

Características:

1. La consulta sin conexión ofrece una gama mucho más amplia de usos en comparación con la consulta en línea.
2. Proporcionan una mayor facilidad de uso y la oportunidad de personalizar los datos de devolución.
3. La solución fuera de línea primero lee todas las consultas y las preprocesa (como ordenar las consultas para hacer que el proceso adicional también sea eficiente), luego calcula y genera la respuesta de cada consulta en el orden inicial dado.
4. En una configuración fuera de línea, todas las consultas se presentan por adelantado.
5. Los problemas son más fáciles de resolver en una configuración fuera de línea, ya que uno puede reordenar las consultas o puede trabajar en varias consultas al mismo tiempo.
6. Ordenar las consultas y los datos originales puede ayudar a lograr una mejor eficiencia de O(N + Q) en lugar de la eficiencia de O(N * Q), que es común en los casos en que la ordenación no es posible ya que las consultas siguen transmitiéndose, como en el caso de las consultas en línea. .

Un ejemplo de una consulta fuera de línea es el árbol de segmentos.

Ejemplo: 

Dada una array A[] = {2,3,5,6,7,9} y la tarea es responder q consultas para esta array.
Cada consulta contiene dos números enteros l y r y requiere generar la suma de la array de l a r .

Condición necesaria para la consulta sin conexión: 

Esta técnica se puede usar solo cuando la respuesta de una consulta no depende de las respuestas de consultas anteriores, ya que después de ordenar, el orden de las consultas puede cambiar.

Cuándo usar la consulta sin conexión:

1. Las consultas sin conexión se deben usar para informes grandes.
2. Cuando todas las consultas se conocen por adelantado.

Consulta en línea

Para responder a las consultas en orden de aparición y no puede manipular previamente las consultas para un enfoque eficiente, dichas consultas se denominan consultas en línea. 

Características:

1. En este tipo de consultas, nuestros datos también pueden actualizarse.
2. La respuesta no se puede precalcular de antemano.
3. La respuesta de una consulta también afecta la respuesta de otras consultas. Por lo tanto, cada consulta se responde una por una.
4. Las consultas en línea ofrecerán una respuesta poco después de la consulta, lo que permitirá una rápida resolución de la consulta.

Ejemplo:

Dada una array A = {2,3,5,6,7,9} y la tarea es responder q consultas para esta array.
Cada consulta es de dos tipos

1. Actualizar el i-ésimo índice por A[i] = x 
2. Encuentra la suma de l a r

En este ejemplo, después de cada consulta, los datos de la array están cambiando. Por lo tanto, no se puede resolver con el método de consulta fuera de línea.

Condición necesaria para la consulta en línea:

Las consultas en línea se pueden usar solo cuando los datos están cambiando y cuando la clasificación no es posible debido a la transmisión continua de consultas. 

Cuándo usar la consulta en línea:

1. Las consultas en línea deben utilizarse cuando es necesario consultar algunas transacciones en una fecha y hora específicas.
2. Deben usarse cuando se requiere consultar consultas pequeñas rápidamente.

Consulta fuera de línea vs Consulta en línea

A continuación se muestran algunas de las diferencias entre la consulta sin conexión y la consulta en línea:

No. S.	Consulta fuera de línea	Consulta en línea
1	Esto permite la manipulación de los datos a consultar antes de que se imprima cualquier respuesta.	Las consultas no pueden manipularse previamente y responder a las consultas en orden de aparición.
2	Las consultas sin conexión son posibles cuando las consultas no actualizan el conjunto de elementos original antes de imprimir el resultado.	En consultas en línea, el conjunto de datos también puede actualizarse.
3	Las consultas fuera de línea proporcionan una mayor eficiencia de O(N + Q), ya que la clasificación de las consultas y los datos originales se realiza antes de calcular el resultado.	En el caso de las consultas en línea, las consultas siguen fluyendo debido a que no es posible ordenar las consultas y la eficiencia se reduce a O (N * Q).
4	Las consultas sin conexión se deben usar para informes grandes.	Las consultas en línea deben usarse cuando se requiere consultar pequeñas consultas rápidamente
5	En las consultas fuera de línea, todas las consultas están presentes de antemano.	En las consultas en línea, las consultas siguen transmitiéndose.
6	En una consulta fuera de línea, la respuesta de una consulta no depende de la respuesta de la consulta anterior.	En una consulta en línea, la respuesta de una consulta afecta la respuesta de otras consultas.