给定一个大小为n的数组和一组大小为m的命令。这些命令从1到m枚举。这些命令可以是以下两种类型的命令：
null
- 类型1[LR（1<=l<=r<=n）]： 将数组的所有元素增加一，其索引属于[l，r]范围。在这些查询中，索引包含在范围内。
- 第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。
- 查询2属于类型1：如上所述，我们只需将数组索引增加1 给定的索引是4和5，因此在执行第一个后，我们的数组将变为1。
- 查询3属于类型2：如该类型查询的定义所述，我们将执行范围中所述的查询，即我们将操作查询而不是数组。给定的范围是1和2，因此我们将再次执行查询1和查询2，即我们将对类型2查询使用重复方法，因此我们将再次执行查询1，我们的数组将为2 0 1 1。现在，当我们执行查询时，我们将执行查询2，结果数组将是2 0 2。
- 查询4属于类型2：如该类型查询的定义所述，我们将执行范围中所述的查询，即我们将操作查询而不是数组。给定的范围是1和3，因此我们将再次执行查询1、2和3，即使用重复方法执行查询1、2和3。再次执行查询1后，数组将为3 0 2。再次执行查询2后，数组将为3 0 3。现在由于查询3包含在范围内，我们将执行查询3，结果数组将为4 0 4。如上所述。
- 查询5属于类型2：最后一个查询将执行上文解释的第三个和第四个查询。执行第三次查询后，我们的数组将为5 05。在执行第四个查询，即执行查询1、2和3之后，我们的数组将是7 7 0 7，以上是所需的结果
例2
Input : 1 2
1 1 1
1 1 1
Output : 2
示例2的说明： 我们的数组最初的大小为1，其每个元素都已初始化为0。 现在问题是，对于上面的例子，我们有两个查询。
- 查询1属于类型1：如上所述，我们只需将数组索引增加1，给定的索引是1和1，因此在执行第一个查询后，我们的数组变为1。
- 查询2属于类型1：如上所述，我们只需将数组索引增加1，给定的索引是1和1，因此在执行第一个查询之后，我们的数组变为2。这给了我们期望的结果
方法1： 这种方法是蛮力方法，通过简单的递归将其应用于类型2查询，对于类型1查询，执行数组索引中的简单增量。
C++
// 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; } |
JAVA
// Java program to perform range queries // over range queries. import java.util.*; class GFG { // Function to execute type 1 query static 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 static void type2( int [] arr, int [][] query, 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 public static void main(String[] args) { // Input size of array amd number of queries int n = 5 , m = 5 ; int [] arr = new int [n + 1 ]; // Build query matrix int [] temp = { 1 , 1 , 2 , 1 , 4 , 5 , 2 , 1 , 2 , 2 , 1 , 3 , 2 , 3 , 4 }; int [][] query = new int [ 6 ][ 4 ]; 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++) System.out.print(arr[i] + " " ); System.out.println(); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 program to perform range # queries over range queries. # Function to execute type 1 query def type1(arr, start, limit): # incrementing the array by 1 # for type 1 queries for i in range (start, limit + 1 ): arr[i] + = 1 # Function to execute type 2 query def type2(arr, query, start, limit): for i in range (start, limit + 1 ): # 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 elif (query[i][ 0 ] = = 2 ): type2(arr, query, query[i][ 1 ], query[i][ 2 ]) # Driver code # Input size of array amd # number of queries n = 5 m = 5 arr = [ 0 for i in range (n + 1 )] # Build query matrix temp = [ 1 , 1 , 2 , 1 , 4 , 5 , 2 , 1 , 2 , 2 , 1 , 3 , 2 , 3 , 4 ] query = [[ 0 for i in range ( 3 )] for j in range ( 6 )] j = 0 for i in range ( 1 , m + 1 ): query[i][ 0 ] = temp[j] j + = 1 query[i][ 1 ] = temp[j] j + = 1 query[i][ 2 ] = temp[j] j + = 1 # Perform queries for i in range ( 1 , m + 1 ): if (query[i][ 0 ] = = 1 ): type1(arr, query[i][ 1 ], query[i][ 2 ]) elif (query[i][ 0 ] = = 2 ): type2(arr, query, query[i][ 1 ], query[i][ 2 ]) # printing the result for i in range ( 1 , n + 1 ): print (arr[i], end = " " ) # This code is contributed # by mohit kumar |
C#
// C# program to perform range queries // over range queries. using System; class GFG { // Function to execute type 1 query static 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 static void type2( int [] arr, int [,] query, 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 public static void Main() { // Input size of array amd number of queries int n = 5, m = 5; int [] arr = new int [n + 1]; // Build query matrix int [] temp = { 1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 }; int [,] query = new int [6,4]; 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++) Console.Write(arr[i] + " " ); Console.WriteLine(); } } // This code is contributed by AbhiThakur |
Javascript
<script> // Javascript program to perform range queries // over range queries. // Function to execute type 1 query function type1(arr,start,limit) { // incrementing the array by 1 for type // 1 queries for (let i = start; i <= limit; i++) arr[i]++; } // Function to execute type 2 query function type2(arr,query,start,limit) { for (let 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 // Input size of array amd number of queries let n = 5, m = 5; let arr = new Array(n + 1); for (let i=0;i<arr.length;i++) { arr[i]=0; } // Build query matrix let temp = [ 1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 ]; let query = new Array(6); for (let i=0;i<6;i++) { query[i]= new Array(4); for (let j=0;j<4;j++) { query[i][j]=0; } } let j = 0; for (let i = 1; i <= m; i++) { query[i][0] = temp[j++]; query[i][1] = temp[j++]; query[i][2] = temp[j++]; } // Perform queries for (let 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 (let i = 1; i <= n; i++) document.write(arr[i] + " " ); document.write( "<br>" ); // This code is contributed by patel2127 </script> |
输出：
7 7 0 7 7
上述代码的时间复杂度为 O（2米）
方法2： 在这种方法中，我们使用一个额外的数组来创建记录数组，以查找特定查询正在执行的时间，在创建记录数组之后，我们只需执行类型1的查询，记录数组的包含内容只需添加到主数组中，这将为我们提供结果数组。
C++
// CPP program to perform range queries over range // queries. #include <bits/stdc++.h> using namespace std; // Function to create the record array void record_sum( int record[], int l, int r, int n, int adder) { for ( int i = l; i <= r; i++) record[i] += adder; } // Driver Code int main() { int n = 5, m = 5; int arr[n]; // Build query matrix memset (arr, 0, sizeof arr); int query[5][3] = { { 1, 1, 2 }, { 1, 4, 5 }, { 2, 1, 2 }, { 2, 1, 3 }, { 2, 3, 4 } }; int record[m]; memset (record, 0, sizeof record); for ( int i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_sum if (query[i][0] == 2) record_sum(record, query[i][1] - 1, query[i][2] - 1, m, record[i] + 1); // If query is of type 1 then simply add // 1 to the record array else record_sum(record, i, i, m, 1); } // for type 1 queries adding the contains of // record array to the main array record array for ( int i = 0; i < m; i++) { if (query[i][0] == 1) record_sum(arr, query[i][1] - 1, query[i][2] - 1, n, record[i]); } // printing the array for ( int i = 0; i < n; i++) cout << arr[i] << ' ' ; return 0; } |
JAVA
// Java program to perform range queries // over range queries. import java.util.Arrays; class GFG { // Function to create the record array static void record_sum( int record[], int l, int r, int n, int adder) { for ( int i = l; i <= r; i++) { record[i] += adder; } } // Driver Code public static void main(String[] args) { int n = 5 , m = 5 ; int arr[] = new int [n]; // Build query matrix Arrays.fill(arr, 0 ); int query[][] = {{ 1 , 1 , 2 }, { 1 , 4 , 5 }, { 2 , 1 , 2 }, { 2 , 1 , 3 }, { 2 , 3 , 4 }}; int record[] = new int [m]; Arrays.fill(record, 0 ); for ( int i = m - 1 ; i >= 0 ; i--) { // If query is of type 2 then function // call to record_sum if (query[i][ 0 ] == 2 ) { record_sum(record, query[i][ 1 ] - 1 , query[i][ 2 ] - 1 , m, record[i] + 1 ); } // If query is of type 1 then // simply add 1 to the record array else { record_sum(record, i, i, m, 1 ); } } // for type 1 queries adding the contains of // record array to the main array record array for ( int i = 0 ; i < m; i++) { if (query[i][ 0 ] == 1 ) { record_sum(arr, query[i][ 1 ] - 1 , query[i][ 2 ] - 1 , n, record[i]); } } // printing the array for ( int i = 0 ; i < n; i++) { System.out.print(arr[i] + " " ); } } } // This code is contributed // by Princi Singh |
Python3
# Python3 program to perform range queries over range # queries. # Function to create the record array def record_sum(record, l, r, n, adder): for i in range (l, r + 1 ): record[i] + = adder # Driver Code n = 5 m = 5 arr = [ 0 ] * n # Build query matrix query = [[ 1 , 1 , 2 ],[ 1 , 4 , 5 ],[ 2 , 1 , 2 ], [ 2 , 1 , 3 ],[ 2 , 3 , 4 ]] record = [ 0 ] * m for i in range (m - 1 , - 1 , - 1 ): # If query is of type 2 then function # call to record_sum if (query[i][ 0 ] = = 2 ): record_sum(record, query[i][ 1 ] - 1 , query[i][ 2 ] - 1 , m, record[i] + 1 ) # If query is of type 1 then simply add # 1 to the record array else : record_sum(record, i, i, m, 1 ) # for type 1 queries adding the contains of # record array to the main array record array for i in range (m): if (query[i][ 0 ] = = 1 ): record_sum(arr, query[i][ 1 ] - 1 , query[i][ 2 ] - 1 , n, record[i]) # printing the array for i in range (n): print (arr[i], end = ' ' ) # This code is contributed by shubhamsingh10 |
C#
// C# program to perform range queries // over range queries. using System; class GFG { // Function to create the record array static void record_sum( int []record, int l, int r, int n, int adder) { for ( int i = l; i <= r; i++) { record[i] += adder; } } // Driver Code public static void Main(String[] args) { int n = 5, m = 5; int []arr = new int [n]; // Build query matrix int [,]query = {{1, 1, 2}, {1, 4, 5}, {2, 1, 2}, {2, 1, 3}, {2, 3, 4}}; int []record = new int [m]; for ( int i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_sum if (query[i,0] == 2) { record_sum(record, query[i,1] - 1, query[i,2] - 1, m, record[i] + 1); } // If query is of type 1 then // simply add 1 to the record array else { record_sum(record, i, i, m, 1); } } // for type 1 queries adding the contains of // record array to the main array record array for ( int i = 0; i < m; i++) { if (query[i, 0] == 1) { record_sum(arr, query[i, 1] - 1, query[i, 2] - 1, n, record[i]); } } // printing the array for ( int i = 0; i < n; i++) { Console.Write(arr[i] + " " ); } } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to perform range queries // over range queries. // Function to create the record array function record_sum(record,l,r,n,adder) { for (let i = l; i <= r; i++) { record[i] += adder; } } // Driver Code let n = 5, m = 5; let arr = new Array(n); // Build query matrix for (let i=0;i<arr.length;i++) { arr[i]=0; } let query = [[1, 1, 2], [1, 4, 5], [2, 1, 2], [2, 1, 3], [2, 3, 4]]; let record = new Array(m); for (let i=0;i<record.length;i++) { record[i]=0; } for (let i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_sum if (query[i][0] == 2) { record_sum(record, query[i][1] - 1, query[i][2] - 1, m, record[i] + 1); } // If query is of type 1 then // simply add 1 to the record array else { record_sum(record, i, i, m, 1); } } // for type 1 queries adding the contains of // record array to the main array record array for (let i = 0; i < m; i++) { if (query[i][0] == 1) { record_sum(arr, query[i][1] - 1, query[i][2] - 1, n, record[i]); } } // printing the array for (let i = 0; i < n; i++) { document.write(arr[i] + " " ); } // This code is contributed by unknown2108 </script> |
输出：
7 7 0 7 7
上述代码的时间复杂度为 O（n^2）
方法3： 通过应用，这种方法变得更加有效 平方根分解 到记录数组。
C++
// CPP program to perform range queries over range // queries. #include <bits/stdc++.h> #define max 10000 using namespace std; // For prefix sum array void update( int arr[], int l) { arr[l] += arr[l - 1]; } // This function is used to apply square root // decomposition in the record array void record_func( int block_size, int block[], int record[], int l, int r, int value) { // traversing first block in range while (l < r && l % block_size != 0 && l != 0) { record[l] += value; l++; } // traversing completely overlapped blocks in range while (l + block_size <= r + 1) { block[l / block_size] += value; l += block_size; } // traversing last block in range while (l <= r) { record[l] += value; l++; } } // Function to print the resultant array void print( int arr[], int n) { for ( int i = 0; i < n; i++) cout << arr[i] << " " ; } // Driver code int main() { int n = 5, m = 5; int arr[n], record[m]; int block_size = sqrt (m); int block[max]; int command[5][3] = { { 1, 1, 2 }, { 1, 4, 5 }, { 2, 1, 2 }, { 2, 1, 3 }, { 2, 3, 4 } }; memset (arr, 0, sizeof arr); memset (record, 0, sizeof record); memset (block, 0, sizeof block); for ( int i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_func if (command[i][0] == 2) { int x = i / (block_size); record_func(block_size, block, record, command[i][1] - 1, command[i][2] - 1, (block[x] + record[i] + 1)); } // If query is of type 1 then simply add // 1 to the record array else record[i]++; } // Merging the value of the block in the record array for ( int i = 0; i < m; i++) { int check = (i / block_size); record[i] += block[check]; } for ( int i = 0; i < m; i++) { // If query is of type 1 then the array // elements are over-written by the record // array if (command[i][0] == 1) { arr[command[i][1] - 1] += record[i]; if ((command[i][2] - 1) < n - 1) arr[(command[i][2])] -= record[i]; } } // The prefix sum of the array for ( int i = 1; i < n; i++) update(arr, i); // Printing the resultant array print(arr, n); return 0; } |
JAVA
// Java program to perform range queries over range // queries. public class GFG { static final int max = 10000 ; // For prefix sum array static void update( int arr[], int l) { arr[l] += arr[l - 1 ]; } // This function is used to apply square root // decomposition in the record array static void record_func( int block_size, int block[], int record[], int l, int r, int value) { // traversing first block in range while (l < r && l % block_size != 0 && l != 0 ) { record[l] += value; l++; } // traversing completely overlapped blocks in range while (l + block_size <= r + 1 ) { block[l / block_size] += value; l += block_size; } // traversing last block in range while (l <= r) { record[l] += value; l++; } } // Function to print the resultant array static void print( int arr[], int n) { for ( int i = 0 ; i < n; i++) { System.out.print(arr[i] + " " ); } } // Driver code public static void main(String[] args) { int n = 5 , m = 5 ; int arr[] = new int [n], record[] = new int [m]; int block_size = ( int ) Math.sqrt(m); int block[] = new int [max]; int command[][] = {{ 1 , 1 , 2 }, { 1 , 4 , 5 }, { 2 , 1 , 2 }, { 2 , 1 , 3 }, { 2 , 3 , 4 }}; for ( int i = m - 1 ; i >= 0 ; i--) { // If query is of type 2 then function // call to record_func if (command[i][ 0 ] == 2 ) { int x = i / (block_size); record_func(block_size, block, record, command[i][ 1 ] - 1 , command[i][ 2 ] - 1 , (block[x] + record[i] + 1 )); } // If query is of type 1 then simply add // 1 to the record array else { record[i]++; } } // Merging the value of the block in the record array for ( int i = 0 ; i < m; i++) { int check = (i / block_size); record[i] += block[check]; } for ( int i = 0 ; i < m; i++) { // If query is of type 1 then the array // elements are over-written by the record // array if (command[i][ 0 ] == 1 ) { arr[command[i][ 1 ] - 1 ] += record[i]; if ((command[i][ 2 ] - 1 ) < n - 1 ) { arr[(command[i][ 2 ])] -= record[i]; } } } // The prefix sum of the array for ( int i = 1 ; i < n; i++) { update(arr, i); } // Printing the resultant array print(arr, n); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to perform range # queries over range queries. import math max = 10000 # For prefix sum array def update(arr, l): arr[l] + = arr[l - 1 ] # This function is used to apply square root # decomposition in the record array def record_func(block_size, block, record, l, r, value): # Traversing first block in range while (l < r and l % block_size ! = 0 and l ! = 0 ): record[l] + = value l + = 1 # Traversing completely overlapped # blocks in range while (l + block_size < = r + 1 ): block[l / / block_size] + = value l + = block_size # Traversing last block in range while (l < = r): record[l] + = value l + = 1 # Function to print the resultant array def print_array(arr, n): for i in range (n): print (arr[i], end = " " ) # Driver code if __name__ = = "__main__" : n = 5 m = 5 arr = [ 0 ] * n record = [ 0 ] * m block_size = ( int )(math.sqrt(m)) block = [ 0 ] * max command = [ [ 1 , 1 , 2 ], [ 1 , 4 , 5 ], [ 2 , 1 , 2 ], [ 2 , 1 , 3 ], [ 2 , 3 , 4 ] ] for i in range (m - 1 , - 1 , - 1 ): # If query is of type 2 then function # call to record_func if (command[i][ 0 ] = = 2 ): x = i / / (block_size) record_func(block_size, block, record, command[i][ 1 ] - 1 , command[i][ 2 ] - 1 , (block[x] + record[i] + 1 )) # If query is of type 1 then simply add # 1 to the record array else : record[i] + = 1 # Merging the value of the block # in the record array for i in range (m): check = (i / / block_size) record[i] + = block[check] for i in range (m): # If query is of type 1 then the array # elements are over-written by the record # array if (command[i][ 0 ] = = 1 ): arr[command[i][ 1 ] - 1 ] + = record[i] if ((command[i][ 2 ] - 1 ) < n - 1 ): arr[(command[i][ 2 ])] - = record[i] # The prefix sum of the array for i in range ( 1 , n): update(arr, i) # Printing the resultant array print_array(arr, n) # This code is contributed by chitranayal |
C#
// C# program to perform range queries over range // queries. using System; public class GFG { static readonly int max = 10000; // For prefix sum array static void update( int []arr, int l) { arr[l] += arr[l - 1]; } // This function is used to apply square root // decomposition in the record array static void record_func( int block_size, int []block, int []record, int l, int r, int value) { // traversing first block in range while (l < r && l % block_size != 0 && l != 0) { record[l] += value; l++; } // traversing completely overlapped blocks in range while (l + block_size <= r + 1) { block[l / block_size] += value; l += block_size; } // traversing last block in range while (l <= r) { record[l] += value; l++; } } // Function to print the resultant array static void print( int []arr, int n) { for ( int i = 0; i < n; i++) { Console.Write(arr[i] + " " ); } } // Driver code public static void Main() { int n = 5, m = 5; int []arr = new int [n]; int []record = new int [m]; int block_size = ( int ) Math.Sqrt(m); int []block = new int [max]; int [,]command= {{1, 1, 2}, {1, 4, 5}, {2, 1, 2}, {2, 1, 3}, {2, 3, 4}}; for ( int i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_func if (command[i,0] == 2) { int x = i / (block_size); record_func(block_size, block, record, command[i,1] - 1, command[i,2] - 1, (block[x] + record[i] + 1)); } // If query is of type 1 then simply add // 1 to the record array else { record[i]++; } } // Merging the value of the block in the record array for ( int i = 0; i < m; i++) { int check = (i / block_size); record[i] += block[check]; } for ( int i = 0; i < m; i++) { // If query is of type 1 then the array // elements are over-written by the record // array if (command[i,0] == 1) { arr[command[i,1] - 1] += record[i]; if ((command[i,2] - 1) < n - 1) { arr[(command[i,2])] -= record[i]; } } } // The prefix sum of the array for ( int i = 1; i < n; i++) { update(arr, i); } // Printing the resultant array print(arr, n); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to perform range queries over range // queries. let max = 10000; // For prefix sum array function update(arr,l) { arr[l] += arr[l - 1]; } // This function is used to apply square root // decomposition in the record array function record_func(block_size,block,record,l,r,value) { // traversing first block in range while (l < r && l % block_size != 0 && l != 0) { record[l] += value; l++; } // traversing completely overlapped blocks in range while (l + block_size <= r + 1) { let x = Math.floor(l / block_size); block[x] += value; l += block_size; } // traversing last block in range while (l <= r) { record[l] += value; l++; } } // Function to print the resultant array function print(arr,n) { for (let i = 0; i < n; i++) { document.write(arr[i] + " " ); } } // Driver code let n = 5, m = 5; let arr = new Array(n); for (let i = 0; i < n; i++) arr[i] = 0; let record = new Array(m); for (let i = 0; i < m; i++) record[i] = 0; let block_size = Math.floor( Math.sqrt(m)); let block = new Array(max); for (let i = 0; i < max; i++) block[i] = 0; let command = [[1, 1, 2], [1, 4, 5], [2, 1, 2], [2, 1, 3], [2, 3, 4]]; for (let i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_func if (command[i][0] == 2) { let x = Math.floor(i / (block_size)); record_func(block_size, block, record, command[i][1] - 1, command[i][2] - 1, (block[x] + record[i] + 1)); } // If query is of type 1 then simply add // 1 to the record array else { record[i]++; } } // Merging the value of the block in the record array for (let i = 0; i < m; i++) { let check = Math.floor(i / block_size); record[i] += block[check]; } for (let i = 0; i < m; i++) { // If query is of type 1 then the array // elements are over-written by the record // array if (command[i][0] == 1) { arr[command[i][1] - 1] += record[i]; if ((command[i][2] - 1) < n - 1) { arr[(command[i][2])] -= record[i]; } } } // The prefix sum of the array for (let i = 1; i < n; i++) { update(arr, i); } // Printing the resultant array print(arr, n); // This code is contributed by ab2127 </script> |
输出：
7 7 0 7 7
方法4： 通过应用，这种方法变得更加有效 二叉索引树或Fenwick树 通过分别为查询1和查询2创建两个二叉索引树。
C++
// C++ program to perform range queries over range // queries. #include <bits/stdc++.h> using namespace std; // Updates a node in Binary Index Tree (BITree) at given index // in BITree. The given value 'val' is added to BITree[i] and // all of its ancestors in tree. void updateBIT( int BITree[], int n, int index, int val) { // index in BITree[] is 1 more than the index in arr[] index = index + 1; // Traverse all ancestors and add 'val' while (index <= n) { // Add 'val' to current node of BI Tree BITree[index] = (val + BITree[index]); // Update index to that of parent in update View index = (index + (index & (-index))); } return ; } // Constructs and returns a Binary Indexed Tree for given // array of size n. int * constructBITree( int n) { // Create and initialize BITree[] as 0 int * BITree = new int [n + 1]; for ( int i = 1; i <= n; i++) BITree[i] = 0; return BITree; } // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[] int getSum( int BITree[], int index) { int sum = 0; // index in BITree[] is 1 more than the index in arr[] index = index + 1; // Traverse ancestors of BITree[index] while (index > 0) { // Add element of BITree to sum sum = (sum + BITree[index]); // Move index to parent node in getSum View index -= index & (-index); } return sum; } // Function to update the BITree void update( int BITree[], int l, int r, int n, int val) { updateBIT(BITree, n, l, val); updateBIT(BITree, n, r + 1, -val); return ; } // Driver code int main() { int n = 5, m = 5; int temp[15] = { 1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 }; int q[5][3]; int j = 0; for ( int i = 1; i <= m; i++) { q[i][0] = temp[j++]; q[i][1] = temp[j++]; q[i][2] = temp[j++]; } // BITree for query of type 2 int * BITree = constructBITree(m); // BITree for query of type 1 int * BITree2 = constructBITree(n); // Input the queries in a 2D matrix for ( int i = 1; i <= m; i++) cin >> q[i][0] >> q[i][1] >> q[i][2]; // If query is of type 2 then function call // to update with BITree for ( int i = m; i >= 1; i--) if (q[i][0] == 2) update(BITree, q[i][1] - 1, q[i][2] - 1, m, 1); for ( int i = m; i >= 1; i--) { if (q[i][0] == 2) { long int val = getSum(BITree, i - 1); update(BITree, q[i][1] - 1, q[i][2] - 1, m, val); } } // If query is of type 1 then function call // to update with BITree2 for ( int i = m; i >= 1; i--) { if (q[i][0] == 1) { long int val = getSum(BITree, i - 1); update(BITree2, q[i][1] - 1, q[i][2] - 1, n, (val + 1)); } } for ( int i = 1; i <= n; i++) cout << (getSum(BITree2, i - 1)) << " " ; return 0; } |
JAVA
// Java program to perform range queries over range // queries. import java.io.*; import java.util.*; class GFG { // Updates a node in Binary Index Tree (BITree) at given index // in BITree. The given value 'val' is added to BITree[i] and // all of its ancestors in tree. static void updateBIT( int BITree[], int n, int index, int val) { // index in BITree[] is 1 more than the index in arr[] index = index + 1 ; // Traverse all ancestors and add 'val' while (index <= n) { // Add 'val' to current node of BI Tree BITree[index] = (val + BITree[index]); // Update index to that of parent in update View index = (index + (index & (-index))); } return ; } // Constructs and returns a Binary Indexed Tree for given // array of size n. static int [] constructBITree( int n) { // Create and initialize BITree[] as 0 int [] BITree = new int [n + 1 ]; for ( int i = 1 ; i <= n; i++) BITree[i] = 0 ; return BITree; } // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[] static int getSum( int BITree[], int index) { int sum = 0 ; // index in BITree[] is 1 more than the index in arr[] index = index + 1 ; // Traverse ancestors of BITree[index] while (index > 0 ) { // Add element of BITree to sum sum = (sum + BITree[index]); // Move index to parent node in getSum View index -= index & (-index); } return sum; } // Function to update the BITree static void update( int BITree[], int l, int r, int n, int val) { updateBIT(BITree, n, l, val); updateBIT(BITree, n, r + 1 , -val); return ; } // Driver code public static void main (String[] args) { int n = 5 , m = 5 ; int temp[] = { 1 , 1 , 2 , 1 , 4 , 5 , 2 , 1 , 2 , 2 , 1 , 3 , 2 , 3 , 4 }; int [][] q = new int [ 6 ][ 3 ]; int j = 0 ; for ( int i = 1 ; i <= m; i++) { q[i][ 0 ] = temp[j++]; q[i][ 1 ] = temp[j++]; q[i][ 2 ] = temp[j++]; } // BITree for query of type 2 int [] BITree = constructBITree(m); // BITree for query of type 1 int [] BITree2 = constructBITree(n); // Input the queries in a 2D matrix /*Scanner sc=new Scanner(System.in); for (int i = 1; i <= m; i++) { q[i][0]=sc.nextInt(); q[i][1]=sc.nextInt(); q[i][2]=sc.nextInt(); }*/ // If query is of type 2 then function call // to update with BITree for ( int i = m; i >= 1 ; i--) if (q[i][ 0 ] == 2 ) update(BITree, q[i][ 1 ] - 1 , q[i][ 2 ] - 1 , m, 1 ); for ( int i = m; i >= 1 ; i--) { if (q[i][ 0 ] == 2 ) { int val = getSum(BITree, i - 1 ); update(BITree, q[i][ 1 ] - 1 , q[i][ 2 ] - 1 , m, val); } } // If query is of type 1 then function call // to update with BITree2 for ( int i = m; i >= 1 ; i--) { if (q[i][ 0 ] == 1 ) { int val = getSum(BITree, i - 1 ); update(BITree2, q[i][ 1 ] - 1 , q[i][ 2 ] - 1 , n, (val + 1 )); } } for ( int i = 1 ; i <= n; i++) System.out.print(getSum(BITree2, i - 1 )+ " " ); } } // This code is contributed by avanitrachhadiya2155 |
C#
// C# program to perform range queries over range // queries. using System; class GFG{ // Updates a node in Binary Index Tree (BITree) // at given index in BITree. The given value // 'val' is added to BITree[i] and // all of its ancestors in tree. static void updateBIT( int [] BITree, int n, int index, int val) { // index in BITree[] is 1 more than // the index in arr[] index = index + 1; // Traverse all ancestors and add 'val' while (index <= n) { // Add 'val' to current node of BI Tree BITree[index] = (val + BITree[index]); // Update index to that of parent in update View index = (index + (index & (-index))); } return ; } // Constructs and returns a Binary Indexed // Tree for given array of size n. static int [] constructBITree( int n) { // Create and initialize BITree[] as 0 int [] BITree = new int [n + 1]; for ( int i = 1; i <= n; i++) BITree[i] = 0; return BITree; } // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[] static int getSum( int [] BITree, int index) { int sum = 0; // index in BITree[] is 1 more than // the index in arr[] index = index + 1; // Traverse ancestors of BITree[index] while (index > 0) { // Add element of BITree to sum sum = (sum + BITree[index]); // Move index to parent node in getSum View index -= index & (-index); } return sum; } // Function to update the BITree static void update( int [] BITree, int l, int r, int n, int val) { updateBIT(BITree, n, l, val); updateBIT(BITree, n, r + 1, -val); return ; } // Driver code static public void Main() { int n = 5, m = 5; int [] temp = { 1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 }; int [,] q = new int [6, 3]; int j = 0; for ( int i = 1; i <= m; i++) { q[i, 0] = temp[j++]; q[i, 1] = temp[j++]; q[i, 2] = temp[j++]; } // BITree for query of type 2 int [] BITree = constructBITree(m); // BITree for query of type 1 int [] BITree2 = constructBITree(n); // If query is of type 2 then function call // to update with BITree for ( int i = m; i >= 1; i--) if (q[i, 0] == 2) update(BITree, q[i, 1] - 1, q[i, 2] - 1, m, 1); for ( int i = m; i >= 1; i--) { if (q[i,0] == 2) { int val = getSum(BITree, i - 1); update(BITree, q[i, 1] - 1, q[i, 2] - 1, m, val); } } // If query is of type 1 then function call // to update with BITree2 for ( int i = m; i >= 1; i--) { if (q[i,0] == 1) { int val = getSum(BITree, i - 1); update(BITree2, q[i, 1] - 1, q[i, 2] - 1, n, (val + 1)); } } for ( int i = 1; i <= n; i++) Console.Write(getSum(BITree2, i - 1) + " " ); } } // This code is contributed by rag2127 |
输出：
7 7 0 7 7
方法3和方法4的时间复杂度为 O（对数n） .
本文由 莫哈克·阿格拉瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
