企业官网建设流程全解析

如果你在 LeetCode 上搜索 1622，标题叫「奇妙序列 Fancy Sequence」。我第一次在周赛里碰到它的时候，第一反应是：这不就是个数组模拟题？append 往尾部塞，addAll 全部加一遍，multAll 全部乘一遍，getIndex 直接下标取值，总共四行代码的事。直到提交之后被一个 10 万次操作的用例教做人，我才开始认真琢磨。这道题表面上是模拟题，底子里却是一道数学题，考的是取模运算的逆运算——模逆元，以及把全局操作增量记账的懒标记思想。今天这篇文章，我想从暴力开始，一步步把这道题的完整思路、数学推导、代码实现和踩过的坑都摊开讲一遍，也顺便说说这个思想在面试里能怎么聊。

1. 题目拆解：一场面向全体成员的操作风暴

1.1 暴力模拟的复杂度危机

先看题目要求维护一个序列，支持四种操作：

• append(val)：在序列末尾追加一个数字
• addAll(inc)：当前序列所有数字整体加inc
• multAll(m)：当前序列所有数字整体乘m
• getIndex(idx)：查询第idx个位置的值，若越界返回 -1，否则返回对1e9+7取模后的结果

最直觉的写法就是直接开一个数组或者扩容的列表，每次addAll就for循环全部加一遍，每次multAll就for循环全部乘一遍，查询的时候直接下标返回。这个暴力实现在小数据量下完全没问题，但题目调用次数上限是 10 万次，每次操作如果都遍历整个数组，最坏情况下总复杂度是 O(nq)，其中 n 是数组长度，q 是操作次数，极端数据会让数组长度和操作次数都逼近 10 万，算一下就是 10^10 次运算量级，任何语言都会超时。

这个复杂度危机的本质在于：addAll和multAll作用的对象是「整个序列」，而查询只是单点。如果每一次整体操作都真的去更新每一个元素，相当于把一个 O(1) 能表达的变化，强行拆成了 O(n) 次独立赋值，信息被重复写进了 n 个位置。我们真正需要的不是让每个元素都「亲眼看到」更新的那一刻，而是让每个元素在「被查询的那一刻」能够算出当前值。这个认知转变，是这道题的破局点。

1.2 关键直觉：给整个数组挂一个“全局账本”

既然整体操作是作用于全部元素的，那我能不能不真的去改数组，而是把「当前全体元素都被加了多少、乘了多少」记在几个全局变量上？就像老板给全公司所有人涨薪 500 块，他不会真的逐个改每个人的工资档案，而是在薪酬系统里挂一条「所有员工 +500」的全局规则。每个人的基础工资不动，等到真正发工资、算月薪的时候，再把这个全局规则套到个人基础数字上。

放到这道题里，我们把每个位置存的基础值看作「不含任何全局操作影响的基准值」，然后用两个全局变量mul和add记录当前套用在所有基准值上的一层线性变换：真实值 =基准值 * mul + add。这样一来，addAll(inc)只需要更新add += inc，multAll(m)只需要更新mul *= m且add *= m，都是 O(1) 操作。真正剩下的难题是：append新元素时，新来的值本身还没被全局变换作用过，我该往数组里存什么，才能让它和之前的老元素共用同一套mul / add变换？这就把问题从数据结构推向了数学。

2. 数学地基：模逆元与延迟标记推导

2.1 为什么 1e9+7 是个难得的“好模数”

题目要求所有查询结果对1e9+7取模。这个数字看起来只是随手选的一个大质数，其实大有讲究。

第一，模数足够大，常规运算中间结果乘起来不太容易溢出 64 位整数。1e9+7平方大约是1e18，在 Java 的long范围内，可以直接乘完再取模。

第二，最关键的一点：1e9+7是质数。这意味着在模1e9+7的世界里，任何一个 1 到1e9+6之间的整数，都和模数互质。而只要两个数互质，这个数就在模运算下有「逆元」。题目限定1 <= m <= 1e9，注意这个上界小于1e9+7，所以每一个乘法操作因子和模数天然互质，逆元一定存在。要是模数是个合数，某些因子可能没有逆元，整个方案就直接卡死。理解这层关系，你就明白了为什么出题人偏偏挑这个数字。

第三，因为模数是质数，求逆元有现成公式：费马小定理。若a与质数MOD互质，则a^(MOD-1) ≡ 1 (mod MOD)，两边同时除以a，得到a^(MOD-2) ≡ a^(-1) (mod MOD)。所以求逆元就等价于做一次快速幂，代码好写，也不容易出错。

2.2 延迟标记的推导过程

我们现在定义全局变换为：

真实值 = 基准值 × mul + add (全部对 MOD 取模)

这个变换是「先乘后加」的形式。初始状态mul = 1，add = 0，此时真实值就是基准值本身。

处理append(val)的时候，新元素是一个「还没被全局变换作用过」的独立值。但我希望它套用全局变换之后得到val，也就是说，我需要找一个基准值stored，使得：

stored × mul + add ≡ val (mod MOD)

移项得到：

stored ≡ (val - add) × mul^(-1) (mod MOD)

这个式子就是整个算法的核心。它告诉我们，新元素存入数组的并不是它表面的val，而是一个「反向还原」后的值。因为当前全局账本已经积累了过去的很多次addAll和multAll，一个新加入的元素不能平白无故也享受老元素已经吃过的加减乘，所以必须先把val还原成没有全局操作历史的裸值。存储完成后，这个新元素就和所有老元素一样，每次查询时统一套用当前的mul / add就能算出来。

为什么是减法在前、乘法逆元在后，顺序不能乱？因为先乘后加的变换里，想还原x，就要先消去加法，再消除乘法。如果你先除乘法再减加法，算出来的基准值套回全局变换时会对不上账。这一步我当初刷题时真就被顺序坑过一次，后面踩坑章节会再展开。

2.3 乘法因子与加法因子的联动更新

全局变换需要支持两种整体操作，它们的更新方式不是对称的，很多人容易在这里出错。

addAll(inc)给所有当前元素加一个数。对全局变换而言，相当于在现有结果外再套一层加法：

新变换(x) = (x × mul + add) + inc = x × mul + (add + inc)

所以只需要add += inc，mul不动。这个比较好理解。

multAll(m)就微妙一些。整体乘m，等价于在现有变换外再套一层乘法：

新变换(x) = m × (x × mul + add) = x × (mul × m) + add × m

注意这里add也必须跟着乘m。因为全局变换是「先乘后加」，外层的乘法会把之前累计的加法也放大m倍。如果只更新mul而忘记更新add，等于把「每个元素都乘 m」错写成了「每个元素都乘 m，但之前加的偏置没乘」，结果必然错误。

把这两个更新规则用代码表示就是：

void addAll(int inc) { add = (add + inc) % MOD; } void multAll(int m) { mul = mul * m % MOD; add = add * m % MOD; }

到这里，所有操作都变成了 O(1) 级别的账本更新，也只有append需要一次快速幂求逆元。

3. 从公式到代码：Java 实现全解析

3.1 数据结构设计

类的成员变量需要三样东西：

• List<Long> values：保存每个元素的基准值（已还原不含全局变换的裸值）
• long mul：全局乘法因子，初始为 1
• long add：全局加法因子，初始为 0

为什么用List<Long>而不是数组？因为append需要动态扩容，且getIndex是随机访问，ArrayList的底层数组访问是 O(1)，完全匹配需求。用long是为了防溢出，虽然取模后所有值都在[0, MOD-1]范围内，但乘法运算的中间结果可能达到 10^18 量级，int会爆。

还有一个细节：mul和add始终维护在[0, MOD-1]区间内，每次更新后立即取模。这样保证后续运算的中间结果不会无限膨胀。

3.2 快速幂求逆元

求逆元用的是费马小定理，本质上是一次模意义下的幂运算。快速幂是常规操作：

private long modPow(long a, long n) { long res = 1; while (n > 0) { if ((n & 1) == 1) { res = res * a % MOD; } a = a * a % MOD; n >>= 1; } return res; } private long modInv(long a) { return modPow(a, MOD - 2); }

MOD - 2 = 1000000005，二进制大约 30 位，所以一次求逆元只做约 30 次乘法循环。10 万次操作里最坏情况每次append都求一次逆元，也才几百万次乘法，完全在可接受范围内。

3.3 四个操作一步步实现

append(int val)的代码是：

public void append(int val) { long invMul = modInv(mul); long stored = (val - add + MOD) % MOD; stored = stored * invMul % MOD; values.add(stored); }

这里(val - add + MOD) % MOD是为了处理负数取模。因为val和add都是取了模的数，val - add可能为负，Java 的%对负数结果仍是负数，加上一个MOD再取模就能保证结果落在[0, MOD-1]。

addAll(int inc)：

public void addAll(int inc) { add = (add + inc) % MOD; }

multAll(int m)：

public void multAll(int m) { mul = mul * m % MOD; add = add * m % MOD; }

getIndex(int idx)：

public int getIndex(int idx) { if (idx >= values.size()) { return -1; } long stored = values.get(idx); long real = (stored * mul % MOD + add) % MOD; return (int) real; }

越界返回 -1 是题目的明确要求，注意不是返回对MOD取模后的结果，就是字面意义上的 -1。

3.4 完整可运行代码

把上面几段拼起来，就是完整的 Java 解法：

class Fancy { private static final long MOD = 1_000_000_007L; private List<Long> values = new ArrayList<>(); private long mul = 1; private long add = 0; private long modPow(long a, long n) { long res = 1; while (n > 0) { if ((n & 1) == 1) { res = res * a % MOD; } a = a * a % MOD; n >>= 1; } return res; } private long modInv(long a) { return modPow(a, MOD - 2); } public void append(int val) { long stored = (val - add + MOD) % MOD; stored = stored * modInv(mul) % MOD; values.add(stored); } public void addAll(int inc) { add = (add + inc) % MOD; } public void multAll(int m) { mul = mul * m % MOD; add = add * m % MOD; } public int getIndex(int idx) { if (idx >= values.size()) { return -1; } long real = (values.get(idx) * mul % MOD + add) % MOD; return (int) real; } }

如果你用 Python 刷题，写法几乎一样，唯一区别是 Python 的%对负数结果天然非负，负数取模不需要手动加MOD：

MOD = 10**9 + 7 class Fancy: def __init__(self): self.vals = [] self.mul = 1 self.add = 0 def _pow(self, a, n): res = 1 while n: if n & 1: res = res * a % MOD a = a * a % MOD n >>= 1 return res def append(self, val: int) -> None: inv = self._pow(self.mul, MOD - 2) stored = (val - self.add) % MOD * inv % MOD self.vals.append(stored) def addAll(self, inc: int) -> None: self.add = (self.add + inc) % MOD def multAll(self, m: int) -> None: self.mul = self.mul * m % MOD self.add = self.add * m % MOD def getIndex(self, idx: int) -> int: if idx >= len(self.vals): return -1 return (self.vals[idx] * self.mul + self.add) % MOD

4. 实测验证与避坑指南

4.1 用一个可手算的用例检验正确性

光看懂代码不算完，必须亲手推一组数据让每一步都对上账。我们构造一个短小的操作序列：

1. append(5)：此时mul=1, add=0，stored = (5-0)×1 = 5，数组为[5]
2. addAll(3)：add = 3，所有现有元素的真实值变为5×1 + 3 = 8
3. append(2)：当前mul=1, add=3，要存的值需满足stored×1 + 3 = 2，于是stored = (2-3)×1 ≡ MOD-1，数组变成[5, MOD-1]
4. multAll(2)：mul = 1×2 = 2，add = 3×2 = 6
5. getIndex(0)：5×2 + 6 = 16

来验证一下真实过程：元素 5 先被addAll(3)变成 8，再被multAll(2)变成 16，完全一致。

6. getIndex(1)：(MOD-1)×2 + 6 ≡ -2 + 6 = 4

这里要特别注意：元素 2 是在addAll(3)之后才加入的，它没赶上 +3 这趟车，只经历了后面的multAll(2)，所以真实过程是2 × 2 = 4。如果一开始误以为所有元素都能享受历史操作，就会在这里算出 10 来。stored的「逆向还原」正是为了把这个时间差精确地消掉。

再多加一个操作验证：append(10)之后，当前mul=2, add=6，stored = (10-6) × inv(2) = 4 × 500000004 ≡ 2（因为2 × 500000004 ≡ 1 mod MOD），所以新元素基准值是 2。接着multAll(3)，mul=6, add=18，再查getIndex(2)得到2×6+18=30，真实过程中 10 直接乘 3 等于 30，正确。到这一步，整个机制已经闭环了。

4.2 高频错误：懒标记更新顺序写反

最容易错的点就是multAll时忘了同步更新add。举一个反例：当前add=3, mul=1，数组里有一个元素基准值为 5，真实值是 8。现在执行multAll(2)，如果只把mul改成 2，add仍是 3，查询时会算出5×2+3=13，但正确结果应该是8×2=16。差在哪？差在那笔 +3 的账没有被乘 2。因为整体乘法的语义是「对所有当前元素乘 m」，之前加上的 3 作为元素值的一部分，也必须跟着翻倍。所以正确写法永远是mul *= m与add *= m同时发生。

另一个容易搞混的点是append时减法和乘法的顺序。求基准值的公式是stored = (val - add) / mul，代码里一定要先减add再乘逆元inv(mul)。如果你先乘逆元再减add，左边右边就不等价了。这里没有太多的技巧可言，每次写之前心里默念三遍：还原的时候，先解加法，再解乘法。

4.3 高频错误：负数取模与溢出

Java 的%运算结果是带符号的，-3 % 1000000007 = -3，不是数学上习惯的余数。所以(val - add)这一步必须显式处理负数。我的习惯是写(val - add + MOD) % MOD，因为val - add的下界大于-MOD，加一次MOD就足够让结果非负。如果你拿不准，更保险的万能写法是((val - add) % MOD + MOD) % MOD，但没必要多一次取模。

溢出问题主要出在mul * m、add * m、stored * mul这些乘法上。以mul为例，它始终小于MOD，m最大 10 亿，乘积不超过10^18，还在 Javalong的范围内，所以大胆用long做中间运算，每步乘完立刻% MOD。我见过有人贪图方便把它们声明成int，结果大用例直接WA或者出现奇怪负数，排查半天才发现是溢出。

还有个隐藏的「溢出」陷阱是List<Long>的自动装箱。每次append都会把一个long装成Long对象，10 万次操作的内存开销完全可接受，但如果强迫症发作想优化，也可以预先分配一个大数组加一个指针来模拟。实测下来ArrayList在本题数据规模下没有任何性能问题。

4.4 一个额外的性能优化

标准写法里每次append都要调用一次modPow(mul, MOD-2)。实测 10 万次调用里全是append的话，大概要多做 300 万次模乘，依然很快，不是瓶颈。如果你想追求常数上的极致，可以额外维护一个mulInv表示当前mul的逆元：

• append时直接stored = (val - add + MOD) % MOD * mulInv % MOD，O(1) 完成
• multAll时除了更新mul和add，还要把mulInv也乘上m的逆元：mulInv = mulInv * modInv(m) % MOD

这样做的好处是append和getIndex都变成纯 O(1)，逆元计算被挪到了multAll里。两种写法总体复杂度一样，主要看你更需要哪个操作更快。对于刷题来说，标准写法更简洁清晰，面试沟通也更顺畅；对于追求极限常数或实际项目里的类似需求，第二种写法更工程化。我在 LeetCode 提交区看了一圈，大部分 high-performance 解法用的都是带mulInv的版本。

5. 举一反三：懒标记思想的辐射范围

5.1 从这道题看线段树的 Lazy Propagation

这道题的「全局账本」思想，本质上是数据结构里非常经典的一个技巧：懒标记（Lazy Propagation）。线段树处理区间加、区间乘、区间赋值这类操作时，不会每次更新都递归到叶子节点把每个值改一遍，而是在代表整个区间的节点上挂一个标记，记录「这个区间内的所有元素都需要加一个数、乘一个数」，等到真正要查询或下推时才把标记合并、传播到子节点。

LeetCode 1622 相当于是线段树懒标记的一个极简模型：因为操作永远作用于整个序列，所以不需要树形结构，两个全局变量就够用；因为查询永远单点，所以也不需要区间合并。你把这题的mul和add想成是根节点上的两个懒标记，把values里的每个基准值想成叶子节点上的裸值，整个模型就和 P3373 这类经典线段树题对上了。

如果你接下来准备刷线段树，强烈建议先彻底吃透这题再上树。因为线段树懒标记的难点并不在树结构本身，而在于「标记之间如何合并」：先加后乘、先乘后加、赋值和其他操作的优先级，这些规则和本体的mul / add联动更新是同构的。先把二维的账本弄明白，树上的三维账本只是多了一个「沿树路径下推」的动作。

5.2 如果题目换个限定，算法会崩吗？

一个值得追问的问题是：为什么我们敢肯定mul永远有逆元？因为题目只有m <= 1e9 < MOD，并且MOD是质数。任意两个[1, MOD-1]范围内的数相乘，模MOD不可能为 0，所以mul永远不会归零。

如果题目放开限制，允许m = MOD甚至m是MOD的倍数，这个方案就需要打补丁。因为一旦mul变成 0，全局变换退化成一个常数函数，append时想求基准值就会出现「除以 0」的情况。此时可以额外维护一个状态表示「全局乘法因子是否为 0」，分情况讨论：

• 若mul != 0，维持原逻辑
• 若mul == 0，那么所有元素的真实值恒等于add，此时append(val)若val == add可以任存一个值（比如 0），否则无法构造基准值，需要另一种标记

面试时能主动聊出这层边界，比单纯背题要加分很多。

另一个方向是如果操作多了「区间赋值」怎么办。这时基准值的还原就需要记录原来的变换类型，或者为每个元素维护一个独立的「版本号」。其实更通用的做法是让每个元素存储它加入时的全局账本快照，查询时用当前账本减去快照账本来计算差异，但要注意减法在乘法和加法组合下不能简单相减，需要维护一个「变换函数」并支持逆变换。这些都是进阶话题，能看懂多少算多少。

5.3 面试现场怎么讲这道题

刷题是一回事，面试把思路讲清楚是另一回事。如果面试官抛出这道题，我建议按照下面的节奏来：

先给暴力解法，坦诚地说出它的复杂度问题：整体操作 O(n)，查询 O(1)，最坏 O(nq)。然后抛出核心矛盾：整体操作太多，查询太少，能不能把整体操作压缩成 O(1)？引出全局账本mul / add。

接着讲addAll和multAll如何更新，重点解释为什么multAll要连add一起乘。讲到append时，自然引出「逆向还原」的需求，用一个简单的例子说明：已经全体加过 3 之后再追加一个 2，这个 2 不能享受 +3 的历史待遇，所以它存的基准值要能让当前变换还原回 2。推导出stored = (val - add) / mul。

当你说到「除以 mul」时，面试官大概率会追问：模运算里怎么做除法？这就是展示数学功底的时刻：模数是质数，费马小定理，逆元等于a^(MOD-2)，快速幂求解。再补一句本题数据范围天然保证mul非零且逆元存在，把边界条件也照顾到。

最后总结复杂度：单次操作最坏 O(log MOD)，空间 O(q)。如果面试官再问能不能优化，抛出上面说的mulInv优化思路。整条线讲下来，逻辑闭环，别人一听就知道这题是真的被你想透了。

我个人刷这道题最大的收获，是养成了一种习惯：遇到「整体操作 + 单点查询」的结构，先别急着写循环，想一想有没有办法把整体操作「记账」下来，需要时再统一结算。这个思路在区间更新、延迟渲染、批量任务调度里都很好用。最后再分享一个小技巧：写这类带全局因子的题，最好先在手边留一段模拟暴力的参考代码，随机生成小规模操作序列并对比两种实现的结果。我就是靠这个方法，在五分钟内抓出了自己multAll忘记同步add的那个 bug。算法题里，「推公式」和「验账」从来都不该分开。