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/)