Algoritmo de Mo extendido con complejidad de tiempo ≈ O(1)

Dada una array de n elementos y q consultas de rango (suma de rango en este artículo) sin actualizaciones, la tarea es responder estas consultas con una complejidad de tiempo y espacio eficiente. La complejidad temporal de una consulta de rango después de aplicar la descomposición de la raíz cuadrada resulta ser O(√n) . Este factor de raíz cuadrada se puede reducir a un factor lineal constante aplicando la descomposición de raíz cuadrada en el bloque de la array que se descompuso anteriormente.
Prerrequisito: Algoritmo de Mo | Array de prefijos

Enfoque:
A medida que aplicamos la descomposición de la raíz cuadrada a la array dada, la consulta de una suma de rango se produce en el tiempo O(√n) .
Aquí, calcule la suma de los bloques que se encuentran entre los bloques considerados (bloques de esquina), lo que requiere O(√n) iteraciones.
Array inicial:

array inicial

Descomposición de la array en bloques:

Descomposición en el nivel 1

Y el tiempo de cálculo para la suma en el bloque inicial y el bloque final toma O(√n) iteraciones.

Lo que nos dejará por complejidad de tiempo de consulta de:

= O(√n) + O(√n) + O(√n)
= 3 * O(√n)   
~O(√n)

Aquí, podemos reducir inteligentemente la complejidad del tiempo de ejecución de nuestro algoritmo de consulta calculando la suma de prefijos por bloques y utilizándola para calcular la suma acumulada en los bloques que se encuentran entre los bloques bajo consideración. Considere el siguiente código:

interblock_sum[x1][x2] = prefixData[x2 - 1] - prefixData[x1];

El tiempo necesario para el cálculo de la tabla anterior es:

= O(√n) * O(√n)  
~O(n)

NOTA: No hemos considerado la suma de los bloques x1 y x2, ya que podrían contener datos parciales.
Array de prefijos:

array de prefijos

Supongamos que queremos consultar la suma del rango de 4 a 11, consideramos la suma entre el bloque 0 y el bloque 2 (excluyendo los datos contenidos en el bloque 0 y el bloque 1), que se puede calcular usando la suma en los bloques de color verde representada en la imagen de arriba.
Suma entre el bloque 0 y el bloque 2 = 42 – 12 = 30
Para el cálculo del resto de la suma presente en los bloques amarillos, considere la array de prefijos en el nivel de descomposición-2 y repita el proceso nuevamente.
Aquí, observe que hemos reducido significativamente nuestra complejidad de tiempo por consulta, aunque nuestro tiempo de ejecución sigue siendo similar a nuestro último enfoque:

Nuestra nueva complejidad temporal se puede calcular como:

= O(√n) + O(1) + O(√n)
= 2 * O(√n)   
~O(√n)

Descomposición de raíz cuadrada en el nivel 2:

Descomposición en el nivel 2

Además, aplicamos la descomposición de raíz cuadrada nuevamente en cada bloque descompuesto retenido de la descomposición anterior. Ahora, en este nivel, tenemos aproximadamente √√n subbloques en cada bloque que se descompusieron en el último nivel. Por lo tanto, necesitamos ejecutar una consulta de rango en estos bloques solo dos veces, una vez para el bloque inicial y una vez para el bloque final.

Precálculo Tiempo necesario para la descomposición del nivel 2:
Nº de bloques en el nivel 1 ~ √n
Nº de bloques en el nivel 2 ~ √√n

Tiempo de ejecución de descomposición de nivel 2 de un bloque descompuesto de nivel 1:

= O(√n)

Tiempo de ejecución general de la descomposición de nivel 2 en todos los bloques:

= O(√n) * O(√n)
~O(n)

Ahora, podemos consultar nuestros bloques descompuestos de nivel 2 en tiempo O(√√n) .
Entonces, hemos reducido nuestra complejidad de tiempo general de O(√n) a O(√√n)

Complejidad del tiempo necesario para consultar bloques perimetrales:

= O(√√n) + O(1) + O(√√n)
= 2 * O(√√n)
~O(√√n)

La complejidad del tiempo total se puede calcular como:

= O(√√n)+O(1)+O(√√n)
= 2 * O(√√n)   
~O(√√n)

Descomposición de raíz cuadrada en el nivel 3:

Descomposición en el nivel 3

Usando este método podemos descomponer nuestra array una y otra vez recursivamente d veces para reducir nuestra complejidad de tiempo a un factor de linealidad constante .

O(d * n^{1/(2^d)) ~ O(k), as d increases this factor converges to a constant linear term}

El código que se presenta a continuación es una representación de la descomposición de raíz cuadrada triple donde d = 3:

O(q * d * n^{1/(2 ^ 3)}) ~ O(q * k) ~ O(q)

[donde q representa el número de consultas de rango]

C++

// CPP code for offline queries in
// approx constant time.
#include<bits/stdc++.h>
using namespace std;
 
int n1;
 
// Structure to store decomposed data
typedef struct
{
    vector<int> data;
    vector<vector<int>> rdata;
    int blocks;
    int blk_sz;
}sqrtD;
 
vector<vector<sqrtD>> Sq3;
vector<sqrtD> Sq2;
sqrtD Sq1;
 
// Square root Decomposition of
// a given array
sqrtD decompose(vector<int> arr)
{
    sqrtD sq;
    int n = arr.size();
    int blk_idx = -1;
    sq.blk_sz = sqrt(n);
    sq.data.resize((n/sq.blk_sz) + 1, 0);
     
    // Calculation of data in blocks
    for (int i = 0; i < n; i++)
    {
        if (i % sq.blk_sz == 0)
        {
            blk_idx++;
        }
        sq.data[blk_idx] += arr[i];
    }
     
    int blocks = blk_idx + 1;
    sq.blocks = blocks;
     
    // Calculation of prefix data
    int prefixData[blocks];
    prefixData[0] = sq.data[0];
    for(int i = 1; i < blocks; i++)
    {
        prefixData[i] =
          prefixData[i - 1] + sq.data[i];
    }
     
    sq.rdata.resize(blocks + 1,
             vector<int>(blocks + 1));
     
    // Calculation of data between blocks
    for(int i = 0 ;i < blocks; i++)
    {
        for(int j = i + 1; j < blocks; j++)
        {
            sq.rdata[i][j] = sq.rdata[j][i] =
            prefixData[j - 1] - prefixData[i];
        }
    }
     
    return sq;
}
 
// Square root Decomposition at level3
vector<vector<sqrtD>> tripleDecompose(sqrtD sq1,
                      sqrtD sq2,vector<int> &arr)
{
    vector<vector<sqrtD>> sq(sq1.blocks,
                      vector<sqrtD>(sq1.blocks));
     
    int blk_idx1 = -1;
     
    for(int i = 0; i < sq1.blocks; i++)
    {
        int blk_ldx1 = blk_idx1 + 1;
        blk_idx1 = (i + 1) * sq1.blk_sz - 1;
        blk_idx1 = min(blk_idx1,n1 - 1);
 
        int blk_idx2 = blk_ldx1 - 1;
         
        for(int j = 0; j < sq2.blocks; ++j)
        {
            int blk_ldx2 = blk_idx2 + 1;
            blk_idx2 = blk_ldx1 + (j + 1) *
                       sq2.blk_sz - 1;
            blk_idx2 = min(blk_idx2, blk_idx1);
         
            vector<int> ::iterator it1 =
                        arr.begin() + blk_ldx2;
            vector<int> ::iterator it2 =
                        arr.begin() + blk_idx2 + 1;
            vector<int> vec(it1, it2);
            sq[i][j] = decompose(vec);    
        }
    }
    return sq;        
}
 
// Square root Decomposition at level2
vector<sqrtD> doubleDecompose(sqrtD sq1,
                              vector<int> &arr)
{
    vector<sqrtD> sq(sq1.blocks);
    int blk_idx = -1;
    for(int i = 0; i < sq1.blocks; i++)
    {
        int blk_ldx = blk_idx + 1;
        blk_idx = (i + 1) * sq1.blk_sz - 1;
        blk_idx = min(blk_idx, n1 - 1);
        vector<int> ::iterator it1 =
                    arr.begin() + blk_ldx;
        vector<int> ::iterator it2 =
                    arr.begin() + blk_idx + 1;
        vector<int> vec(it1, it2);
        sq[i] = decompose(vec);
    }
     
    return sq;    
}
 
// Square root Decomposition at level1
void singleDecompose(vector<int> &arr)
{
    sqrtD sq1 = decompose(arr);
    vector<sqrtD> sq2(sq1.blocks);
    sq2 = doubleDecompose(sq1, arr);
     
    vector<vector<sqrtD>> sq3(sq1.blocks,
           vector<sqrtD>(sq2[0].blocks));
            
    sq3 = tripleDecompose(sq1, sq2[0],arr);
         
    // ASSIGNMENT TO GLOBAL VARIABLES
    Sq1 = sq1;
    Sq2.resize(sq1.blocks);
    Sq2 = sq2;
    Sq3.resize(sq1.blocks,
        vector<sqrtD>(sq2[0].blocks));
    Sq3 = sq3;
}
 
// Function for query at level 3
int queryLevel3(int start,int end, int main_blk,
                int sub_main_blk, vector<int> &arr)
{
    int blk_sz= Sq3[0][0].blk_sz;
 
    // Element Indexing at level2 decomposition
    int nstart = start - main_blk *
        Sq1.blk_sz - sub_main_blk * Sq2[0].blk_sz;
    int nend = end - main_blk *
        Sq1.blk_sz - sub_main_blk * Sq2[0].blk_sz;
 
    // Block indexing at level3 decomposition
    int st_blk = nstart / blk_sz;
    int en_blk = nend / blk_sz;
     
    int answer =
        Sq3[main_blk][sub_main_blk].rdata[st_blk][en_blk];
     
    // If start and end point don't lie in same block
    if(st_blk != en_blk)
    {
        int left = 0, en_idx = main_blk * Sq1.blk_sz +
                      sub_main_blk * Sq2[0].blk_sz +
                      (st_blk + 1) * blk_sz -1;
     
        for(int i = start; i <= en_idx; i++)
        {
            left += arr[i];
        }
         
        int right = 0, st_idx = main_blk * Sq1.blk_sz +
                       sub_main_blk * Sq2[0].blk_sz +
                       (en_blk) * blk_sz;
         
        for(int i = st_idx; i <= end; i++)
        {
            right += arr[i];
        }
         
        answer += left;
        answer += right;
    }
    else
    {
        for(int i = start; i <= end; i++)
        {
            answer += arr[i];
    }
}
return answer;    
}
 
// Function for splitting query to level two
int queryLevel2(int start, int end, int main_blk,
                vector<int> &arr)
{
    int blk_sz = Sq2[0].blk_sz;
 
    // Element Indexing at level1 decomposition
    int nstart = start - (main_blk * Sq1.blk_sz);
    int nend = end - (main_blk * Sq1.blk_sz);
 
    // Block indexing at level2 decomposition
    int st_blk = nstart / blk_sz;
    int en_blk = nend / blk_sz;
     
    // Interblock data level2 decomposition
    int answer = Sq2[main_blk].rdata[st_blk][en_blk];
     
    if(st_blk == en_blk)
    {
        answer += queryLevel3(start, end, main_blk,
                              st_blk, arr);
    }
    else
    {
        answer += queryLevel3(start, (main_blk *
                  Sq1.blk_sz) + ((st_blk + 1) *
                  blk_sz) - 1, main_blk, st_blk, arr);
         
        answer += queryLevel3((main_blk * Sq1.blk_sz) +
                  (en_blk * blk_sz), end, main_blk, en_blk, arr);
    }
    return answer;    
}
 
// Function to return answer according to query
int Query(int start,int end,vector<int>& arr)
{
    int blk_sz = Sq1.blk_sz;
    int st_blk = start / blk_sz;
    int en_blk = end / blk_sz;
     
    // Interblock data level1 decomposition    
    int answer = Sq1.rdata[st_blk][en_blk];
 
    if(st_blk == en_blk)
    {
        answer += queryLevel2(start, end, st_blk, arr);
    }
    else
    {
        answer += queryLevel2(start, (st_blk + 1) *
                  blk_sz - 1, st_blk, arr);
        answer += queryLevel2(en_blk * blk_sz, end,
                              en_blk, arr);
    }
     
    // returning final answer
    return answer;
}
 
// Driver code
int main()
{    
    n1 = 16;
     
    vector<int> arr = {7, 2, 3, 0, 5, 10, 3, 12,
                       18, 1, 2, 3, 4, 5, 6, 7};
 
    singleDecompose(arr);
     
    int q = 5;
    pair<int, int> query[q] = {{6, 10}, {7, 12},
                  {4, 13}, {4, 11}, {12, 16}};
     
    for(int i = 0; i < q; i++)
    {
        int a = query[i].first, b = query[i].second;
        printf("%d\n", Query(a - 1, b - 1, arr));
    }
     
    return 0;
}

Producción:

Complejidad de tiempo: O(q * d * n ^{1/(2^3)} ) ≈ O(q * k) ≈ O(q)
Espacio auxiliar: O(k * n) ≈ O(n)
Nota: Este artículo es para solo explique el método de descomposición de la raíz cuadrada para una mayor descomposición.

Publicación traducida automáticamente

Artículo escrito por Harshit Saini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Deja una respuesta Cancelar la respuesta