C 语言 Mo 算法

Mo 算法 是一种智能且高效的算法，用于回答静态数组上的重复区间查询，主要用于竞争性编程。当我们需要离线进行预处理查询时（即，我们提前知道所有查询，而无需立即响应每个查询），它非常有用。在这些示例中，Mo 算法之所以有效，是因为它极大地改进了朴素方法。区间查询是算法问题中最常见的问题之一。

例如，给定一个数组，对于许多查询，您可能希望计算索引 L 和 R 之间的元素总和。虽然对于此类查询有高效的动态解决方案，例如段树或通常称为二叉索引树的 Fenwick 树，但 Mo 算法更适合静态数组，其中数组的成员在处理查询阶段不会改变。虽然这些问题有高效的动态解决方案，例如段树或 Fenwick 树（有时称为二叉索引树），但 Mo 算法更适合静态数组，其中数组元素在查询处理阶段不会发生变化。

Mo 算法的必要性是什么？

要理解 Mo 算法的适用性，了解更直接方法的局限性很重要。假设我们有一个大小为 n 的数组，并且我们必须回答 q 个区间求和查询。然后，对于每个查询，我们可以简单地遍历数组，每个查询的时间复杂度为 O(n)。因此，所有 q 个查询的总时间复杂度将累加到 O(nq)。对于较小的 n 和 q 值，这可能有效，但对于大型数据集，当 n 和 q 达到数十万甚至数百万时，它可能会消耗大量计算时间。

这正是 Mo 算法发挥作用的地方。它避免了冗余操作，并大大减少了每次查询更新范围所花费的时间。查询的重新排列精确地创建了一个处理模式，该模式仅进行小的修改，例如添加或删除元素，而不是为每个查询重新计算整个范围。

现实生活中的比较

想象一下，您有一个包含数千万个条目的数组，并且想要计算多个子数组的总和。您无需为每个子数组一遍又一遍地计算总和；相反，您可以“滑动”遍历数组。您需要做的就是滑动，只在新项目位于范围内时添加它们，在范围外时删除它们。这种微小变化的过程是 Mo 算法的核心。

没有 Mo 算法，您需要为要提出的每个查询从头开始解决此问题，这可能意味着重新计算您已经在先前查询中计算过的总和。这在概念上类似于解决一系列拼图，其中每个拼图与前一个拼图共享一些碎片，但您必须从头开始重新组装每个拼图。另一方面，Mo 算法节省了时间和精力：它重复使用拼图的碎片。

Mo 算法的应用

由于其良好的灵活性，Mo 算法可用于处理大量需要对数组进行静态区间查询的问题。它在竞争性编程领域很重要，因为它可以非常高效地处理固定数组上的大量查询。让我们看看下面 Mo 算法表现良好的几个典型应用场景。

1. 总和查询

回答大量的区间求和查询可能是 Mo 算法最直观的应用。假设我们有一个整数数组，并且需要为大量的查询报告索引 L 和 R 之间的元素总和。因此，在朴素方法下，每个此类查询的时间复杂度都为 O(n)，其中 n 是数组的大小。对于大型数据集，O(nq) 的查询总时间复杂度可能会慢得令人无法接受。

考虑一个示例数组 [1, 2, 3, 4, 5] 和两个查询，例如。

从索引 0 到但不包括索引 3 有多少个元素？

索引 1 到索引 4 的值的总和是多少？

对于第二个问题，由于 Mo 算法，我们不关心我们如何计算总和。对于第二个查询，我们从第一个查询的总和中减去第一个元素，并添加最后一个元素以得出结果。

2. 差异元素查询

最明显的用法似乎是查找子数组中不同元素的数量。解决此问题的一种朴素方法是创建一个数据结构（如集合或哈希映射）来跟踪不同元素，然后在每次查询时扫描整个子数组。全局而言，此算法的时间复杂度为 O(nq)，每个查询的时间复杂度为 O(n)。

使用 Mo 算法，我们可以显着降低时间复杂度。该算法通过维护给定范围内元素的频率计数来工作。随着查询范围的变化，我们会增加或减少范围内的元素数量。当计数从 0 变为 1 时，一个元素将被添加到唯一元素集中，当计数回落到 0 时，它将从集中移除。增量方法使我们能够确保每个查询都不需要完全重新计算唯一元素的数量。例如，给定一个计算索引 1 到索引 4 之间唯一元素数量的范围查询，我们返回数组 [1, 2, 1, 3, 4]，其中包含 4 个唯一元素：2、1、3、4。如果下一个查询要求计算索引 0 到索引 3 之间的唯一元素数量，我们只需添加第一个元素并更新计数。

3. 查询频率

可以将 Mo 算法进一步推广，以回答有关给定区间中某个元素的频率的查询。例如，要计算某个给定数字在两个索引之间出现了多少次，我们可以在更新查询区间时维护一个频率数组。

这些是典型的问题用例，您想知道子数组中最频繁的元素是什么，或者某个给定元素是否已超过某个特定频率。Mo 算法可以通过对查询进行排序，然后随着范围的移动不断更新频率计数，来快速回答这些查询。

4. 子数组逆序

一种朴素的统计大数组子数组中逆序对数量的方法耗时过长，因为它会检查子数组中的每一对元素，导致每个查询的时间复杂度为 O(n^2)。Mo 算法可以通过对查询进行排序，然后逐渐更改范围同时更新逆序对计数来大大减少这种情况。

要将 Mo 算法应用于此问题，我们在每次更新查询范围时维护逆序对计数。本质上，当一个元素被引入或从范围中移除时，就会发生逆序对，因为它需要与已存在于范围中的元素进行比较。

例如，在 [2,4,1,3,5] 中，由于 4 > 1，位于 (4, 1) 的列表元素存在逆序对。如果 Mo 算法维护一个计数，说明随着区间修改，逆序对计数如何变化，它就可以轻松找到索引 0 和 3 之间的逆序对数量。

5. 最大和最小数量查询

使用 Mo 算法的变体可以解决询问区间最大或最小元素的范围查询。虽然在这种情况下通常会使用稀疏表或段树等数据结构，但 Mo 算法对于高效地回答静态查询非常有用，即使在动态设置中也是如此。

与在其他用例中的思想相同：在更改查询范围时，逐步更新最大值或最小值。因此，我们无需每次都从头开始计算每个查询的最大值或最小值。

例如，如果一个问题要求找到区间 1-3 中的最大元素，并且给定数组 [5, 2, 9, 3, 6]，Mo 算法会通过移动区间而无需每次都计算最大值来轻松解决此问题。

在处理大型数组和大量搜索时，Mo 算法为许多静态区间查询问题提供了一种高效的解决方案。

Mo 算法通过增量处理查询，显着降低了与 CPU 相关的操作开销。这不仅适用于简单的求和查询，还适用于更复杂的任务，例如不同项的数量、频率跟踪、逆序对查找或子数组中的最大/最小值识别。竞争性程序员依赖 Mo 算法进行静态区间查询，因为它高效、通用且易于实现。

步骤 1：表示查询的结构

在这里，我们定义一个 Query 结构来存储每个查询，包括左、右范围端点 L 和 R，以及一个索引 idx，用于在排序后将结果映射回原始查询。

比较函数首先按块然后按右端点对查询进行排序。

步骤 2：Mo 算法核心逻辑

步骤 3：示例用法

输出

8
4
6

每个查询包括：

• L：查询的左端点。
• R：查询的右端点。
• idx：查询的索引，用于在处理后按正确顺序存储结果。

moAlgorithm() 函数

此函数使用 Mo 算法处理查询。它接受：

• arr[]：输入数组。
• n：数组的大小。
• queries[]：查询结构的数组。
• q：查询的数量。

  查询处理

  该算法维护两个指针 currentL 和 currentR，它们定义了当前范围。对于每个查询：

  • 通过移动 currentL 和 currentR 来扩展或收缩范围，使其匹配查询的范围 [L, R]。
  • 如果 currentL 小于 L，则从左端移除元素，并调整 currentSum。
  • 如果 currentL 大于 L，则从左侧重新添加元素。
  • 如果 currentR 小于或等于 R，则从右侧添加元素。
  • 如果 currentR 大于 R，则从右侧移除元素。

  ---

  下一主题Optimal-merge-pattern-in-c
  
   
  ← 上一篇 下一篇 →