Descomposición de la raíz

Tenemos un problema sobre cómo calcular rápidamente las sumas en el intervalo l...r en una matriz estática a en asintóticas menores que O(n).

Dividamos el arreglo a en k bloques del mismo tamaño y primero calculemos la suma de elementos para cada uno de ellos.

Ahora, al responder la solicitud, podemos revisar los elementos de la matriz a y agregarlos al resultado, también si uno de los bloques se encuentra dentro del segmento, entonces podemos agregar su suma al resultado y omitir el elementos de este bloque.

El número máximo de operaciones por consulta con este algoritmo es n / k + k, por lo que el k óptimo es igual a la raíz cuadrada de n.

 

Tenemos un problema sobre cómo calcular rápidamente las sumas en el segmento l...r en la matriz a, en la que los elementos pueden cambiar uno a la vez, en asintóticas menores que O(n).

Esta tarea se resuelve de manera similar a la anterior, pero al momento de solicitar un cambio, es necesario cambiar la cantidad en el bloque correspondiente.

Se da una tarea en la que es necesario realizar operaciones masivas sobre un segmento y reconocer un elemento por índice.

Las operaciones en masa se llevan a cabo como un cálculo de suma en un segmento.

Para cada bloque, almacenamos el cambio en ese bloque, y cuando solicitamos un elemento de ese bloque, tomamos en cuenta esa información.