Programa C++ para encontrar consultas de suma de rango para rotaciones en sentido contrario a las agujas del reloj de índices Array by K

Dada una array arr que consta de N elementos y Q consultas de los siguientes dos tipos: 
 

• 1 K : para este tipo de consulta, la array debe girarse K índices en sentido contrario a las agujas del reloj desde su estado actual .
• 2 LR : Para esta consulta, se debe calcular la suma de los elementos de la array presentes en los índices [L, R] .

Ejemplo:
 

Entrada: arr = { 1, 2, 3, 4, 5, 6 }, consulta = { {2, 1, 3}, {1, 3}, {2, 0, 3}, {1, 4}, { 2, 3, 5} } 
Salida: 
9 
16 
12 
Explicación: 
Para la 1ra consulta {2, 1, 3} -> Suma de los elementos en los índices [1, 3] = 2 + 3 + 4 = 9. 
Para la 2da consulta {1, 3} -> La array modificada después de la rotación en sentido antihorario por 3 lugares es { 4, 5, 6, 1, 2, 3 } 
Para la 3ra consulta {2, 0, 3} -> Suma de los elementos en los índices [0, 3] = 4 + 5 + 6 + 1 = 16. 
Para la cuarta consulta {1, 4} -> La array modificada después de la rotación en sentido antihorario por 4 lugares es { 2, 3, 4, 5, 6, 1 } 
Para la 5ta consulta {2, 3, 5} -> Suma de los elementos en los índices [3, 5] = 5 + 6 + 1 = 12. 
 

Acercarse: 
 

• Cree una array de prefijos que sea el doble del tamaño de la array y copie el elemento en el i ^-ésimo índice de la array a la i ^-ésima y N + i ^-ésima índice del prefijo para todas las i en [0, N) .
• Calcule previamente la suma del prefijo para cada índice de esa array y guárdela en prefix .
• Establezca el inicio del puntero en 0 para indicar el índice inicial de la array inicial.
• Para consultas de tipo 1, cambie el inicio a

((start + K) % N)th position

• Para consulta de tipo 2, calcular 
   

prefix[start + R]
 - prefix[start + L- 1 ]

• si start + L >= 1 , luego imprima el valor de 
   

prefix[start + R]

El siguiente código es la implementación del enfoque anterior:
 

// C++ Program to calculate range sum
// queries for anticlockwise
// rotations of array by K
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to execute the queries
void rotatedSumQuery(
    int arr[], int n,
    vector<vector<int> >& query,
    int Q)
{
    // Construct a new array
    // of size 2*N to store
    // prefix sum of every index
    int prefix[2 * n];
 
    // Copy elements to the new array
    for (int i = 0; i < n; i++) {
        prefix[i] = arr[i];
        prefix[i + n] = arr[i];
    }
 
    // Calculate the prefix sum
    // for every index
    for (int i = 1; i < 2 * n; i++)
        prefix[i] += prefix[i - 1];
 
    // Set start pointer as 0
    int start = 0;
 
    for (int q = 0; q < Q; q++) {
 
        // Query to perform
        // anticlockwise rotation
        if (query[q][0] == 1) {
            int k = query[q][1];
            start = (start + k) % n;
        }
 
        // Query to answer range sum
        else if (query[q][0] == 2) {
 
            int L, R;
            L = query[q][1];
            R = query[q][2];
 
            // If pointing to 1st index
            if (start + L == 0)
 
                // Display the sum upto start + R
                cout << prefix[start + R] << endl;
 
            else
 
                // Subtract sum upto start + L - 1
                // from sum upto start + R
                cout << prefix[start + R]
                            - prefix[start + L - 1]
                     << endl;
        }
    }
}
 
// Driver code
int main()
{
 
    int arr[] = { 1, 2, 3, 4, 5, 6 };
 
    // Number of query
    int Q = 5;
 
    // Store all the queries
    vector<vector<int> > query
        = { { 2, 1, 3 },
            { 1, 3 },
            { 2, 0, 3 },
            { 1, 4 },
            { 2, 3, 5 } };
 
    int n = sizeof(arr) / sizeof(arr[0]);
    rotatedSumQuery(arr, n, query, Q);
 
    return 0;
}

9
16
12

Complejidad de Tiempo : O(N + Q), donde Q es el número de consultas, y como cada consulta costará O (1) tiempo para Q consultas la complejidad del tiempo sería O(Q).

Espacio auxiliar : O (N), ya que estamos usando espacio adicional para el prefijo.
 

Consulte el artículo completo sobre consultas de suma de rango para rotaciones en sentido contrario a las agujas del reloj de índices Array by K para obtener más detalles.