让我们考虑下面的问题来理解MO算法。 我们得到一个数组和一组查询范围，我们需要找到每个查询范围的总和。
null
例子：
Input: arr[] = {1, 1, 2, 1, 3, 4, 5, 2, 8}; query[] = [0, 4], [1, 3] [2, 4]Output: Sum of arr[] elements in range [0, 4] is 8 Sum of arr[] elements in range [1, 3] is 4 Sum of arr[] elements in range [2, 4] is 6
A. 天真的解决方案 就是从L到R运行一个循环，并计算每个查询在给定范围内的元素之和[L，R]
C++
// C++ Program to compute sum of ranges for different range // queries. #include <bits/stdc++.h> using namespace std; // Structure to represent a query range struct Query { int L, R; }; // Prints sum of all query ranges. m is number of queries // n is the size of the array. void printQuerySums( int a[], int n, Query q[], int m) { // One by one compute sum of all queries for ( int i=0; i<m; i++) { // Left and right boundaries of current range int L = q[i].L, R = q[i].R; // Compute sum of current query range int sum = 0; for ( int j=L; j<=R; j++) sum += a[j]; // Print sum of current query range cout << "Sum of [" << L << ", " << R << "] is " << sum << endl; } } // Driver program int main() { int a[] = {1, 1, 2, 1, 3, 4, 5, 2, 8}; int n = sizeof (a)/ sizeof (a[0]); Query q[] = {{0, 4}, {1, 3}, {2, 4}}; int m = sizeof (q)/ sizeof (q[0]); printQuerySums(a, n, q, m); return 0; } |
JAVA
// Java Program to compute sum of ranges for different range // queries. import java.util.*; // Class to represent a query range class Query{ int L; int R; Query( int L, int R){ this .L = L; this .R = R; } } class GFG { // Prints sum of all query ranges. m is number of queries // n is the size of the array. static void printQuerySums( int a[], int n, ArrayList<Query> q, int m) { // One by one compute sum of all queries for ( int i= 0 ; i<m; i++) { // Left and right boundaries of current range int L = q.get(i).L, R = q.get(i).R; // Compute sum of current query range int sum = 0 ; for ( int j=L; j<=R; j++) sum += a[j]; // Print sum of current query range System.out.println( "Sum of [" + L + ", " + R + "] is " + sum); } } // Driver program public static void main(String argv[]) { int a[] = { 1 , 1 , 2 , 1 , 3 , 4 , 5 , 2 , 8 }; int n = a.length; ArrayList<Query> q = new ArrayList<Query>(); q.add( new Query( 0 , 4 )); q.add( new Query( 1 , 3 )); q.add( new Query( 2 , 4 )); int m = q.size(); printQuerySums(a, n, q, m); } } // This code is contributed by shivanisinghss2110 |
Python3
# Python program to compute sum of ranges for different range queries. # Function that accepts array and list of queries and print sum of each query def printQuerySum(arr,Q): for q in Q: # Traverse through each query L,R = q # Extract left and right indices s = 0 for i in range (L,R + 1 ): # Compute sum of current query range s + = arr[i] print ( "Sum of" ,q, "is" ,s) # Print sum of current query range # Driver script arr = [ 1 , 1 , 2 , 1 , 3 , 4 , 5 , 2 , 8 ] Q = [[ 0 , 4 ], [ 1 , 3 ], [ 2 , 4 ]] printQuerySum(arr,Q) #This code is contributed by Shivam Singh |
C#
// C# program to compute sum of ranges for // different range queries using System; using System.Collections; // Class to represent a query range public class Query { public int L; public int R; public Query( int L, int R) { this .L = L; this .R = R; } } class GFG{ // Prints sum of all query ranges. m //is number of queries n is the size // of the array. static void printQuerySums( int []a, int n, ArrayList q, int m) { // One by one compute sum of all queries for ( int i = 0; i < m; i++) { // Left and right boundaries of // current range int L = ((Query)q[i]).L, R = ((Query)q[i]).R; // Compute sum of current query range int sum = 0; for ( int j = L; j <= R; j++) sum += a[j]; // Print sum of current query range Console.Write( "Sum of [" + L + ", " + R + "] is " + sum + "" ); } } // Driver code public static void Main( string []argv) { int []a = { 1, 1, 2, 1, 3, 4, 5, 2, 8 }; int n = a.Length; ArrayList q = new ArrayList(); q.Add( new Query(0, 4)); q.Add( new Query(1, 3)); q.Add( new Query(2, 4)); int m = q.Count; printQuerySums(a, n, q, m); } } // This code is contributed by pratham76 |
Javascript
<script> // Javascript Program to compute sum of ranges for different range // queries. // Class to represent a query range class Query{ constructor(L, R) { this .L = L; this .R = R; } } // Prints sum of all query ranges. m is number of queries // n is the size of the array. function printQuerySums(a, n, q, m) { // One by one compute sum of all queries for (let i = 0; i < m; i++) { // Left and right boundaries of current range let L = q[i].L, R = q[i].R; // Compute sum of current query range let sum = 0; for (let j = L; j <= R; j++) sum += a[j]; // Print sum of current query range document.write( "Sum of [" + L + ", " + R + "] is " + sum+ "<br>" ); } } // Driver program let a = [1, 1, 2, 1, 3, 4, 5, 2, 8]; let n = a.length; let q = []; q.push( new Query(0,4)); q.push( new Query(1,3)); q.push( new Query(2,4)); let m = q.length; printQuerySums(a, n, q, m); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
Sum of [0, 4] is 8Sum of [1, 3] is 4Sum of [2, 4] is 6
上述解的时间复杂度为O（mn）。 关于 莫氏算法 是对所有查询进行预处理，以便在下一个查询中使用一个查询的结果。以下是步骤。
允许 a[0…n-1] 输入数组和 q[0..m-1] 可以是一个查询数组。
- 对所有查询进行排序，使使用L值的查询 0 到 √n–1 将所有查询放在一起 √N 到 2*√n–1 等等块内的所有查询都按R值的递增顺序排序。
- 逐个处理所有查询，每个查询都使用上一个查询中计算的总和。
- 让“sum”是前一个查询的总和。
- 删除上一个查询的额外元素。例如，如果前一个查询是[0,8]，而当前查询是[3,9]，那么我们从总和中减去[0]、[1]和[2]
- 添加当前查询的新元素。在与上面相同的示例中，我们将[9]添加到总和。
这个算法最大的优点是，在第二步中，索引变量最多为R变化 O（n*√n） 在整个运行过程中，L的次数最多会改变其值 O（m*√n） 时间（请参见下面代码后面的详细信息）。所有这些界限都是可能的，只是因为查询首先按块排序 √N 大小
预处理部分需要O（m logm）时间。
处理所有查询需要花费大量时间 O（n*√n） + O（m*√n） = O（（m+n）*√n） 时间
下面是上述想法的实施。
C++
// Program to compute sum of ranges for different range // queries #include <bits/stdc++.h> using namespace std; // Variable to represent block size. This is made global // so compare() of sort can use it. int block; // Structure to represent a query range struct Query { int L, R; }; // Function used to sort all queries so that all queries // of the same block are arranged together and within a block, // queries are sorted in increasing order of R values. bool compare(Query x, Query y) { // Different blocks, sort by block. if (x.L/block != y.L/block) return x.L/block < y.L/block; // Same block, sort by R value return x.R < y.R; } // Prints sum of all query ranges. m is number of queries // n is size of array a[]. void queryResults( int a[], int n, Query q[], int m) { // Find block size block = ( int ) sqrt (n); // Sort all queries so that queries of same blocks // are arranged together. sort(q, q + m, compare); // Initialize current L, current R and current sum int currL = 0, currR = 0; int currSum = 0; // Traverse through all queries for ( int i=0; i<m; i++) { // L and R values of current range int L = q[i].L, R = q[i].R; // Remove extra elements of previous range. For // example if previous range is [0, 3] and current // range is [2, 5], then a[0] and a[1] are subtracted while (currL < L) { currSum -= a[currL]; currL++; } // Add Elements of current Range while (currL > L) { currSum += a[currL-1]; currL--; } while (currR <= R) { currSum += a[currR]; currR++; } // Remove elements of previous range. For example // when previous range is [0, 10] and current range // is [3, 8], then a[9] and a[10] are subtracted while (currR > R+1) { currSum -= a[currR-1]; currR--; } // Print sum of current range cout << "Sum of [" << L << ", " << R << "] is " << currSum << endl; } } // Driver program int main() { int a[] = {1, 1, 2, 1, 3, 4, 5, 2, 8}; int n = sizeof (a)/ sizeof (a[0]); Query q[] = {{0, 4}, {1, 3}, {2, 4}}; int m = sizeof (q)/ sizeof (q[0]); queryResults(a, n, q, m); return 0; } |
JAVA
// Java Program to compute sum of ranges for // different range queries import java.util.*; // Class to represent a query range class Query{ int L; int R; Query( int L, int R){ this .L = L; this .R = R; } } class MO{ // Prints sum of all query ranges. m is number of queries // n is size of array a[]. static void queryResults( int a[], int n, ArrayList<Query> q, int m){ // Find block size int block = ( int ) Math.sqrt(n); // Sort all queries so that queries of same blocks // are arranged together. Collections.sort(q, new Comparator<Query>(){ // Function used to sort all queries so that all queries // of the same block are arranged together and within a block, // queries are sorted in increasing order of R values. public int compare(Query x, Query y){ // Different blocks, sort by block. if (x.L/block != y.L/block) return (x.L < y.L ? - 1 : 1 ); // Same block, sort by R value return (x.R < y.R ? - 1 : 1 ); } }); // Initialize current L, current R and current sum int currL = 0 , currR = 0 ; int currSum = 0 ; // Traverse through all queries for ( int i= 0 ; i<m; i++) { // L and R values of current range int L = q.get(i).L, R = q.get(i).R; // Remove extra elements of previous range. For // example if previous range is [0, 3] and current // range is [2, 5], then a[0] and a[1] are subtracted while (currL < L) { currSum -= a[currL]; currL++; } // Add Elements of current Range while (currL > L) { currSum += a[currL- 1 ]; currL--; } while (currR <= R) { currSum += a[currR]; currR++; } // Remove elements of previous range. For example // when previous range is [0, 10] and current range // is [3, 8], then a[9] and a[10] are subtracted while (currR > R+ 1 ) { currSum -= a[currR- 1 ]; currR--; } // Print sum of current range System.out.println( "Sum of [" + L + ", " + R + "] is " + currSum); } } // Driver program public static void main(String argv[]){ ArrayList<Query> q = new ArrayList<Query>(); q.add( new Query( 0 , 4 )); q.add( new Query( 1 , 3 )); q.add( new Query( 2 , 4 )); int a[] = { 1 , 1 , 2 , 1 , 3 , 4 , 5 , 2 , 8 }; queryResults(a, a.length, q, q.size()); } } // This code is contributed by Ajay |
Python3
# Python program to compute sum of ranges for different range queries import math # Function that accepts array and list of queries and print sum of each query def queryResults(arr,Q): #Q.sort(): # Sort by L #sort all queries so that all queries in the increasing order of R values . Q.sort(key = lambda x: x[ 1 ]) # Initialize current L, current R and current sum currL,currR,currSum = 0 , 0 , 0 # Traverse through all queries for i in range ( len (Q)): L,R = Q[i] # L and R values of current range # Remove extra elements from previous range # if previous range is [0, 3] and current # range is [2, 5], then a[0] and a[1] are subtracted while currL<L: currSum - = arr[currL] currL + = 1 # Add elements of current range while currL>L: currSum + = arr[currL - 1 ] currL - = 1 while currR< = R: currSum + = arr[currR] currR + = 1 # Remove elements of previous range # when previous range is [0, 10] and current range # is [3, 8], then a[9] and a[10] are subtracted while currR>R + 1 : currSum - = arr[currR - 1 ] currR - = 1 # Print the sum of current range print ( "Sum of" ,Q[i], "is" ,currSum) arr = [ 1 , 1 , 2 , 1 , 3 , 4 , 5 , 2 , 8 ] Q = [[ 0 , 4 ], [ 1 , 3 ], [ 2 , 4 ]] queryResults(arr,Q) #This code is contributed by Shivam Singh |
输出：
Sum of [1, 3] is 4Sum of [0, 4] is 8Sum of [2, 4] is 6
上述程序的输出不会以与输入相同的顺序打印查询结果，因为查询是经过排序的。该程序可以很容易地扩展，以保持相同的顺序。
重要观察结果：
- 所有的查询都是预先知道的，因此可以对它们进行预处理
- 它不适用于更新操作与求和查询混合的问题。
- MO的算法只能用于查询问题，其中一个查询可以根据前一个查询的结果进行计算。还有一个这样的例子是最大值或最小值。
时间复杂性分析： 该函数主要为所有排序的查询运行for循环。在for循环中，有四个while查询移动“currL”和“currR”。
移动了多少现金？ 对于每个块，查询按R的递增顺序排序。因此，对于一个块，curr按递增顺序移动。在最坏的情况下，在每个区块开始之前，最右边的Curr和当前区块会将其移回最左边。这意味着，对于每个区块，Curr最多移动一次 O（n） .既然有 O(√n） 块，电流的总移动量为 O（n*√n） .
移动了多少currL？ 由于所有查询都是以L值按块分组的方式进行排序的，因此移动是非常困难的 O(√n） 当我们从一个查询移动到另一个查询时。对于m查询，currL的总移动量为 O（m*√n） 请注意，解决这个问题的一个简单且更有效的解决方案是计算从0到n-1的所有元素的前缀和。让前缀和存储在数组preSum[]中（preSum[i]的值存储arr[0..i]的和）。一旦我们构建了preSum[]，我们就可以逐个遍历所有查询。对于每个查询[L，R]，我们都返回preSum[R]–preSum[L]的值。在这里，处理每个查询需要O（1）个时间。
本文的目的是用一个非常简单的例子介绍MO的算法。我们将很快讨论使用MO算法的更有趣的问题。
参考资料： http://blog.anudeep2011.com/mos-algorithm/ 本文由 鲁希尔·加格 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
