最近刷到一个挺有意思的题《3756. 连接非零数字并乘以其数字和 II》标签是“前缀和”。题目名字虽然长核心其实很朴素给你一个数字串每次给一个区间把区间里所有非零数字按原始顺序拼接成一个整数再乘上这个整数的各位数字之和快速返回答案。我第一次看到时觉得“这不就是模拟吗”但多组查询加上大范围数据之后单纯的模拟会超时到怀疑人生。把这道题吃透你会顺带把前缀和里最容易被忽略的一条暗线——“带顺序信息的拼接型前缀”——彻底搞明白。这篇文章适合两类人一类是准备算法面试或竞赛的选手想找一道题把前缀和、取模、区间合并练熟另一类是刚接触数据结构的同学想看看“一个前缀和数组不够用的时候到底该怎么加维度”。我会先把这个题的数学模型拆开再推导前缀和公式给出 C 和 Java 的完整实现最后聊聊我在调试过程中踩过的真坑。如果你自己动手写过大概率会对第 4 节的内容会心一笑。1. 先把这个题目翻译成人话1.1 从题干到数学表达式的翻译我习惯拿到题先不看解法而是把所有条件变成自己能算的式子。题目的输入是一个数字串比如1023405我们要对某个区间[l, r]做三步操作把区间内所有非零字符挑出来保持相对顺序。比如1023405去掉零之后变成12345。计算这个新整数的数字和。注意这里的数字和是指拼接成的新整数各位相加也就是1 2 3 4 5 15。让拼接后的整数乘以它的数字和返回结果。如果结果很大按题目要求取模。有一个关键观察能直接省掉很多无效计算拼接不会改变数字的“组成成分”。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])也就是说我至少要维护三个前缀数组preCnt[i]前 i 个字符中非零数字的个数preVal[i]前 i 个字符中非零数字拼接成的数值需要取模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 M2.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(); vectorlong 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 0preVal[4] 0intervalValue 0digitSum 0结果 0逻辑没问题。但如果你的代码里把“拼接结果为空”当成错误情况比如直接throw或者返回 -1那就错了。题目要求的结果就是 0因为空数字适配到整数是 0数字和是 0乘积自然是 0。还有一种边界区间里只有一个非零数字比如s 5查[1,1]。cnt 1intervalValue 5digitSum 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[r1] - 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-l1)。本质上都是“前缀信息 幂次修正”的思路。所以如果你把题目里的“非零数字拼接”理解成“某种基数下的编码”那这道题的解法可以迁移到很多场景字符子串哈希、多项式前缀、进制转换问题等。可见前缀和不是一个死的模板而是一套“维护可平移、可还原信息”的通用思想。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 的逆元。这又是一个能延伸出去的知识点这里不展开。写在最后我自己的体会是前缀和这个知识点特别容易让人产生“我懂了”的错觉直到遇到这种需要维护带权拼接信息的题才发现原来对“前缀数组到底存了什么”理解得不够深。数字和可以减拼接值却要乘幂修正这两种操作的区别才是这道题真正想考的东西。如果你也想练手建议按这个顺序来先写暴力版再写前缀和版最后尝试线段树版。每个版本都用一个随机生成器对拍一遍确保输出一致。这样下来你对“区间合并信息”会有一种很踏实的手感以后再遇到类似题目第一反应就不是套模板了。