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 entonces imprime el valor de
prefix[start + R]
El siguiente código es la implementación del enfoque anterior:
Java
// Java program to calculate range sum // queries for anticlockwise // rotations of array by K class GFG{ // Function to execute the queries static void rotatedSumQuery(int arr[], int n, int [][]query, int Q) { // Construct a new array // of size 2*N to store // prefix sum of every index int []prefix = new int[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 System.out.print(prefix[start + R] + " "); else // Subtract sum upto start + L - 1 // from sum upto start + R System.out.print(prefix[start + R] - prefix[start + L - 1] + " "); } } } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 5, 6 }; // Number of query int Q = 5; // Store all the queries int [][]query = { { 2, 1, 3 }, { 1, 3 }, { 2, 0, 3 }, { 1, 4 }, { 2, 3, 5 } }; int n = arr.length; rotatedSumQuery(arr, n, query, Q); } } // This code is contributed by Rohit_ranjan
9 16 12
Complejidad de tiempo : O(Q), donde Q es el número de consultas, y como cada consulta costará O (1) el 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA