# 范圍查詢中的數組范圍查詢 > 原文： [https://www.geeksforgeeks.org/array-range-queries-range-queries/](https://www.geeksforgeeks.org/array-range-queries-range-queries/) 給定大小為`n`的數組和大小為`m`的給定命令集。 命令從 1 到`m`枚舉。 這些命令可以是以下兩種類型的命令： 1. **類型 1 `[lr(1 <= l <= r <= n)]`**：將數組的所有元素加一，其索引屬于范圍`[l, r]`。 在這些查詢中，索引包含在范圍內。 2. **類型 2 `[lr(1 <= l <= r <= m)]`**：執行所有索引在`[l, r]`范圍內的命令。 在這些查詢中，索引包含在范圍內。 保證`r`嚴格小于當前命令的枚舉/數量。 注意：根據問題說明，數組索引從 1 開始。 **示例 1** ``` Input : 5 5 1 1 2 1 4 5 2 1 2 2 1 3 2 3 4 Output : 7 7 0 7 7 ``` **示例 1 的說明**： 我們的數組最初是大小為 5 的數組，其每個元素都已初始化為 0。 因此，現在的問題是對于上述示例，我們有 5 個查詢。 1. 查詢 1 的類型為 1：如上所述，在給定索引為 1 和 2 的情況下，我們將簡單地將數組索引增加 1，因此在執行第一個數組后，我們的數組將變為`1 1 0 0 0`。 2. 查詢 2 的類型為 1：如上所述，在給定索引為 4 和 5 的情況下，我們將簡單地將數組索引增加 1 ，因此在執行第一個數組后，我們的數組將變為`1 1 0 1 1`。 3. 查詢 3 是類型 2：如此類查詢的定義中所述，我們將執行范圍內所述的查詢，即，我們將操作查詢而不是數組。 給定的范圍是 1 和 2，所以我們將再次執行查詢 1 和 2，即，我們將對類型 2 查詢使用重復方法，因此我們將再次執行查詢 1，數組將是`2 2 0 11`。現在，當執行 查詢，我們將執行查詢 2，結果數組將是`2 2 0 2 2`。 4. 查詢 4 是類型 2：如此類查詢的定義中所述，我們將執行范圍內所述的查詢，即，我們將操作查詢而不是數組。 給定的范圍是 1 和 3，因此我們將再次執行查詢 1、2 和 3，即使用重復方法將執行查詢 1、2 和 3。 再次執行查詢 1 后，數組將為`3 3 0 2 2`。 再次執行查詢 2 后，數組將為`3 3 0 3 3`。 現在由于查詢 3 包含范圍，我們將執行查詢 3，結果數組將為`4 4 0 4 4`。 如上所述。 5. 查詢 5 是類型 2：最后一個查詢將執行上面已說明的第三和第四查詢。 執行完第三個查詢后，我們的數組將為`5 5 0 5 5`。 在執行第四個查詢后，即執行查詢 1、2 和 3，我們的數組將為 7 7 0 7 7 以上是所需結果 **示例 2** ``` Input : 1 2 1 1 1 1 1 1 Output : 2 ``` 示例 2 的說明： 我們的數組初始大小為 1，其每個元素都已初始化為 0。 因此，現在的問題表明，對于上述示例，我們有 2 個查詢。 1. 查詢 1 的類型為 1：如上所述，在給定索引為 1 和 1 的情況下，我們將簡單地將數組索引加 1，因此在執行第一個數組后，我們的數組將變為 1。 2. 查詢 2 的類型為 1：如上所述，在給定索引為 1 和 1 的情況下，我們將簡單地將數組索引增加 1，因此在執行第一個數組后，我們的數組將變為 2。 這給了我們想要的結果 **方法 1**： 此方法是暴力方法，其中對 2 類查詢應用簡單遞歸，對 1 類查詢執行簡單的數組索引增量。 ## C++ ```cpp // CPP program to perform range queries over range // queries. #include <bits/stdc++.h> using namespace std; // Function to execute type 1 query void type1(int arr[], int start, int limit) { ????// incrementing the array by 1 for type? ????// 1 queries ????for (int i = start; i <= limit; i++)??????? ????????arr[i]++; } // Function to execute type 2 query void type2(int arr[], int query[][3], int start, int limit) { ????for (int i = start; i <= limit; i++) { ????????// If the query is of type 1 function ????????// call to type 1 query ????????if (query[i][0] == 1)? ????????????type1(arr, query[i][1], query[i][2]); ????????// If the query is of type 2 recursive call? ????????// to type 2 query ????????else if (query[i][0] == 2)? ????????????type2(arr, query, query[i][1], query[i][2]);???????? ????} } // Driver code int main() { ????// Input size of array amd number of queries ????int n = 5, m = 5; ????int arr[n + 1]; ????for (int i = 1; i <= n; i++)? ????????arr[i] = 0; ????// Build query matrix ????int temp[15] = { 1, 1, 2, 1, 4, 5, 2,? ????????????????????1, 2, 2, 1, 3, 2, 3, 4 }; ????int query[5][3]; ????int j = 0; ????for (int i = 1; i <= m; i++) { ????????query[i][0] = temp[j++]; ????????query[i][1] = temp[j++]; ????????query[i][2] = temp[j++]; ????} ????// Perform queries? ????for (int i = 1; i <= m; i++)? ????????if (query[i][0] == 1)? ????????????type1(arr, query[i][1], query[i][2]); ????????else if (query[i][0] == 2)? ????????????type2(arr, query, query[i][1], query[i][2]);???????? ????// printing the result ????for (int i = 1; i <= n; i++)? ????????cout << arr[i] << " "; ????return 0; } ```