MO 的算法（平方根分解查询） | 系列 1（简介）
原文： 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
# 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 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]为查询数组。
-
对所有查询进行排序，将
L值从 0 到√n– 1的查询放在一起，然后将所有从√n到2√n– 1的查询组合在一起 ，依此类推。 块中的所有查询均按R值的升序排序。 -
以每个查询都使用上一个查询中计算出的总和的方式逐一处理所有查询。
-
假设
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++
// 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
# 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 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
由于查询已排序，因此上述程序的输出不会以与输入相同的顺序打印查询结果。 该程序可以轻松扩展以保持相同的顺序。
重要观察：
-
所有查询都是事先知道的，以便可以对其进行预处理。
-
它不适用于我们同时进行了更新操作和总和查询的问题。
-
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 算法的更有趣的问题。
参考：
http://blog.anudeep2011.com/mos-algorithm/
版权属于：月萌API www.moonapi.com，转载请注明出处
