前缀和觉醒：十万查询瞬杀术，O(1)结印碾压群殴战场
前情提要
昨天那场「单存档修复战」（3754. 连接非零数字并乘以其数字和 I）你还记得吧？磁盘坏道像一群虚空寄生虫，往玩家数据里随地大小 0。你祭出一套“纯数学流·逐位拆解连招”，平 A 带走全服第一氪佬的存档，操作秀得运维在群里连刷三个「大佬喝茶.jpg」。在你合上笔记本的瞬间，屏幕右下角又弹出运维的夺命连环消息——策划要在修复前先做一轮批量验伤，十万个查询区间，每个截子串、去零、拼接、求和、对轰，算出纯净校验码，好按损坏程度发补偿钻石。
今天早上 9:30，你端着刚冲好的咖啡坐到工位，发现运维已经 @ 了你三次：“哥，怎么样了？策划说十点半要开例会，他想在会上展示批量校验的结果。“你深吸一口气——昨天是单挑，今天是团本，平 A 清小怪的时代结束，是时候切一套群体大招了。
战场升级：从单挑到群殴
昨天的任务是这样的：
给你一个整数
n，过滤掉所有的0，拼接成x，计算去零拼接x * 数字和sum。
今天的任务变成了这样：
给你一个长度为 10^5 的数字字符串
s，还有 10^5 个查询，每个查询让你处理一个子串s[l..r]，执行和昨天一样的操作。返回所有查询的结果数组。
你心里快速拉了个复杂度：如果还用昨天的逐位拆解，每次查询都要遍历一遍子串，总复杂度 O(Q × N) = 10^5 × 10^5 = 10^10 次操作。好家伙，这个数字比你的加班时长还离谱，跑完别说十点半例会，连下个月版本更新都赶不上。你仿佛已经听见服务器风扇在悲鸣——不行，得请出「前缀和阵法」了。
破局关键：前缀和预炼化
你开始盘算：每次查询都是从原始字符串里截一段，再扫一遍做去零拼接，本质上是在重复计算——同一个位置的数字，可能被几十上百个查询区间扫过，每次都在做一模一样的事情，判断是不是零、累加数字和、去零拼接。
既然查询是海量的、区间是任意的，那为什么不提前把整条原始数据“炼化”一遍，把每个位置的关键信息预先算好、存进数组里？这样每次查询就像从数据库里查索引，O(1) 拿到中间结果，再拼装一下就能出答案。
你回想起经典的前缀和套路——算子串 [l, r] 的某个属性，往往可以用 pref[r] - pref[l-1] 的形式 O(1) 得到。比如，对于[l, r]区间内的**非零数字和 sum **，用前缀和数组 preSum[i] 表示 s[0..i-1] 中所有非零数字的和，那么 sum = preSum[r+1] - preSum[l]。O(1)，搞定。
但前缀和这个“减法”能成立，有个隐藏前提：属性必须是可加的，而且和顺序无关。
**去零拼接值 x **显然和顺序强相关。一旦区间内有零混迹其中，虽然非零数字之间的相对顺序不变，但它们中间的空位被“吃掉”了——比如 "102003" 变成 "123"，中间的零全是幽灵，2 直接跟在 1 后面，3 直接跟在 2 后面，原本隔着十万八千里的两个数字现在挨得紧紧的——零的出现会动态改变数字之间的位权关系，光靠一个前缀和数组没法直接算出 x。
你放下咖啡杯，意识到这个拼接操作才是真正的拦路虎。
关键洞察：把拼接拆成两件事
去零拼接值 x 说穿了就是一组非零数字按顺序排排坐，每个数字站在自己该站的数位上，拼成一个新的整数。写成算式就是：x = d₁ × 10^(k-1) + d₂ × 10^(k-2) + ... + dₖ × 10⁰，其中 k 是这组非零数字的总个数。每个数字的“站位”不由它在原串里的绝对位置决定，而由它在这个区间里排老几决定——前面还有几个非零数字，它就得往左挪几位。
假设整串 s 被切成三段：[0, l-1]、[l, r]、[r+1, n-1]。去零之后，这三段各自蜕变成一串纯数字。你给它们起了名字：第一段的拼接值叫 preVal[l]，第二段（我们要的那段）的拼接值叫 x，第二段里有 cnt 个非零数字，第一段加第二段合起来的拼接值叫 preVal[r+1]。
你盯着第一段和第二段去零后的连接，灵光炸裂——去零拼接操作本质上是“按序追加”（前缀 [0, l-1] 的拼接值后面，直接接上区间 [l, r] 的拼接值）。这不就是标准的“高位拼接低位”吗？第一段的拼接值往左挪 cnt 个位置（也就是乘以 10 的 cnt 次幂），腾出来的低位恰好由第二段的 x 填上：
preVal[r+1] = preVal[l] × 10^cnt + x
再赶紧把这个等式倒过来：
x = preVal[r+1] - preVal[l] × 10^cnt
这下好办了！preVal 本身从头扫到尾递推就行——遇非零数字就 preVal[i+1] = (preVal[i] × 10 + d) % MOD；cnt用一个标准的前缀和数组 preCnt 就能cnt = preCnt[r+1] - preCnt[l] O(1) 搞定；再提前预计算好 pow10 数组（pow10[cnt] 就是 10^cnt % MOD），这行公式就是 O(1) 的！
三前缀数组阵法：preSum、preVal、preCnt
你整理好一套干净利落的“三前缀数组阵法”。三个数组，各司其职，建好之后每个查询就是三次数组查找加两次算术运算，轻量得像刺客的连招：
preSum[i]——数字和总管：前i个字符中所有数字的和（0 不影响求和，所以等价于非零数字和）。sum = preSum[r+1] - preSum[l]就是区间内非零数字的和，O(1) 秒出。preVal[i]——拼接值档案库：前i个字符中去零拼接成的整数（对 MOD 取模）。递推规则：遇非零数字就preVal[i+1] = (preVal[i] × 10 + d) % MOD，遇零则preVal[i+1] = preVal[i]。它记录的是“如果从这里下刀，前面那段的拼接值是多少”，相当于给每个位置都拍了个快照。preCnt[i]——位权修正计数器：前i个字符中非零数字的个数。cnt = preCnt[r+1] - preCnt[l]就是区间内非零数字的个数，也是preVal[l]需要左移的位数。它管的是那个关键的10^cnt修正因子。
有了这三件法器，对于任意查询 [l, r]，你的施法流程直接变成一条流水线：
def sumAndMultiply(s: str, queries: List[List[int]]) -> List[int]:
MOD = 10**9 + 7
m = len(s)
# 预计算 10 的幂次（pow10[k] = 10^k % MOD）
pow10 = [1] * (m + 1)
for i in range(1, m + 1):
pow10[i] = (pow10[i-1] * 10) % MOD
# 三个前缀数组
preSum = [0] * (m + 1) # 数字和
preVal = [0] * (m + 1) # 去零拼接值
preCnt = [0] * (m + 1) # 非零数字个数
for i in range(m):
d = ord(s[i]) - 48 # 或者 int(s[i])
preSum[i+1] = preSum[i] + d
preCnt[i+1] = preCnt[i] + (d != 0)
if d != 0:
preVal[i+1] = (preVal[i] * 10 + d) % MOD
else:
preVal[i+1] = preVal[i]
ans = []
for l, r in queries:
cnt = preCnt[r+1] - preCnt[l]
if cnt == 0:
ans.append(0)
continue
sum_val = preSum[r+1] - preSum[l]
x = (preVal[r+1] - preVal[l] * pow10[cnt]) % MOD
ans.append((x * sum_val) % MOD)
return ans
你看着这段像乐高积木一样紧凑的代码，满意地往椅背上一靠。十万个查询在三个数组面前，不过是把同一套减法算术做十万遍——CPU 最不怕的就是重复劳动，让它跑去吧。
尾声
你把脚本跑完，十万条查询像开闸放水一样倾泻而过，终端上的进度条几乎没来得及显示就已经跳到 100%。从建数组到出结果，全程不到十秒，策划还没来得及在群里@你第四次。
用前缀和阵法瞬杀了十万次群殴，用空间换了时间，又让 CPU 少烧了几亿次循环。你端起那杯从九点半端到现在终于能喝一口的咖啡，温度刚好——就像 O(m) 预处理加 O(1) 查询，一切都卡在刚好的复杂度上。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。