Meta 按值区间求和：单次扫描到多查询索引

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• S<=E，值域过滤含两个端点；重复值每次出现均累加，负值正常参与。
• 条件作用于元素值，不是数组下标。示例单次查询不修改输入、不预排序。

解题路线

1. 单次查询直接扫所有值，若S<=v<=E则加v。无索引时所有元素都可能影响答案，O(n)已合适。
2. 多次静态查询可排序数组，并建立前缀和；lower_bound(S)与upper_bound(E)得到所有合格元素的切片，前缀差返回总和。
3. 若频繁更新而值域可离散化，树状数组存每个值的总贡献value×frequency，范围查询两个prefix之差；仅存次数无法直接得到和值。

手动走一遍

[5,1,3,3,−2]，S=1/E=3，答案1+3+3=7；S=−2/E=−2返回−2，不是数目1。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def value_range_sum(values, start, end):
    if start > end:
        raise ValueError("reversed value bounds")
    return sum(value for value in values if start <= value <= end)

复杂度

单次O(n)时间/O(1)辅助空间；静态多查询预处理O(n log n)+O(n)空间，每次O(log n)。动态压缩值域查询与更新O(log U)。

易错点与追问

容易失分的边界

• 将过滤当作下标切片会完全误解题意。
• 以set去重后求和会把重复值贡献丢掉。

继续深挖

• 只有非负值时可能提前根据sum剪枝吗？未排序输入没有依据跳过后续值，单次扫描仍必需。
• 动态插入此前未知值会使离散化失效，可改有序统计树并维护子树sum。