注意力分数的稳定区间求和（AI038）- 算法机考高频题型 · log-sum-exp / 数值稳定题解 | AlgoMooc

AI038. 注意力分数的稳定区间求和

困难

通过率 0% · 提交 0 · 通过 0

log-sum-exp数值稳定

这道 OJ 的配套动画

稳定区间求和 · 对应本题的思路、过程和代码

看这道题的动画讲解

改编自算法机考高频题型 · log-sum-exp / 数值稳定类型 · 难度：困难

给定 n 个注意力分数 s_i，回答 q 个查询：对区间 [l,r] 输出 ln(Σ exp(s_i))，保留四位小数。

可以用区间最大值 m 与缩放和 t=Σ exp(s_i−m) 表示指数和，对应答案为 m+ln(t)。合并两段时，先取共同最大值 M，再计算 t_1 exp(m_1−M)+t_2 exp(m_2−M)。这在精确实数运算下等价；有限精度实现不保证不同合并顺序得到逐位相同的结果。

测试数据保证精确答案到四位小数舍入边界的距离不小于 10^-7。实现仍须控制输入解析、减法、求和及加回最大值的误差；这个保护距离不意味着直接读取为 double 的任意实现都能正确舍入。

这类题属于算法机考高频题型中「log-sum-exp / 数值稳定」方向的高频题型，通常考察对「log-sum-exp / 数值稳定」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

第一行两个整数 n q。第二行 n 个实数 s_i，小数位数不超过 4。随后 q 行，每行两个整数 l r，满足 1 <= l <= r <= n。分数以普通十进制形式给出，不使用科学计数法，小数位数不超过四位。

输出描述

对每个查询输出一行，即区间指数和的自然对数，保留四位小数。

数据范围

1 <= n <= 20000；1 <= q <= 50；|s_i| <= 10^9；小数位数不超过 4。每个查询答案的精确值到四位小数舍入边界的距离不小于 10^-7。

示例

示例 1

输入示例

3 2
1.0000 2.0000 3.0000
1 3
2 2

输出示例

3.4076
2.0000

说明：

小数组基础查询

示例 2

输入示例

2 1
1000000000.0000 -1000000000.0000
1 2

输出示例

1000000000.0000

说明：

±10^9 的稳定计算

时间限制 5000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

训练营动画视频讲解

最大值与缩放和的区间合并

加载中

正在加载动画…

问小欧 · 图解算法年卡¥99 开通 →

题库上一题下一题

未登录也能直接「运行」调试;「提交」判题需微信登录,你写的代码会自动保留、登录后回到本题继续。

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

1
2

# 在此编写你的代码

写完代码点「提交」，将对全部测试用例判题。

⚠️ 这道题的坑 · 易错点与反直觉

这些是真正决定能不能 AC、但通用题解里常被略过的点。

最大值平移避免指数溢出，但输入解析和最后加回最大值也可能损失精度。
先把四位小数存成整数，整数相减后才转浮点数；最大值最终也以整数加回。
Python 用 fsum、C++/Java 用补偿求和；只舍入较小的对数修正量，再输出整数保存的四位小数。

解题思路

每个查询先找区间最大值 m，再计算 total=Σexp(s_i-m)，答案为 m+ln(total)。输入最多四位小数，先按字符串解析为放大一万倍的整数 S；指数只使用整数差 S_i-M 转换得到的小数，最后把较小的对数修正量舍入后与整数 M 相加，避免十亿量级原值在浮点加法中丢失低位。

正确性说明

从指数和中提出公共因子 exp(m)，可得 ln(Σexp(s_i))=m+ln(Σexp(s_i-m))，因此变换与原式完全等价。缩放后至少有一项为 exp(0)=1，不会发生总和下溢为零。补偿求和减少多个小指数相加时的舍入误差，整数形式加回最大值保留了四位小数所需的低位。

复杂度分析

每个查询扫描区间两次，最坏时间复杂度为 O(nq)，保存输入需要 O(n) 空间。题目范围内最多执行一百万级的元素访问，无需额外构造线段树。

边界与常见错误

区间非空，因此缩放和始终为正。实现忽略指数参数小于 -50 的项时，其总误差上界低于 20000·exp(-50)，结合题目给出的舍入保护距离不会改变四位小数结果。不能直接计算 exp(s_i)，也不能先把十亿量级且带四位小数的输入读成低精度数再做差。

参考代码

import math
import sys


def parse_scaled(text):
    sign = -1 if text.startswith('-') else 1
    text = text.lstrip('+-')
    whole, _, fraction = text.partition('.')
    return sign * (int(whole or '0') * 10000 + int((fraction + '0000')[:4]))


def format_scaled(value):
    magnitude = abs(value)
    return ('-' if value < 0 else '') + f'{magnitude//10000}.{magnitude%10000:04d}'


def solve(text):
    tokens = iter(text.split())
    n, q = int(next(tokens)), int(next(tokens))
    scores = [parse_scaled(next(tokens)) for _ in range(n)]
    out = []
    for _ in range(q):
        left, right = int(next(tokens))-1, int(next(tokens))
        maximum = max(scores[left:right])
        total = math.fsum(math.exp((s-maximum)/10000) for s in scores[left:right]
                          if s-maximum >= -500000)
        offset = math.floor(math.log(total)*10000 + 0.5)
        out.append(format_scaled(maximum + offset))
    return '\n'.join(out)


if __name__ == '__main__':
    print(solve(sys.stdin.read()))