# 數組左右循環查詢 > 原文： [https://www.geeksforgeeks.org/queries-left-right-circular-shift-array/](https://www.geeksforgeeks.org/queries-left-right-circular-shift-array/) 給定 **N** 個整數的數組。 有三種類型的命令： * **`1 x`**：右循環將數組移動`x`次。 如果數組是`a[0], a[1], ...., a[n – 1]`，則在右移一圈后，該數組將變為`a[n – 1], a[0], a[1], …, a[n – 2]`。 * **`2 y`**：左循環將數組移動`y`次。 如果數組是`a[0], a[1], ...., a[n – 1]`，則在右移一圈后，該數組將變為`a[1], ...., a[n – 2], a[n – 1], a[0]`。 * **`3 l r`**：打印子數組`a[l…r]`（包括`l`和`r`）中所有整數的總和。 給定 **Q** 個查詢，該任務將在每個查詢中執行。 例子： ``` 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. ``` **方法 1 ：（暴力）**實現三個函數：`rotateR(arr, k)`，將數組`arr`右旋轉`k`倍； `rotateL(arr, k)`，將數組`arr`旋轉`k`次，`sum(arr, l, r)`，它將輸出數組`arr`從索引`l`到索引`r`的和。 在輸入值 1、2、3 時，調用相應的函數。 **方法 2 ：（有效方法）**最初，沒有輪換，并且我們有很多查詢詢問范圍或者索引中存在的整數和。 我們可以評估數組中所有元素的前綴和，`prefixsum[i]`將表示直到第`i`個索引的所有整數的和。 現在，如果要查找兩個索引即`l`和`r`之間的元素之和，我們只需計算`prefixsum[r] – prefixsum[1-1]`就可以在恒定時間內對其進行計算。 現在，對于輪換而言，如果我們為每個查詢旋轉數組，那么效率將非常低下。 我們只需要跟蹤凈旋轉量即可。 如果跟蹤的數字為負，則表示左旋已占域，否則右旋已占主導地位。 當我們跟蹤凈旋轉時，我們需要執行`mod n`。 每旋轉`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 ``` * * * * * *