Python3 Program to Find Range sum queries for anticlockwise rotations of Array by K indices
Given an array arr consisting of N elements and Q queries of the following two types:
- 1 K: For this type of query, the array needs to be rotated by K indices anticlockwise from its current state.
- 2 L R: For this query, the sum of the array elements present in the indices [L, R] needs to be calculated.
Example:
Input: arr = { 1, 2, 3, 4, 5, 6 }, query = { {2, 1, 3}, {1, 3}, {2, 0, 3}, {1, 4}, {2, 3, 5} }
Output:
9
16
12
Explanation:
For the 1st query {2, 1, 3} -> Sum of the elements in the indices [1, 3] = 2 + 3 + 4 = 9.
For the 2nd query {1, 3} -> Modified array after anti-clockwise rotation by 3 places is { 4, 5, 6, 1, 2, 3 }
For the 3rd query {2, 0, 3} -> Sum of the elements in the indices [0, 3] = 4 + 5 + 6 + 1 = 16.
For the 4th query {1, 4} -> Modified array after anti-clockwise rotation by 4 places is { 2, 3, 4, 5, 6, 1 }
For the 5th query {2, 3, 5} -> Sum of the elements in the indices [3, 5] = 5 + 6 + 1 = 12.
Approach:
- Create a prefix array which is double the size of the arr and copy the element at the ith index of arr to ith and N + ith index of prefix for all i in [0, N).
- Precompute the prefix sum for every index of that array and store in prefix.
- Set the pointer start at 0 to denote the starting index of the initial array.
- For query of type 1, shift start to
((start + K) % N)th position
- For query of type 2, calculate
prefix[start + R] - prefix[start + L- 1 ]
- if start + L >= 1 ,then print the value of
prefix[start + R]
Below code is the implementation of the above approach:
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 |
9 16 12
Time Complexity: O(Q), where Q is the number of queries, and as each query will cost O (1) time for Q queries time complexity would be O(Q).
Auxiliary Space: O(N), as we are using extra space for prefix.
Please refer complete article on Range sum queries for anticlockwise rotations of Array by K indices for more details!