最近刷题的时候碰到一个挺有意思的字符串处理问题，题面很简短，翻译成人话大概是这样的：给你一个只包含数字的字符串，然后来一堆区间查询，每次给你一个区间 [l, r]，你要在这个子串里把所有“非零”的字符数字按从左到右的顺序挑出来、拼成一个数，再把这些非零数字的数值和算出来，最后把这两个东西乘起来作为答案。
说实话，第一眼看上去感觉就是个模拟题，但仔细一琢磨，“每个查询区间”这几个字一出来，事情就没那么简单了。如果直接每个查询都去扫描一遍子串，那复杂度轻松爆炸，尤其是字符串长度和查询次数都到十万级别的时候。今天的主题就是用 Go 语言把这个题做得漂亮：核心思路是前缀和 + 幂次预处理，把每次查询压到 O(1)，顺便把大数乘法和溢出这些暗坑也一起处理干净。
这个题非常适合拿来练 Go 的数组操作和数学推导，对刚学完 go语言基础、想进阶的同学来说，是一道性价比很高的综合题。下面我从题意拆解、数学推导到完整代码实现，把整条链路捋一遍。
1. 先搞清楚题目到底在问什么
很多同学看到“连接非零数字并乘以其数字和”这种题面，第一反应是懵的。我们先把这个规则拆干净，确保每一步都明确。
1.1 “连接非零数字”和“数字和”分别是什么
给定一个字符串 s = "1203405"，假设查询区间是 [1, 5]（这里我按 1-based 下标，后面实现里也统一用这个约定），子串就是 "12034"。
第一步，按从左到右的顺序，把所有非零的字符数字拿出来：
- 字符 '1' -> 数字 1
- 字符 '2' -> 数字 2
- 字符 '0' 是零，跳过
- 字符 '3' -> 数字 3
- 字符 '4' -> 数字 4
于是得到数字序列 [1, 2, 3, 4]，按顺序拼接成一个整数就是 1234。
第二步，算这些非零数字的“数字和”，也就是 1 + 2 + 3 + 4 = 10。
这里要特别提醒一下，“数字和”不是让你把拼接出来的 1234 的每一位再拆开求和——虽然在这个特定问题里这两种理解恰好等价，因为拼接出来的数本来就只包含这些非零数字，每一位就是那些非零数字本身。但从题目设计的角度理解，更准确的说法是：对所有挑出来的非零数字字符，做一个数值累加。这个细节在后面设计前缀数组的时候很关键。
最终答案就是 1234 × 10 = 12340。
如果区间里全是零，比如子串是 "000"，那就没有任何非零数字，拼接结果为空，这时候答案应该输出 0，这个边界要单独处理，后面我会讲。
1.2 为什么不能直接暴力扫描每个区间
最朴素的做法，每次查询都从 l 遍历到 r，把非零数字拼接、求和、相乘，复杂度是 O(区间长度)。如果字符串长度 n 是 10^5，查询次数 q 也是 10^5，最坏情况下总操作量是 10^10 量级，在 Go 里哪怕常数再小，也是铁定超时的。
所以问题的本质是一个典型的“区间聚合查询”问题：我们被反复询问某个区间的一些统计信息，这些信息有某种可减性，或者可以通过其他信息还原出来。最经典的思路就是前缀和。
这里存在一个障碍：拼接操作不像普通加法那样直观。假设我已经算出了前缀的拼接值，比如前 5 个非零数字拼成了 123，现在又来一个数字 4，拼接结果应该是 123 × 10 + 4 = 1234。这个操作本身很简单，但区间查询时不能直接拿两个前缀值相减，因为拼接数不是简单的累加量，它跟“区间内非零数字的个数”有关。这个问题就需要一点数学推导来解决了。
2. 核心思路：用三个前缀数组搞定一切
要把查询复杂度压到 O(1)，关键在于设计好预处理阶段的信息。这个题我最终用了三个数组：非零数字计数前缀数组、非零数字数值和前缀数组、非零数字拼接值前缀数组，外加一个 10 的幂次数组。下面一个一个说清楚。
2.1 计数前缀和与数字和前缀
第一个数组 cnt，cnt[i] 表示原字符串前 i 个字符（我习惯用 1-based 语义，cnt[0] = 0）中非零数字的个数。
第二个数组 sum，sum[i] 表示前 i 个字符中所有非零数字的数值之和。
这两个数组用脚趾头都能想明白遍历一遍字符串就能构建：
- 遇到字符 '0'，cnt 和 sum 都不变；
- 遇到非零字符 c，cnt[i] = cnt[i-1] + 1，sum[i] = sum[i-1] + int(c - '0')。
区间查询的时候，区间 [l, r] 内的非零数字个数 c = cnt[r] - cnt[l-1]，数字和 segSum = sum[r] - sum[l-1]。
这两个信息已经能回答“数字和”这一半了。
2.2 拼接值的区间还原：一个漂亮的数学公式
麻烦的是“拼接值”。如果有一个数组 val，val[i] 表示“前 i 个字符中的所有非零数字按顺序拼接成的整数”，那我怎么从 val[r] 和 val[l-1] 还原出区间 [l, r] 的拼接值？
先看一个事实：val[r] 本质上是“所有非零数字拼接出来的一个完整整数”。假设前缀 l-1 的部分拼接成了 X，区间 [l, r] 内的非零数字拼接成了 Y，Y 一共有 c 位（c 恰好就是区间内非零数字的个数），那么整个前缀 r 的拼接值就是：
val[r] = X × 10^c + Y
这个式子非常好理解，随便举个数：前缀拼接值是 12，区间内拼接值是 345，c = 3，整个值就是 12 × 1000 + 345 = 12345。
所以反过来：
Y = val[r] - val[l-1] × 10^c
用这个公式，只要预处理了 val 数组和 10 的幂次数组 pow10，每次查询就能 O(1) 还原区间拼接值。
这里再强调一个容易忽略的细节：指数 c 不是区间长度，而是区间内“非零数字的个数”。因为拼接过程会跳过零，零不产生新的数字位，所以在乘 10 的幂次时，补位的数量必须跟非零数字的数量严格一致，否则公式就错了。
2.3 取模的必要性与 pow10 数组的构建
标题里的“Ⅱ”说明这是一个系列题，通常这种题的输出会涉及一个很大的整数，因为非零数字拼接出来可能长达 10^5 位，这在任何固定位数的整数类型里都存不下。所以常见的赛题版本会要求对结果取模，比如模 10^9+7。这个题目的描述里虽然没有明确写模数，但工程上比较稳妥的做法是：默认处理取模版本，同时在文章最后给大家补充不取模时该怎么做。
我用的模数 mod = 1000000007，这是一个经典的质数模数，Go 的 int64 完全装得下中间运算结果。
pow10 数组的含义是 10 的 i 次方对 mod 取模的结果。构建时一个循环搞定：
pow10 := make([]int64, n+1) pow10[0] = 1 for i := 1; i <= n; i++ { pow10[i] = pow10[i-1] * 10 % mod }为什么只需要准备到 n？因为区间内非零数字个数最多也就是整个字符串的长度 n，所以幂次最大就是 n。
2.4 为什么这套方案能跑得快
整体的时间复杂度分两部分：
- 预处理阶段，遍历一次字符串 O(n)；
- 查询阶段，每个区间进行常数次加减乘和取模，O(1)。
所以总复杂度是 O(n + q)，即使 n 和 q 都是 10^6 级别，也能轻松跑完。空间上用了 4 个长度为 n+1 的 int64 数组，大约 4 × 8 × 10^5 = 3.2MB，在 Go 的内存模型下毫无压力。
对比一下暴力做法的 O(nq)，这个优化力度是数量级的飞跃，也是这个题最核心的价值所在：让你意识到“区间查询”类问题，永远先去想能不能用前缀信息表达出来。
3. Go语言完整实现与逐段拆解
光讲理论不行，代码也得能直接抄。下面我给出一份完整的 Go 实现，并标好注释，方便对照理解。
3.1 核心代码：预处理 + 查询
package main import ( "bufio" "fmt" "os" ) const mod = 1000000007 func main() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n, q int fmt.Fscan(in, &n, &q) var s string fmt.Fscan(in, &s) cnt := make([]int, n+1) // 非零数字个数前缀 sum := make([]int64, n+1) // 非零数字数值和前缀 val := make([]int64, n+1) // 非零数字拼接值前缀（取模） pow10 := make([]int64, n+1) // 10的幂次（取模） pow10[0] = 1 for i := 0; i < n; i++ { cnt[i+1] = cnt[i] sum[i+1] = sum[i] val[i+1] = val[i] pow10[i+1] = pow10[i] * 10 % mod if s[i] != '0' { d := int64(s[i] - '0') cnt[i+1]++ sum[i+1] += d val[i+1] = (val[i]*10 + d) % mod } } for i := 0; i < q; i++ { var l, r int fmt.Fscan(in, &l, &r) c := cnt[r] - cnt[l-1] if c == 0 { fmt.Fprintln(out, 0) continue } segVal := (val[r] - val[l-1]*pow10[c]%mod + mod) % mod segSum := sum[r] - sum[l-1] ans := segVal * (segSum % mod) % mod fmt.Fprintln(out, ans) } }3.2 关键代码逻辑说明
预处理循环里，我用了“先继承后更新”的模式：cnt、sum、val 每个新位置都先等于前一个位置的值，然后根据当前字符是否为零决定要不要更新。这样做的原因是保持前缀定义的完整性：如果当前字符是零，那么前 i+1 个字符的非零数字集合跟前 i 个字符是完全一样的，值必须继承下来。
val 的更新使用了拼接公式：把当前数字 d 追加到已有拼接值的末尾，等价于 val[i] × 10 + d。在取模的情况下，因为 (a×10 + d) mod M = (a mod M × 10 + d) mod M，所以每一步取模是安全的。
查询阶段里，
segVal := (val[r] - val[l-1]*pow10[c]%mod + mod) % mod这行要仔细看。val[l-1] × pow10[c] 本身可能已经很大，所以先取了 mod，再用 val[r] 去减。减完之后可能是负数，所以加一个 mod 再取一次模，保证结果是 [0, mod) 范围内的非负整数。这是 Go 里处理负数取模的标准写法，千万别省掉中间那个 + mod。
segSum 是 int64 类型，理论上最大值是 n × 9，n 到 10^6 也只有 9×10^6，远不会溢出，所以直接算就行。最后乘之前再对 segSum 取一次模，避免出现更大的中间结果。
3.3 输入输出与性能细节
字符串长度和查询次数都很大时，fmt.Fscan 和 fmt.Fprintln 配合 bufio.Reader 和 bufio.Writer 已经足够应对，不需要再手动写快读。这里有几个性能小习惯：
- 尽量把输出 writer 攒到最后统一 flush，减少系统调用次数；
- 如果输入里只有数字和空格，可以尝试用 strings.Fields 一次读完，但 bufio.Fscan 的通用性更好，代码也更简洁；
- 在极大规模（比如 n, q 到 10^7）下，可以换用自定义的 readInt 函数，但对于绝大多数练习场景，上面的写法足够了。
4. 实战踩坑：我从这个题里学到的几个教训
这个题表面简单，实际代码一写，各种问题就冒出来了。我把在本地测试和提交时踩过的坑整理一下，每一条都是真金白银换来的。
4.1 索引从 0 到 1 的偏移，最容易犯错
Go 的字符串下标天然是 0-based，而题目查询输入通常是 1-based。我在前缀数组里把下标 i 定义为“前 i 个字符”，也就是 index = 0 表示空前缀，index = i 对应 s[0..i-1]。这样查询 [l, r] 时，区间内字符对应的前缀下标分别是 l-1 和 r。
这个设计在很多题里都很管用，但代价是容易把边界搞混。我调试时遇到过一次查询 [1, 1] 结果不对，最后发现是在初始化循环里写成了 cnt[i] = cnt[i-1]，导致 cnt[0] 被赋了垃圾值。正确写法是循环变量 i 从 0 到 n-1，新位置统一用 i+1。
建议拿到任何一道区间题，先把“我的数组下标代表什么”写在注释里，再开始写循环，别省这几秒。
4.2 全零区间不是“正常跑公式”能 cover 的
如果区间内没有非零数字，c = 0，val[l-1] × pow10[0] = val[l-1]，segVal = val[r] - val[l-1]。如果 l-1 和 r 之间恰好没有任何非零数字，val[r] 就等于 val[l-1]，segVal 计算结果为 0，看似没问题。
但等一下，真的没问题吗？如果字符串是 "0001000"，查询 [5, 7]，子串是 "000"，非零数字个数确实是0，公式算出 segVal = 0。可如果查询区间跨过一个非零数字但区间本身为零呢？比如查询 [2, 3]，子串 "00"，val[3] 可能包含前面某个非零数字，val[1] 也可能包含那个非零数字，两者相等，结果还是 0。
这个公式在数学上其实是自洽的，但问题在于 c = 0 时，segSum 一定也是 0，最终结果注定是 0。为了避免不必要的计算和潜在的边界混淆，我在代码里显式判断了 c == 0，直接输出 0。这个分支看起来多余，实际上能让逻辑更清晰，也能防止某些变体题里对空拼接值的特殊定义造成混淆。
4.3 取模时机不对，结果悄悄出错
我第一次写的时候，segVal 直接这样写：
segVal := (val[r] - val[l-1]*pow10[c] + mod) % mod忽略了 pow10[c] 和 val[l-1] 都是模过 M 的数，它们相乘以后可能超过 int64 的安全范围吗？两个 int64 数相乘，最大可以达到 (10^9)^2 = 10^18，int64 的上限是约 9.2×10^18，看起来不溢出。但如果模数不是 10^9+7，而是更大的值，或者以后题目变了，这里很容易炸。正确的做法是先对乘积取模：
segVal := (val[r] - val[l-1]*pow10[c]%mod + mod) % mod这里有个优先级要提醒：在 Go 里，% 和 *、/ 是同一优先级，从左到右结合。所以 val[l-1]*pow10[c]%mod 会先算 val[l-1] * pow10[c]，再整体对 mod 取模，这正是我想要的效果，不会产生歧义。
4.4 val 的拼接值取模后会丢信息吗
有同学可能会担心：val 是取模后的拼接值，用它去还原 segVal，结果还是“真实的拼接值”吗？
答案是：在模 M 的意义下是。因为整个公式里只有加减和乘法，这些运算在模运算下是同态映射——对每个数先取模再运算，和先运算再取模，结果一致。所以 val[r] 和 val[l-1] 都取模后，segVal 得到的是真实区间拼接值对 M 取模的结果，这正好是题目要求的答案。
如果你真的遇到了不取模的题目，那情况下面的 big.Int 方案会更合适，但复杂度会明显变高，后面第五节单独讲。
4.5 本地测试时用对拍验证
提交前我习惯写一个暴力解法做对拍。小数据量下随机生成字符串和查询区间，比较每个查询的暴力结果和优化版本结果。
对拍代码逻辑很简单：暴力函数直接对 s[l:r] 遍历，维护一个 int64 的拼接值和一个 int64 的和，最后相乘。因为小数据不会溢出，所以能直接算。
如果对拍十万组随机数据全都一致，我才会提交。这个习惯帮我抓到了不止一个因为索引偏移导致的隐蔽 bug，强烈推荐。
5. 延伸思考与进一步的优化空间
接下来聊几个跟这个题相关的进阶话题，也是我在做完之后自己思考过的问题，分享出来给大家一些启发。
5.1 不取模时怎么办：big.Int 与性能取舍
如果题目明确要求输出完整的大整数，不取模，那情况就复杂了。区间拼接值可能是一个十万位的十进制整数，Go 内置的 int64 完全装不下，这时候必须使用 math/big 包。
思路依然是前缀和，只不过 val 数组不能存 int64 了，得存 *big.Int。问题是这样一来内存和时间都会翻倍，而且每次区间查询如果要构造完整的大数，复杂度容易退化。一种可行的方案是：不是每个位置都存完整前缀大数，而是存一个结构体，包含拼接值对应的 big.Int；查询时通过减法得到区间的拼接值，再与数字和相乘。
但这种实现的常数非常大，实测在 n, q 都为 10^5 时，运行时间可能比取模版本慢一个数量级甚至更多。所以竞赛题里基本不会这么出，如果真遇到了，大概率是 n 和 q 都不大，或者要求用十进制字符串处理。
从这里也能看出，出题人让你取模，不只是为了刁难你，更是在给你降低难度。
5.2 如果查询区间很大，还能更快吗
目前的 O(n + q) 已经是最优渐进复杂度了，因为你至少要把字符串读一遍、把每个查询读一遍。常数方面，还有一点优化空间：pow10 数组可以只在需要时用快速幂计算，但这样每个查询变成 O(log n)，反而更慢，所以预处理所有幂次是更合适的选择。
内存方面，cnt 数组理论上可以用 int32 甚至 int16，但在 Go 里这些类型的运算需要额外转换，反而可能变慢，所以直接用 int 就好，不必过度优化。
5.3 这类“跳过特定字符再拼接”的题目还有什么变体
我做完这个题，第一反应是联想到“去除某些字符后求哈希值”一类的问题。比如给你一个字符串，查询区间内去掉空格后拼接起来的哈希值；或者去掉元音字母后拼接起来再取模。核心思想完全一致：
- 维护一个“有效字符计数前缀”；
- 维护一个“聚合值前缀”；
- 查询时用 cnt 差作为幂次或长度修正。
掌握了这个套路，遇到类似题目基本能秒出思路。关键在于识别出问题中的“跳过规则”是否只影响字符的选择，不影响相对顺序。只要相对顺序保持，就可以用类似的前缀拼接公式。
5.4 用这个题强化 Go 的切片思维
说实话，这个题也是一道很好的 Go 练习题。它强迫你思考下标语义、切片边界、数组复用，这些都是 go语言基础 里比较容易薄弱的地方。我在给新手做代码 review 时经常发现，很多同学写循环喜欢复制粘贴、i 和 i+1 混用，这个题就是治这个毛病的好药。
建议拿到代码后手动跑几个小样例，把 cnt、sum、val、pow10 四个数组的每个下标都手算一遍，画一张表出来去对比。这个过程看着笨，但对理解和记忆是非常扎实的。
6. 本地测试用例与最终验证
最后放一组我用的测试数据，大家可以拿去直接跑一下，验证自己的实现是否正确。
输入：
7 4 1203405 1 5 2 3 1 7 4 6输出期望：
12340 4 26010 420我手算其中两个验证一下：
查询 [2, 3]，子串是 "20"，非零数字只有 2，拼接值 2，数字和 2，答案 4。
查询 [4, 6]，子串是 "340"，非零数字是 3 和 4，拼接值 34，数字和 7，答案 238？等等，这里我重新算一下：s[4] = '3'，s[5] = '4'，s[6] = '0'，子串是 "340"，拼接值是 34，数字和是 3 + 4 = 7，34 × 7 = 238，不是 420。看来上面期望值写错了，我纠正一下，实际应该输出：
- [1, 5]：1234 × 10 = 12340
- [2, 3]：2 × 2 = 4
- [1, 7]：12345 × 15 = 185175
- [4, 6]：34 × 7 = 238
所以真正的期望输出是：
12340 4 185175 238这个小插曲其实也说明了一个问题：手算期望值很容易出错，尤其是指定多个区间的时候。所以我在本地总是跑对拍，而不是依赖手算，这一点值得所有人养成习惯。
我自己在实现完后，用随机生成的数据跑了十万组对拍，结果完全一致，才最终定稿。整个过程下来最大的感受是：这个题的核心难点不在 Go 语法，而在你能不能看穿“前缀拼接值”背后的数学本质。只要理解了 val[r] = val[l-1] × 10^c + intervalVal 这个公式，整个题目就豁然开朗了。
最后再分享一个小技巧：调试这种带前缀数组的题目，别急着用 fmt.Println 打印整个数组。如果你只打印某个区间相关的几个值，信息噪音会小很多，问题定位反而更快。我就是靠这种方式，把一开始那个隐蔽的取模负数问题揪出来的。希望这篇文章能帮你在 Go 的算法路上少踩几个坑，咱们下次见。
