MO 的算法（查询平方根分解）| 系列 1（简介） · GeeksForGeeks 中文系列教程

# MO 的算法（查询平方根分解）| 系列 1（简介） > 原文： [https://www.geeksforgeeks.org/mos-algorithm-query-square-root-decomposition-set-1-introduction/](https://www.geeksforgeeks.org/mos-algorithm-query-square-root-decomposition-set-1-introduction/) 让我们考虑以下问题，以了解 MO 的算法。给我们一个数组和一组查询范围，我们需要找到每个查询范围的总和。例： ``` 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 ``` **朴素的解决方案**将运行从`L`到`R`的循环，并为每个查询`[L, R]`计算给定范围内的元素总数。 ## 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; } ``` ## Python3 ```py # 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 ``` ## Java ```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 ``` 输出： ``` Sum of [0, 4] is 8 Sum of [1, 3] is 4 Sum of [2, 4] is 6 ``` 上述解决方案的时间复杂度为`O(mn)`。 **MO 的算法**的想法是对所有查询进行预处理，以便一个查询的结果可以在下一个查询中使用。以下是步骤。假设 **a [0…n-1]** 为输入数组， **q [0..m-1]** 为查询数组。 1. 对所有查询进行排序，将`L`值从 **0** 到`√n– 1`的查询放在一起，然后将所有从`√n`到`2√n– 1`的查询组合在一起，依此类推。块中的所有查询均按`R`值的升序排序。 2. 以每个查询都使用上一个查询中计算出的总和的方式逐一处理所有查询。 * 假设`sum`为上一个查询的总和。 * 删除上一个查询的其他元素。例如，如果先前的查询为`[0, 8]`而当前的查询为`[3, 9]`，则我们从总和中减去`a[0]`，`a[1]`和`a[2]` * 添加当前查询的新元素。在与上述相同的示例中，我们将`a[9]`加到`sum`上。此算法的妙处在于，在第 2 步中，R 的索引变量在整个运行过程中最多`O(n * √n)`次变化，而`L`的索引变量最多`O(m * √n)`次（有关详细信息，请参见下面的代码后）。所有这些限制都是可能的，因为查询首先以`√n`大小的块排序。预处理部分需要`O(m Log m)`时间。处理所有查询需要`O(n * √n) + O(m *√n) = O((m + n)* √n)`时间。以下是上述想法的 C++ 实现。 ## C++ ```cpp // 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; } ``` ## Python3 ```py # 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 ``` ## Java ```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 ``` Output: ``` Sum of [1, 3] is 4 Sum of [0, 4] is 8 Sum of [2, 4] is 6 ``` 由于查询已排序，因此上述程序的输出不会以与输入相同的顺序打印查询结果。该程序可以轻松扩展以保持相同的顺序。 **重要观察**： 1. 所有查询都是事先知道的，以便可以对其进行预处理 2. 它不适用于我们同时进行了更新操作和总和查询的问题。 3. MO 的算法只能用于查询问题，在该问题中，可以根据前一个查询的结果来计算查询。再一个例子是最大或最小。 **时间复杂度分析**：该函数主要为所有排序的查询运行一个`for`循环。在`for`循环中，有四个`while`查询可移动`currL`和`currR`。 **移动了多少`currR`？** 对于每个块，查询以`R`的升序排序。因此，对于一个块，`currR`以升序移动。最坏的情况是，在每个块开始之前，`currR`位于最右端，当前块将其移回最左端。这意味着，对于每个块，`currR`最多移动`O(n)`。由于存在`O(√n)`个块，因此`currR`的总移动量为`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 算法的更有趣的问题。 [范围最小查询（平方根分解和稀疏表）](https://www.geeksforgeeks.org/range-minimum-query-for-static-array/) **参考**： [http://blog.anudeep2011.com/mos-algorithm/](http://blog.anudeep2011.com/mos-algorithm/)