C++程序找到旋转 K 个索引的数组的范围和查询

给定一个由 N 个元素和 Q 个以下两种类型查询的数组 arr ：

1 K ：对于这种查询类型，需要将数组从当前状态逆时针旋转 K 个索引。
2 L R ：对于此查询，需要计算索引 [L，R] 中出现的数组元素的总和。

示例：

输入： arr = { 1, 2, 3, 4, 5, 6 }，query = { {2，1，3}，{1，3}，{2，0，3}，{1，4}，{2，3，5} }

输出：

说明：

对于第 1 个查询 {2, 1, 3} -> 索引 [1, 3] 中的元素之和 = 2 + 3 + 4 = 9。

对于第 2 个查询 {1, 3} -> 顺时针旋转 3 个位置后的修改后的数组为 {4，5，6，1，2，3}

对于第 3 个查询 {2, 0, 3} -> 索引 [0, 3] 中的元素之和为 4 + 5 + 6 + 1 = 16。

对于第 4 个查询 {1, 4} -> 逆时针旋转 4 个位置后的修改后的数组为 {2，3，4，5，6，1}

对于第 5 个查询 {2，3，5} -> 索引 [3,5] 中的元素之和为 5 + 6 + 1 = 12。

方法：

创建一倍于 arr 大小的 前缀数组 ，并将 arr 的第 i th ** 个索引的元素复制到 **prefix 的第 i th ** 和 **N+i th ** 个索引上，其中i的区间为 **[0，N) 。
预先计算该数组每个索引的前缀和，并存储在 prefix 中。
将指针 start 设置为0，以表示初始数组的起始索引位置。
对于查询类型 1，将 start 移动到以下位置：

（（start + K）％N） th 个位置

对于类型为2的查询，计算

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

如果 start + L ≥ 1 ，则打印以下值：

 prefix[start + R]

以下代码实现了上述方法：

// C++程序来计算区间和
// 逆时针旋转数组k次询问
 
#include <bits/stdc++.h>
using namespace std;
 
// 执行查询的函数
void rotatedSumQuery(
    int arr[], int n,
    vector<vector<int> >& query,
    int Q)
{
    // 构造一个新的大小为2*N的数组
    // 来存储每个索引的前缀和
    int prefix[2 * n];
 
    // 将元素复制到新数组中
    for (int i = 0; i < n; i++) {
        prefix[i] = arr[i];
        prefix[i + n] = arr[i];
    }
 
    // 计算每个索引的前缀和
    for (int i = 1; i < 2 * n; i++)
        prefix[i] += prefix[i - 1];
 
    // 将开始指针设为0
    int start = 0;
 
    for (int q = 0; q < Q; q++) {
 
        // 执行旋转逆时针查询
        if (query[q][0] == 1) {
            int k = query[q][1];
            start = (start + k) % n;
        }
 
        // 查询回答范围和
        else if (query[q][0] == 2) {
 
            int L, R;
            L = query[q][1];
            R = query[q][2];
 
            // 如果指向第一个索引
            if (start + L == 0)
 
                // 显示到start + R的总和
                cout << prefix[start + R] << endl;
 
            else
 
                // 从start + L - 1的总和
                // 减去start + R的总和
                cout << prefix[start + R]
                            - prefix[start + L - 1]
                     << endl;
        }
    }
}
 
// 主函数
int main()
{
 
    int arr[] = { 1, 2, 3, 4, 5, 6 };
 
    // 查询数量
    int Q = 5;
 
    // 存储所有查询
    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;
}

输出: