算法题：对数组进行左、右循环移位查询

给定一个数组一种ofñ整数。有三种类型的命令：

• 1 x：向右循环将数组移动x次。如果数组为a [0], a [1], ...., a [n – 1], 则在右移一圈后, 该数组将变为a [n – 1], a [0], a [1] , …。, a [n – 2]。
• 2年：向左循环将数组y次。如果数组是a [0], a [1], ...., a [n – 1], 则在右移一圈后, 该数组将变为a [1], ...., a [n – 2], a [n – 1], a [0]。
• 3升打印子数组a [l…r](包括l和r)中的所有整数之和。

给定问查询, 任务是执行每个查询。

例子：

Input : n = 5, arr[] = { 1, 2, 3, 4, 5 }
        query 1 = { 1, 3 }
        query 2 = { 3, 0, 2 }
        query 3 = { 2, 1 }
        query 4 = { 3, 1, 4 }
Output : 12
         11
Initial array arr[] = { 1, 2, 3, 4, 5 }
After query 1, arr[] = { 3, 4, 5, 1, 2 }.
After query 2, sum from index 0 to index 
               2 is 12, so output 12.
After query 3, arr[] = { 4, 5, 1, 2, 3 }.
After query 4, sum from index 1 to index 
               4 is 11, so output 11.

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

方法1 ：(强力)实现三个函数rotateR(arr, k), 将数组arr右旋转k次； rotateL(arr, k), 将数组arr旋转k次, sum(arr, l, r), 将输出数组arr的和从索引l到索引r。输入值1、2、3时, 调用相应的函数。

方法2 ：(有效方法)

最初, 没有轮换, 并且我们有很多查询要求范围od索引中存在整数的总和。

我们可以评估数组中所有元素的前缀和,

前缀和[i]

将表示直到ith索引的所有整数之和。

现在, 如果要查找两个索引即l和r之间的元素之和, 我们只需计算prefixsum [r]-prefixsum [l-1]就可以在恒定时间内对其进行计算。

现在进行轮换, 如果我们为每个查询轮换数组, 那将是非常低效的。

我们只需要跟踪净旋转。如果跟踪的数字为负, 则表示左旋已占域, 否则右旋已占主导地位。当我们跟踪净旋转时, 我们需要做

模式

。每旋转n次, 数组将返回其原始状态。

我们需要以这样一种方式进行观察：每次旋转数组时, 只有其索引在变化。

如果我们需要回答任何第三种查询, 则有l和r。我们需要找到原始顺序的l和r。我们可以通过将净旋转量添加到索引并取mod n来轻松找到它。

每个命令都可以在O(1)时间执行。

以下是此方法的C ++实现：

// CPP Program to solve queries on Left and Right 
// Circular shift on array
#include <bits/stdc++.h>
using namespace std;
  
// Function to solve query of type 1 x.
void querytype1( int * toRotate, int times, int n)
{
     // Decreasing the absolute rotation
     (*toRotate) = ((*toRotate) - times) % n;
}
  
// Function to solve query of type 2 y.
void querytype2( int * toRotate, int times, int n)
{
     // Increasing the absolute rotation.
     (*toRotate) = ((*toRotate) + times) % n;
}
  
// Function to solve queries of type 3 l r.
void querytype3( int toRotate, int l, int r, int preSum[], int n)
{
     // Finding absolute l and r.
     l = (l + toRotate + n) % n;
     r = (r + toRotate + n) % n;
  
     // if l is before r.
     if (l <= r) 
         cout << (preSum[r + 1] - preSum[l]) << endl;    
  
     // If r is before l.
     else 
         cout << (preSum[n] + preSum[r + 1] - preSum[l])
              << endl;    
}
  
// Wrapper Function solve all queries.
void wrapper( int a[], int n)
{
     int preSum[n + 1];
     preSum[0] = 0;
  
     // Finding Prefix sum
     for ( int i = 1; i <= n; i++)
         preSum[i] = preSum[i - 1] + a[i - 1];
  
     int toRotate = 0;
  
     // Solving each query
     querytype1(&toRotate, 3, n);
     querytype3(toRotate, 0, 2, preSum, n);
     querytype2(&toRotate, 1, n);
     querytype3(toRotate, 1, 4, preSum, n);
}
  
// Driver Program
int main()
{
     int a[] = { 1, 2, 3, 4, 5 };
     int n = sizeof (a) / sizeof (a[0]);
     wrapper(a, n);
     return 0;
}

输出如下：

12
11

---