MO算法（查询平方根分解）| 第一部分（介绍）

让我们通过下面的问题来理解 MO 算法。给定一个数组和一个查询范围集合，我们需要求出每个查询范围的元素之和。

示例

MO 算法的核心思想是预处理所有查询，以便一个查询的结果可以被下一个查询使用。具体步骤如下：

MO 算法的思路

设 a[0...n-1] 为输入数组。

• 排序查询：以特定的方式对所有查询进行排序。排序的依据是：

* 首先按 L 值所在的块排序。

* 如果 INLINECODE5111a44d 值在同一块内，则按 INLINECODE858359c1 值排序。

通过这种排序，我们确保在处理所有查询的过程中，INLINECODEd2fd7c1d 指针的值在 INLINECODE7c2a5d3a 的时间内变化，R 指针的变化同样在可控范围内。

• 处理所有查询：

* 预处理：排序部分的时间复杂度为 O(m Log m)。

* 查询处理：处理所有查询的时间复杂度为 O((m+n) * √n)。

下面是上述思路的具体实现代码。

C++ 实现

// 计算不同范围查询的区间和的程序
#include 
using namespace std;

// 表示块大小的变量。设为全局变量以便 sort 的 compare() 函数使用
int block;

// 表示查询范围的结构体
struct Query {
    int L, R;
};

// 用于排序所有查询的函数，使得同一块的查询排列在一起，
// 且在同一个块内，查询按 R 值的递增顺序排列。
bool compare(Query x, Query y) {
    // 不同的块，按块号排序
    if (x.L / block != y.L / block)
        return x.L / block < y.L / block;
    // 同一块内，按 R 值排序
    return x.R < y.R;
}

// 打印所有查询范围的和。m 是查询的数量，n 是数组 a[] 的大小
void queryResults(int a[], int n, Query q[], int m) {
    // 计算块大小
    block = (int)sqrt(n);

    // 对所有查询进行排序，使相同块的查询安排在一起
    sort(q, q + m, compare);

    // 初始化当前的 L, R 和当前和
    int currL = 0, currR = 0;
    int currSum = 0;

    // 遍历所有查询
    for (int i = 0; i < m; i++) {
        // 当前范围的 L 和 R 值
        int L = q[i].L, R = q[i].R;

        // 移除上一个范围中多余的元素。
        // 例如，如果上一个范围是 [0, 3]，当前范围是 [2, 5]，
        // 则需要减去 a[0] 和 a[1]
        while (currL  L) {
            currSum += a[currL - 1];
            currL--;
        }
        while (currR  R + 1) {
            currSum -= a[currR - 1];
            currR--;
        }

        // 打印当前范围的和
        cout << "Sum of [" << L << ", " << R << "] is " << currSum << endl;
    }
}

// 主程序
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 程序
import java.util.*;

// 表示查询范围的类
class Query {
    int L;
    int R;
    Query(int L, int R) {
        this.L = L;
        this.R = R;
    }
}

class MO {
    // 打印所有查询范围的和。m 是查询的数量，n 是数组 a[] 的大小
    static void queryResults(int a[], int n, ArrayList q, int m) {
        // 计算块大小
        int block = (int) Math.sqrt(n);

        // 对所有查询进行排序，使相同块的查询安排在一起
        Collections.sort(q, new Comparator() {
            // 用于排序所有查询的函数，使得同一块的查询排列在一起，
            // 且在同一个块内，查询按 R 值的递增顺序排列。
            public int compare(Query x, Query y) {
                // 不同的块，按块号排序
                if (x.L / block != y.L / block)
                    return (x.L < y.L ? -1 : 1);
                // 同一块内，按 R 值排序
                return (x.R < y.R ? -1 : 1);
            }
        });

        // 初始化当前的 L, R 和当前和
        int currL = 0, currR = 0;
        int currSum = 0;

        // 遍历所有查询
        for (int i = 0; i < m; i++) {
            // 当前范围的 L 和 R 值
            int L = q.get(i).L, R = q.get(i).R;

            // 移除上一个范围中多余的元素。
            // 例如，如果上一个范围是 [0, 3]，当前范围是 [2, 5]，
            // 则需要减去 a[0] 和 a[1]
            while (currL  L) {
                currSum += a[currL - 1];
                currL--;
            }
            while (currR  R + 1) {
                currSum -= a[currR - 1];
                currR--;
            }

            // 打印当前范围的和
            System.out.println("Sum of [" + L + ", " + R + "] is " + currSum);
        }
    }

    // 主程序
    public static void main(String argv[]) {
        ArrayList q = new ArrayList();
        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());
    }
}

> 注意：上述代码展示了如何利用之前查询的结果来高效地计算当前查询的和，极大地减少了重复计算。