Sí, esto se puede lograr usando una versión de transmisión de un árbol de segmentos. La idea básica es simple: por cada segundo elemento que llegue, almacene el máximo de este y el elemento anterior en una segunda matriz. En el tiempo t, esta matriz tiene un tamaño aproximado de t / 2. Luego, por cada segundo elemento que agregue a esa matriz, almacene el máximo de ella y el elemento anterior que agregó a la misma matriz a otra matriz (que tiene aproximadamente t / 4 elementos). Siga creando matrices hasta que la matriz final tenga 1 elemento.
A medida que hace esto en una secuencia, eventualmente la matriz final con 1 elemento obtendrá un segundo elemento, en cuyo punto agregaría otra matriz de tamaño 1, con el máximo de esos dos elementos. Tenga en cuenta que esta estructura usa t + t / 2 + t / 4 + … = O (t) espacio, por lo que esto no es malo en términos de uso del espacio.
En términos del tiempo que lleva colocar elementos en esta estructura de datos, ya que están listos desde la secuencia, escribimos una entrada en la matriz base el 100% del tiempo, una entrada en la siguiente matriz el 50% del tiempo, una entrada a la matriz después de ese 25% del tiempo, etc. Al hacer el cálculo, esto promedia solo 2 escrituras (y una cantidad proporcional de cómputo) por elemento leído. Entonces, la inserción es O (1) por elemento.
- ¿Cuáles son algunos de los temas / conceptos más importantes para el examen APAC de Google para estudiantes universitarios de 2016?
- ¿Cuáles son las tres rondas de entrevistas para AllinCall Research and Solution?
- ¿Cuáles son los tipos de preguntas basadas en MapReduce que se hacen durante las entrevistas en Google?
- ¿Cómo debo prepararme para las entrevistas de Google, Facebook y Microsoft con CLRS considerando que realmente no soy bueno en Data Structures?
- Cómo prepararse para la entrevista de Microsoft Skype para el puesto de consultor asociado
En cuanto a la operación que solicitó en la pregunta, la idea es que si queremos el máximo de un rango como 1-7 de una matriz a, podemos dividirlo en max (a [1], max (a [2 … 7])). Pero max (a [2 … 7]) puede ser respondido completamente por la matriz reducida de tamaño t / 2, porque max (a [2 … 7]) = max (b [1 … 3]) si b es la matriz reducida . Luego procedemos de manera similar para promover la evaluación a matrices cada vez más reducidas. Si realiza el análisis completo, verá que como máximo se deben examinar 2 elementos en cada matriz (con solo un número constante de operaciones para cada uno), y hay matrices O (log t), porque la matriz base tiene t elementos, el siguiente tiene t / 2, etc., hasta que el tamaño se reduce a 1. Por lo tanto, la complejidad de tiempo para una consulta de rango es la O deseada (log t).
Esta estructura de datos se llama árbol de segmentos. La presentación normal solo considera cómo resolver este problema para las matrices de tamaño fijo conocidas de antemano, pero también puede funcionar para las transmisiones de la forma en que lo he presentado aquí.