范围查询中的数组范围查询 · GeeksForGeeks 中文系列教程

# 范围查询中的数组范围查询 > 原文： [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; } ```