企业官网建设流程全解析

最近刷到一个挺有意思的题：《3756. 连接非零数字并乘以其数字和 II》，标签是“前缀和”。题目名字虽然长，核心其实很朴素：给你一个数字串，每次给一个区间，把区间里所有非零数字按原始顺序拼接成一个整数，再乘上这个整数的各位数字之和，快速返回答案。我第一次看到时觉得“这不就是模拟吗”，但多组查询加上大范围数据之后，单纯的模拟会超时到怀疑人生。把这道题吃透，你会顺带把前缀和里最容易被忽略的一条暗线——“带顺序信息的拼接型前缀”——彻底搞明白。

这篇文章适合两类人：一类是准备算法面试或竞赛的选手，想找一道题把前缀和、取模、区间合并练熟；另一类是刚接触数据结构的同学，想看看“一个前缀和数组不够用的时候，到底该怎么加维度”。我会先把这个题的数学模型拆开，再推导前缀和公式，给出 C++ 和 Java 的完整实现，最后聊聊我在调试过程中踩过的真坑。如果你自己动手写过，大概率会对第 4 节的内容会心一笑。

1. 先把这个题目翻译成人话

1.1 从题干到数学表达式的翻译

我习惯拿到题先不看解法，而是把所有条件变成自己能算的式子。题目的输入是一个数字串，比如1023405，我们要对某个区间[l, r]做三步操作：

1. 把区间内所有非零字符挑出来，保持相对顺序。比如1023405去掉零之后变成12345。
2. 计算这个新整数的数字和。注意这里的数字和是指拼接成的新整数各位相加，也就是1 + 2 + 3 + 4 + 5 = 15。
3. 让拼接后的整数乘以它的数字和，返回结果。如果结果很大，按题目要求取模。

有一个关键观察能直接省掉很多无效计算：拼接不会改变数字的“组成成分”。12345的数字和，本质上就是原串里所有非零数字的和。也就是说，数字和这一部分根本不需要知道拼接结果长什么样，它只跟“区间内非零数字的累加”有关系。

于是题目被拆成两个独立问题：

• 数字和：区间内所有非零数字的和，普通前缀和就能解决。
• 拼接值：区间内非零数字按顺序拼成的那个大整数，这个才是难点，因为它依赖“顺序”和“位置权重”。

1.2 为什么“数字和”不难，难的是“拼接值”

如果你写过字符串拼接相关的题，应该知道一个问题：1 + 2拼成12，和1 + 20拼成120是完全不同的。拼接的本质是“前面拼接好的数乘以 10 的某个幂次，再加上后面的数”。

举个例子，区间非零数字序列是[3, 0, 4, 5]（这里 0 被忽略），真正参与拼接的是3, 4, 5。那么：

拼接值 = 3 然后 3 * 10 + 4 = 34 然后 34 * 10 + 5 = 345

每一步都是new = old * 10 + d。如果我只给你一个区间，让你从头开始模拟，那和暴力的时间开销差不多。多组查询时，每个查询都要重新遍历区间，复杂度最坏是 O(nq)，n 是数字串长度，q 是查询次数，一旦两边都到 10^5，基本就跑不动了。

所以需要一种预处理结构，让任意区间的拼接值都能在 O(1) 或 O(log n) 内拿到。前缀和在这里最大的价值是：它能把“区间信息”变成两个“前缀信息”的差。问题是，拼接值并不是一个普通的可加量，不能简单相减，因为它里面藏着 10 的幂次。

1.3 暴力法的时间瓶颈与优化空间

很多初学者看到这道题的第一反应是：直接对每个查询循环一遍，遇到非零字符就x = x * 10 + d，同时累计数字和，最后相乘取模。确实，这个逻辑完全正确，而且对于小数据就是标准答案。

但当你把数字串长度拉到 10^5，查询数量也拉到 10^5，单次查询 O(区间长度)，总复杂度 O(nq)，最坏是 10^10 级别操作。即便 C++ 每秒能跑 10^9 次简单运算，也是五十多秒的量级，超时是板上钉钉的事。

优化方向有两个维度：

• 如果查询全是离线的，可以用前缀和把每次查询压到 O(1)；
• 如果存在单点修改，那就不能用静态前缀和了，得换线段树维护区间合并信息。

这篇文章会两条路都走一遍。尤其是线段树那条路，很多人以为只要会写pushUp就行，但实际上“区间合并”的规则才是最需要动脑子的地方。

2. 前缀和为什么能接住这道题

2.1 前缀和的两个基本维度：个数与幂次

要做区间拼接值查询，先看一个简单情形：已知preVal[i]表示数字串前 i 个字符中所有非零数字拼接成的整数，那么对于区间[l, r]，我们想知道的是“从 preVal[l-1] 之后，再接上区间内的非零数字，会变成什么”。

这个过程可以写成：

preVal[r] = preVal[l-1] * 10^(区间内非零数字个数) + 区间拼接值

所以“区间拼接值”是可以反推的：

区间拼接值 = preVal[r] - preVal[l-1] * 10^(preCnt[r] - preCnt[l-1])

也就是说，我至少要维护三个前缀数组：

1. preCnt[i]：前 i 个字符中非零数字的个数；
2. preVal[i]：前 i 个字符中非零数字拼接成的数值，需要取模；
3. pow10[i]：10^i 对模数取模的值，用来快速得到 10 的幂次。

有了这三个数组，任意区间的拼接值都能在 O(1) 时间内算出来。

2.2 连接值的区间合并公式推导

用数学语言把上面的思路写严谨一点。假设模数为 M。

定义：

preVal[i] = (preVal[i-1] * 10 + d_i) mod M (当 s[i] 非零时) preCnt[i] = preCnt[i-1] + 1 (当 s[i] 非零时)

其中d_i是第 i 个字符对应的数字。如果s[i]是零，则preVal[i] = preVal[i-1]，preCnt[i] = preCnt[i-1]。

对于区间[l, r]，设cnt = preCnt[r] - preCnt[l-1]，这个cnt是区间内非零数字个数。

由preVal[r]的构造过程可以写出：

preVal[r] = preVal[l-1] * 10^cnt + intervalValue

移项得到：

intervalValue = preVal[r] - preVal[l-1] * 10^cnt

在实际代码里，因为preVal是在模 M 意义下存储的，所以上式可能需要加一个 M 再取模，防止出现负数。

到这里，区间拼接值已经解决了。数字和部分更简单，因为拼接不改变数字和，所以再维护一个preDigitSum[i]，代表前 i 个字符中所有非零数字的和：

digitSum = preDigitSum[r] - preDigitSum[l-1]

最终答案就是：

answer = intervalValue * digitSum mod M

2.3 区间查询 O(1) 公式验证与边界

纸上推公式总觉得心里没底，我习惯拿一个很小的例子手动验证。

数字串取1023405，我们查区间[2, 6]，也就是0 2 3 4 0这一截，去掉零后应该是234。

手动算一下：

preVal 数组： preVal[0] = 0 preVal[1] = 1 preVal[2] = 1 // 字符 '0' 被忽略 preVal[3] = 12 // '1' + '2' preVal[4] = 123 // '1' '2' '3' preVal[5] = 1234 preVal[6] = 1234 // '0' 被忽略 preCnt 数组： preCnt[1] = 1 preCnt[2] = 1 preCnt[3] = 2 preCnt[4] = 3 preCnt[5] = 4 preCnt[6] = 4

查询[2, 6]：

cnt = preCnt[6] - preCnt[1] = 4 - 1 = 3 intervalValue = preVal[6] - preVal[1] * 10^3 = 1234 - 1 * 1000 = 234

结果正好是234。这个例子虽然简单，但能检验公式中“左边界用 l-1”这个细节对不对。如果写错成l，得到的就是preVal[6] - preVal[2] * 10^cnt，完全不是一回事。

再验证一个边界：全零区间，比如s = "1001"，查询[2, 3]。preVal[3]应该等于preVal[1]，因为'0'和'1'中间两个零被忽略。代入公式后intervalValue = 0，数字和也是 0，乘积为 0。这说明即使区间里没有非零数字，公式也能正确处理，不会出现pow10[0]的问题，因为10^0 = 1。

2.4 数字和与拼接值的区别：一个经典误区

我把这个题发给朋友看，他的第一版代码只维护了“数字和”和“非零数字个数”，然后用(digitSum * 10^cnt?)去拼，明显混淆了概念。

数字和是一个“加法维度”，它只关心每个数字本身是多少。而拼接值是一个“带权的加法维度”，越靠前的数字权重越大，具体权重是 10 的若干次方。

举个例子：区间内非零数字是[9, 1]，拼接值是91，数字和是10，正确答案是910。如果只维护数字和，你会把91误写成9 * 10 + 1倒没错，但如果套路化地以为“只要记录总和，拼接时再乘幂”，遇到[1, 9]和[9, 1]这种顺序不同的区间，结果就错得离谱。

所以记住：数字和可以相减，拼接值不能直接相减。这是整道题最容易被坑的地方。

3. 代码落地：C++和Java两条腿走路

3.1 先写一个暴力版作为对拍基准

在做优化版之前，我强烈建议写一个完全暴力的版本，哪怕复杂度是 O(nq)。它的作用不是提交，而是用来对拍，验证优化算法的正确性。

C++ 的暴力版可以写成这样：

long long brute(const string& s, int l, int r, long long MOD) { long long x = 0, digitSum = 0; for (int i = l; i <= r; ++i) { if (s[i] != '0') { x = (x * 10 + (s[i] - '0')) % MOD; digitSum += (s[i] - '0'); } } return x * (digitSum % MOD) % MOD; }

这段代码读起来就像题目描述的自然翻译，很容易确保逻辑正确。后面优化版写完，构造随机小数据，两边对拍，如果输出完全一致，基本可以放心。

3.2 前缀和优化版：C++实现的关键细节

下面是完整的前缀和优化代码，我给每一段都加了注释：

#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007LL; int main() { string s; cin >> s; int n = s.size(); vector<long long> preCnt(n + 1, 0), preVal(n + 1, 0), preDigitSum(n + 1, 0), pow10(n + 1, 1); for (int i = 1; i <= n; ++i) { pow10[i] = pow10[i - 1] * 10 % MOD; int d = s[i - 1] - '0'; preCnt[i] = preCnt[i - 1]; preVal[i] = preVal[i - 1]; preDigitSum[i] = preDigitSum[i - 1]; if (d != 0) { preCnt[i]++; preVal[i] = (preVal[i] * 10 + d) % MOD; preDigitSum[i] += d; } } auto query = [&](int l, int r) -> long long { long long cnt = preCnt[r] - preCnt[l - 1]; long long leftPart = preVal[l - 1]; long long intervalValue = (preVal[r] - leftPart * pow10[cnt] % MOD + MOD) % MOD; long long digitSum = preDigitSum[r] - preDigitSum[l - 1]; return intervalValue * (digitSum % MOD) % MOD; }; int q; cin >> q; while (q--) { int l, r; cin >> l >> r; cout << query(l, r) << '\n'; } return 0; }

几个关键点：

• preVal的更新是“乘 10 加 d”，因为每遇到一个非零数字，之前拼接好的所有数字都要往左挪一位。
• pow10[cnt]这里的cnt是区间内非零数字个数，它决定了leftPart需要被放大多少倍。
• intervalValue的表达式里加了MOD再取模，是为了处理减法可能带来的负数。这是取模运算里最常见的坑，第 4 节会展开说。

3.3 Java实现与字符串分割的坑

Java 版本在核心思路上完全一样，但要注意输入输出效率。这里给一个能跑的模板：

import java.io.*; import java.util.*; public class Main { static final long MOD = 1000000007L; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s = br.readLine(); int n = s.length(); long[] preCnt = new long[n + 1]; long[] preVal = new long[n + 1]; long[] preDigitSum = new long[n + 1]; long[] pow10 = new long[n + 1]; pow10[0] = 1; for (int i = 1; i <= n; i++) { pow10[i] = pow10[i - 1] * 10 % MOD; int d = s.charAt(i - 1) - '0'; preCnt[i] = preCnt[i - 1]; preVal[i] = preVal[i - 1]; preDigitSum[i] = preDigitSum[i - 1]; if (d != 0) { preCnt[i]++; preVal[i] = (preVal[i] * 10 + d) % MOD; preDigitSum[i] += d; } } int q = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); while (q-- > 0) { StringTokenizer st = new StringTokenizer(br.readLine()); int l = Integer.parseInt(st.nextToken()); int r = Integer.parseInt(st.nextToken()); long cnt = preCnt[r] - preCnt[l - 1]; long leftPart = preVal[l - 1]; long intervalValue = (preVal[r] - leftPart * pow10[(int) cnt] % MOD + MOD) % MOD; long digitSum = preDigitSum[r] - preDigitSum[l - 1]; sb.append(intervalValue * (digitSum % MOD) % MOD).append('\n'); } System.out.print(sb); } }

如果你在 OJ 上提交这类题，会发现一个隐蔽的坑：输入的数字串可能特别长，甚至被换行符截断。有些题的输入描述是“一个整数”，但数据里可能用readLine只能读到一部分。这种情况我处理的方式是循环读，拼成完整的字符串，直到满足长度要求。

还有一个 Java 独有的性能点：System.out.println在循环里频繁调用会非常慢。务必用StringBuilder攒答案，最后一次性输出。别小看这个习惯，几次测试下来，同样的数据能差出一两倍耗时。

3.4 扩展到单点修改：线段树合并的思路

静态前缀和的好处是 O(1) 查询，缺陷是一旦某个位置的数字被修改，所有后续的preVal都要重新计算。如果题目改成“支持把某个位置的字符改掉”，静态前缀和就失效了。

这时可以换线段树。线段树的每个节点只要存三个信息：

len = 区间内非零数字个数 val = 区间内非零数字拼接值 sum = 区间内非零数字和

合并两个左右子节点时，规则非常自然：

len = left.len + right.len sum = left.sum + right.sum val = (left.val * 10^right.len + right.val) % MOD

这个合并规则和前缀和公式一脉相承：左半边的值要被右半边非零数字个数放大 10 的幂次，再接上右半边的值。单点修改时只需要更新叶子节点，然后一路向上pushUp。区间查询时把覆盖的节点合并起来，最后拿sum和val相乘。

写线段树时最需要注意的是right.len不是右区间的总长度，而是右区间里非零数字的个数。很多人习惯性写成区间长度，结果拼接出的数字完全不对。排查的时候可以打印每个节点的len和val，对照暴力结果检查。

3.5 为什么这里用不了树状数组

热词里有人提到“树状数组维护长度 n = 16 的序列。查询前缀和 sum(11) 与单点修改 add(3, x) 分别”。这句话本身没有错，但它描述的是“加法型前缀和”，也就是sum(11)直接累加前 11 个元素。

树状数组的精髓在于“操作可逆”：普通加法区间查询用sum(r) - sum(l-1)，因为加法的逆运算是减法。但线段树节点的合并操作是“左值乘幂加右值”，你没法通过某个前缀的逆操作直接得到任意区间的拼接值。除非你维护的是严格的模意义下的可逆变换，并且能求出逆元，否则树状数组无法胜任这种带顺序的拼接合并。

所以结论很明确：

• 如果只维护数字和，树状数组完全可以，因为digitSum[r] - digitSum[l-1]是加法的逆运算；
• 如果维护拼接值，老老实实上前缀和（静态）或线段树（动态）。

很多人一开始觉得线段树麻烦，想用树状数组偷懒，最后反而浪费更多时间。工具选型的原则是：先看操作是否满足“可逆性”，再决定数据结构。

4. 现场排查：我踩过的坑

4.1 取模运算中的负数修正

写第一版前缀和时，我用的是：

long long intervalValue = (preVal[r] - preVal[l - 1] * pow10[cnt]) % MOD;

结果随机数据对拍时，时不时出现负数答案。原因很简单：C++ 的%运算结果符号和被除数一致，当preVal[r]小于preVal[l-1] * pow10[cnt]时，可能得到一个负数。

修正方法：

long long intervalValue = (preVal[r] - preVal[l - 1] * pow10[cnt] % MOD + MOD) % MOD;

先对乘法部分取模，再整体加一个 MOD，最后取模。这个+MOD能保证中间结果非负。Java 的%同样是符号相关，也要这么处理。

踩过这个坑之后，我写所有涉及取模的减法时都会形成肌肉记忆：先% MOD，再+ MOD，再% MOD。

4.2 全零区间与非零数字为空

第二个容易漏的地方是区间内没有非零数字。比如s = "0000"，查[1, 4]。

按公式算，cnt = 0，preVal[4] = 0，intervalValue = 0，digitSum = 0，结果 0，逻辑没问题。但如果你的代码里把“拼接结果为空”当成错误情况，比如直接throw或者返回 -1，那就错了。题目要求的结果就是 0，因为空数字适配到整数是 0，数字和是 0，乘积自然是 0。

还有一种边界：区间里只有一个非零数字，比如s = "5"，查[1,1]。cnt = 1，intervalValue = 5，digitSum = 5，结果 25，符合“拼接成 5，数字和 5，乘积 25”的预期。

4.3 前缀数组下标是 1-based 还是 0-based

写代码时最容易因为下标错位导致差一错误。我的建议是统一用 1-based 的前缀数组，字符串本身用 0-based 访问。这样查询[l, r]时统一是preVal[r] - preVal[l-1]，不容易混。

如果你喜欢 0-based，那查询时就要想清楚是preVal[r] - preVal[l-1]还是preVal[r+1] - preVal[l]。我见过太多人不小心把边界写反，最后对拍出的结果莫名其妙地差一位。

解决这个问题的办法特别笨但特别有效：在代码注释里写一行样例，比如s = "1023405"，标出每个下标对应的preVal值。调试时拿着这个表对照，一眼就能看出哪一步多加了一个数字。

4.4 调试法宝：双模校验与随机对拍

取模运算有个隐性风险：两个不同的数可能对 MOD 同余，导致答案碰撞。比如 A 和 B 在模数下相等，但真实答案不同。为了防止这种情况，建议在本地调试时用两个不同的质数模数，比如MOD1 = 1000000007和MOD2 = 1000000009，分别跑一遍，如果两个结果都一致，那碰撞概率基本可以忽略。

随机对拍时，我习惯写一个 Python 脚本生成随机数字串，长度从 1 到 20，随机生成几十组区间查询，让 C++ 暴力版和优化版分别跑，然后 diff 输出。一旦发现不一致，缩小数据范围，手动算一遍，基本都能定位到是取模负号还是下标问题。

4.5 顺序错位：从圆心标定x/y到算法里的前后顺序

你可能觉得“顺序”这个概念太简单，不值得单独说。但在实际项目里，顺序错位的代价远比你想象的大。

我记得在生产系统里做喷丝板模型标定时，遇到过圆心标定的 x 和 y 坐标，输出的数字大小顺序位置不一致的问题。表面上是坐标顺序反了，实际上是因为某个中间环节把 x/y 当成一个无序集合处理，丢失了轴的顺序。这类问题像极了算法里把拼接方向搞反：左半部分明明应该乘 10 的幂再拼接右半部分，结果你把左右顺序对调，出来的数字完全不符合原字符串。

所以我总结了一条经验：凡是涉及顺序敏感的数据变换，第一步永远是定义清楚“顺序从哪来、到哪去”。在本题里，顺序来自原始字符串的索引顺序；在图像标定里，顺序来自坐标轴的定义。顺序一旦出错，后面的所有计算都白搭。

5. 这个套路还能怎么玩

5.1 把“拼接”换成“哈希组合”

这道题推导出的核心公式：

intervalValue = preVal[r] - preVal[l-1] * 10^cnt

和字符串哈希的区间查询公式长得非常像。字符串哈希里也维护preHash[i]，然后查[l, r]时做hash(r) - hash(l-1) * P^(r-l+1)。本质上都是“前缀信息 + 幂次修正”的思路。

所以如果你把题目里的“非零数字拼接”理解成“某种基数下的编码”，那这道题的解法可以迁移到很多场景：字符子串哈希、多项式前缀、进制转换问题等。可见前缀和不是一个死的模板，而是一套“维护可平移、可还原信息”的通用思想。

5.2 把“数字和”换成“平方和”

如果题目改成“拼接后的整数乘以数字的平方和”，维护起来会更复杂。平方和信息是sum(d_i^2)，但它和拼接值没直接关系，所以额外维护一个前缀平方和即可。

但如果题目改成“拼接后的整数的平方”，那就需要维护的不只是val，还要维护val^2，因为：

newVal = oldVal * 10 + d newVal^2 = oldVal^2 * 100 + oldVal * 20 * d + d^2

需要同时维护val和val^2两个维度。这说明遇到“乘以其数字和”这个变体时，题目已经算是温和的了，因为它只需要一个前缀和就能解决。

5.3 分块与莫队：当查询变成在线动态？

如果题目既不支持前缀和，又不想写线段树，还有一种中等复杂度的方案是分块。把数字串分成若干块，每块维护三个信息，查询时整块直接取合并结果，零散部分暴力拼接。复杂度大约 O(sqrt(n)) 级别，代码量比线段树小，而且对“区间查询”很友好。

莫队算法也能用在纯查询场景，利用指针移动维护当前区间的拼接状态，但需要注意拼接操作的顺序性，移动左端点时需要能“从左边去掉一个数字”。去掉带权数字的操作不是简单减法，需要预处理 10 的逆元。这又是一个能延伸出去的知识点，这里不展开。

写在最后

我自己的体会是，前缀和这个知识点特别容易让人产生“我懂了”的错觉，直到遇到这种需要维护带权拼接信息的题，才发现原来对“前缀数组到底存了什么”理解得不够深。数字和可以减，拼接值却要乘幂修正，这两种操作的区别，才是这道题真正想考的东西。

如果你也想练手，建议按这个顺序来：先写暴力版，再写前缀和版，最后尝试线段树版。每个版本都用一个随机生成器对拍一遍，确保输出一致。这样下来，你对“区间合并信息”会有一种很踏实的手感，以后再遇到类似题目，第一反应就不是套模板了。