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 inicio + L >= 1 o imprime el valor de
prefix[start + R]
- de lo contrario.
El siguiente código es la implementación del enfoque anterior:
C++
// 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;
}
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] + "\n");
else
// Subtract sum upto start + L - 1
// from sum upto start + R
System.out.print(prefix[start + R] -
prefix[start + L - 1] +
"\n");
}
}
}
// 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
Python3
# Python3 program to calculate range sum # queries for anticlockwise # rotations of the array by K # Function to execute the queries def rotatedSumQuery(arr, n, query, Q): # Construct a new array # of size 2*N to store # prefix sum of every index prefix = [0] * (2 * n) # Copy elements to the new array for i in range(n): prefix[i] = arr[i] prefix[i + n] = arr[i] # Calculate the prefix sum # for every index for i in range(1, 2 * n): prefix[i] += prefix[i - 1]; # Set start pointer as 0 start = 0; for q in range(Q): # Query to perform # anticlockwise rotation if (query[q][0] == 1): k = query[q][1] start = (start + k) % n; # Query to answer range sum elif (query[q][0] == 2): L = query[q][1] R = query[q][2] # If pointing to 1st index if (start + L == 0): # Display the sum upto start + R print(prefix[start + R]) else: # Subtract sum upto start + L - 1 # from sum upto start + R print(prefix[start + R]- prefix[start + L - 1]) # Driver code arr = [ 1, 2, 3, 4, 5, 6 ]; # Number of query Q = 5 # Store all the queries query= [ [ 2, 1, 3 ], [ 1, 3 ], [ 2, 0, 3 ], [ 1, 4 ], [ 2, 3, 5 ] ] n = len(arr); rotatedSumQuery(arr, n, query, Q); # This code is contributed by ankitkumar34
C#
// C# program to calculate range sum
// queries for anticlockwise
// rotations of array by K
using System;
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
Console.Write(prefix[start + R] + "\n");
else
// Subtract sum upto start + L - 1
// from sum upto start + R
Console.Write(prefix[start + R] -
prefix[start + L - 1] +
"\n");
}
}
}
// Driver code
public static void Main()
{
int[] arr = new int[] { 1, 2, 3, 4, 5, 6 };
// Number of query
int Q = 5;
// Store all the queries
int[,] query = new int[,] { { 2, 1, 3 },
{ 1, 3, 0 },
{ 2, 0, 3 },
{ 1, 4, 0 },
{ 2, 3, 5 } };
int n = arr.Length;
rotatedSumQuery(arr, n, query, Q);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to calculate range sum
// queries for anticlockwise
// rotations of array by K
// Function to execute the queries
function rotatedSumQuery(arr, n,
query, Q)
{
// Construct a new array
// of size 2*N to store
// prefix sum of every index
let prefix = [];
// Copy elements to the new array
for(let i = 0; i < n; i++)
{
prefix[i] = arr[i];
prefix[i + n] = arr[i];
}
// Calculate the prefix sum
// for every index
for(let i = 1; i < 2 * n; i++)
prefix[i] += prefix[i - 1];
// Set start pointer as 0
let start = 0;
for(let q = 0; q < Q; q++)
{
// Query to perform
// anticlockwise rotation
if (query[q][0] == 1)
{
let k = query[q][1];
start = (start + k) % n;
}
// Query to answer range sum
else if (query[q][0] == 2)
{
let 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
document.write(prefix[start + R] + "<br/>");
else
// Subtract sum upto start + L - 1
// from sum upto start + R
document.write(prefix[start + R] -
prefix[start + L - 1] +
"<br/>");
}
}
}
// Driver code
let arr = [ 1, 2, 3, 4, 5, 6 ];
// Number of query
let Q = 5;
// Store all the queries
let query = [[ 2, 1, 3 ],
[ 1, 3 ],
[ 2, 0, 3 ],
[ 1, 4 ],
[ 2, 3, 5 ]];
let n = arr.length;
rotatedSumQuery(arr, n, query, Q);
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
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.