C++ 中带更新和不带更新的 Mo 算法

Mo 算法（Mo's Algorithm）是一种离线算法，它结合了平方根分解，可以有效地回答范围查询、求和、频率计数等操作。它将数组分成大小为 √N（数组大小）的块，从而避免了冗余计算并优化了查询处理。查询首先按块索引排序，然后在每个块内按查询的右端点排序。这种排序方式可以保证在两指针法（左指针和右指针）添加或删除元素到当前范围时，移动次数最少。

在 Mo 算法的经典版本中，数组是固定的，在范围查询之间不进行更新。所有查询都会被排序，然后按高效的顺序处理。使用双指针来维护一个当前范围。通过使用辅助结构（如用于计数不同值的频率数组），元素可以以恒定的时间进行添加和删除。对于具有大量查询的静态数组来说，它非常高效。

当数组不再是静态的（例如，在查询之间发生更新，如点更新）时，我们就需要额外的机制。这些可以通过离线存储并与查询一起处理，或者在线使用辅助数据结构（如线段树或 Fenwick 树）来处理。由于必须插入数组的更新，并且需要有效地回答新数组的范围查询，因此复杂性会进一步增加。

因此，虽然静态算法对于没有修改的固定数组是最优的，但带有更新的算法则牺牲了简单性以换取灵活性。这两种版本都广泛用于有效地解决范围查询问题，而朴素方法速度太慢。

带有更新的 Mo 算法

Mo 算法是一种有效的离线算法，用于使用平方根分解在数组上回答范围查询（求和、计数或频率）。在本文考虑的静态情况下，数组是经典形式，但如果存在更新，Mo 算法将被扩展以有效地处理动态变化。

在此版本中，点更新（例如，修改给定的数组位置）与范围查询结合在一起。为了高效地管理更新，该算法采用了两种主要方法：

1. 离线更新：更新和查询都预先存储并作为操作一起处理。Mo 的分块分解用于对查询和更新进行排序。回滚机制允许在查询之间切换时撤销或重做更新。

程序

输出

5 6 
1 2 1 3 2 
Q 1 5 
U 3 4 
Q 1 5 
U 1 2 
Q 1 3 
Q 2 5
3
4
2
3   

说明

初始化

该算法和查询从输入数组和查询中读取。初始数组 arr[] 和用于处理的队列（tempArr[]）的值将相应填充。currentAnswer 维护范围查询的结果，freq[] 数组包含当前查询范围内元素的频率。

查询和更新

• 查询 (Q L R)：此操作将给出范围 [L, R] 内的不同元素数量。
• 更新 (U i x)：它将 x 替换为列表中索引 i 处的值。

这些操作在两个不同的数组中处理：

• queries[]：存储所有查询。
• updates[]：存储所有更新，包括更新索引、旧值和新值。

排序查询

使用基于 Mo 算法方法的自定义比较函数对查询进行排序。

我们将数组分成大小为 √N 的块。首先，按左端点 L 所在的块对查询进行排序，然后按右端点 R 排序。对于同一块中的两个查询，按其右端点排序以最大程度地减少重新计算。这种排序减少了冗余操作，并最大程度地减少了查询范围指针的移动。

处理更新

使用以下函数应用或回滚更新：

• applyUpdate(time)：在特定的“时间”（更新时间轴上的一个点）应用更新。
• rollbackUpdate(time)：它将数组元素恢复到其原始值，并通过撤销相关数组元素来执行更新回滚。

tempArr[] 和 freq[] 将进行调整以反映这些更改，无论使用哪个函数都会修改 tempArr[] 数组。

查询执行

当前范围的两个 L 和 R 指针正在被处理。算法为每个查询（更新指针）匹配范围 [L, R]，同时添加/删除必要的元素。results 数组存储每个查询的答案。

复杂度分析

时间复杂度

Mo 算法（带离线更新）的时间复杂度主要由三个因素决定：

1. 排序查询：它们根据左端点（'L'）和右端点（'R'）对查询进行排序。排序时间为 O(Q log Q)，其中 Q 是查询数量。
2. 处理查询：对于每个查询，算法会更改左指针和右指针（L、R）。每次调整需要 O(√N) 时间，其中 N 是数组的大小。这意味着我们处理 O(Q√N)。
3. 处理更新：对于任何更新，都会根据需要应用和回滚更新，这对于每个更新也需要 O(√N) 时间。对于 U 个更新，这需要 O(U√N)。

因此，总时间复杂度为 O((Q + U)√N)。

空间复杂度

存储需求决定了空间复杂度：

• 'arr[]' 和 'tempArr[]' 需要 O(N) 空间。
• 为了存储 'freq[]' 数组中元素的第一次出现，我们需要 O(N) 空间。
• 存储查询和更新所需的位数占 O(Q + U)。

因此，总空间复杂度为 O(N + Q + U)。

2. 在线更新：对于更新和范围查询，我们使用线段树或 Fenwick 树（二叉索引树）等数据结构来实时执行它们。

程序

输出

3 4
1 3 1
Q 1 5
U 2 4
Q 1 2
U 3 4
9
5   

说明

• 输入：输入以两个整数开始：数组大小 n 和操作数 q。之后，进行 q 次操作，每次操作是一个查询 (Q L R)，用于计算范围 [L, R] 的不同元素数量，或是一个更新 (U i x)，将索引 i 处的值更改为 x。
• 线段树：线段树可以高效地进行各种点更新和范围查询。更新部分数组并返回给定范围内不同元素的数量。
• Mo 算法：Mo 算法处理查询并对其进行排序，以最大程度地减少范围指针的移动和总时间复杂度。我们通过按左索引和右索引对查询进行排序，然后调整每个查询的当前范围以匹配它来做到这一点。
• 更新：每当发生点更新时，线段树就会更新，并且数组的相应部分会被修改。更新可能发生在范围查询之间，并且树保证这些范围查询仍然提供正确的结果。

该程序接受查询并为每次查询输出给定范围内不同元素的数量。在更新之后，会处理范围查询并打印结果。

复杂度分析

时间复杂度

这里的查询排序时间为 O(Q log Q)，其中 Q 是查询数量。每次查询时，我们都会更改范围，由于线段树，这需要 O(log N) 时间。执行所有查询的总成本为 O(Q log N)。更新操作包括更新线段树，也需要 O(log N) 时间进行更新。我们的更新总时间为 O(U log N)，其中 U 是更新次数。结果是，总时间复杂度为 O((Q+U)log N)。

空间复杂度

线段树和辅助数据结构决定了空间复杂度。线段树本身使用 O(N) 空间，查询、结果和辅助信息数组也使用 O(N) 空间。此问题的时空复杂度为 O(N + Q + U)。

Mo 算法（不带更新）

Mo 算法是一种用于在静态数组上进行多范围查询的快速方案。它最常用的应用是解决诸如查找给定范围的总和、最小值或最大值，或给定范围内不同元素的数量等问题。Mo 算法基于重新排序查询以最小化范围边界（指针 L 和 R）移动的想法。

它通过平方根分解来实现这一点。数组被分成大约 √N 大小的段，查询根据其左端点和右端点进行排序。Mo 算法通过以这种顺序处理查询来帮助减少冗余计算并加快计算速度。

程序

输出

5 3
1 2 1 3 2
1 3
2 5
1 5
2
3
3   

说明

输入

代码的第一部分获取输入值。第一行有两个值：数组大小 n 和查询数 q。接下来的 n 个值构成输入数组 arr[]，大小为 n。下一部分读取查询。每个查询包含两个整数 L 和 R，表示需要计算不同元素数量的范围。使用 Query 结构体向量来存储查询。

排序查询

Mo 算法旨在重新排序查询，从而最大限度地减少指针 L 和 R 的移动。

查询按 L/blockSize（左端点所在的块号）以及块内的 R（右端点）进行排序。对于块号为奇数的情况，为了进一步减少移动，查询按 R 降序排序。

添加和删除函数

• add()：当 R 增加（将范围向右扩展）时，调用此函数。如果这是第一次出现，它会增加不同元素的计数并增加该元素的频率。
• remove()：当我们在两侧收缩范围时（R 减小或 L 增大）会调用此函数。如果元素值小于 1，则会减少该元素的频率，当元素的频率达到零时，则减少不同元素的计数。

处理查询

• 对于每个查询，查询的范围会改变左指针和右指针（L 和 R）。
• 在 currentAnswer 中，我们存储当前范围内不同元素的数量，该数量在添加或删除元素时动态更新。
• 所有查询都被处理，并且答案按照原始查询出现的顺序输出。

复杂度分析

时间复杂度

1. 排序查询：（通过直接与数据结构接口，我们通过按左边界和右边界的顺序对查询进行排序，获得 O(Q log Q) 的复杂度，其中 Q 是查询数量。）Mo 算法的这种排序方式使得指针（左和右）在排序过程中移动最少。
2. 处理查询：对于每个查询，通过移动左指针和右指针来调整范围。每个查询在调整指针时需要 O(√N) 时间，其中 N 是数组的大小。对于 Q 个查询，处理所有查询的总时间复杂度为 O(Q√N)。

综合复杂度为 O((Q + N)√N)，其中 N 是数组的大小，Q 是查询数量。

空间复杂度

数组、频率数组和查询的存储决定了空间复杂度：

数组需要 O(N) 的空间复杂度。我们还需要 O(N) 的空间用于频率数组（用于计数元素）。存储查询需要 O(Q) 的空间。因此，此算法的空间复杂度为 O(N + Q)。