【深进1.例1】求区间和

GitHub跳转原题关系图返回列表

用 accumulate 构造带前导零的前缀和，让每次区间询问都能 O(1) 作答。

OJ: luogu

题目 ID: P8218

难度:普及-

标签:前缀和python

创建: 2026-07-16 17:48

更新: 2026-08-09 06:46

后置题目
luogu P1775石子合并（弱化版）B 的区间 DP 转移 dp[l][r]=min(...+sum(l,r)) 反复求区间质量，直接复用 A 教的前缀和数组 prefix[r]-prefix[l-1] 这一步，B 在此之上叠加枚举最后一次合并断点的区间 DP。roj 3595[NOIP2012-普及] 寻宝B 的优化二复用 A 教的前缀和区间计数：pre 给出 [0,j) 的楼梯数，before = S - pre[start] 正是一次区间相减，由此 O(1) 定位第 k 个楼梯；B 在此基础上叠加取周期与两段回绕分支。roj 3029「To the Max」 最大的和B 正解把 A 教的「前缀和相减得到一段区间和」直接搬成列前缀和差分 O(1) 取竖条和，再叠加二维降维与 Kadane。roj 1598「一本通 5.5 例 2」最大连续和B 把 A 教的「前缀和作差得区间和」当作第一步复用（main.py 里 pres[i]-pres[dq[0]]），只是把固定询问区间换成限长子段，再叠加单调队列求窗口最小前缀luogu P3374【模板】树状数组 1B 把 A 的前缀差求区间和一步原样保留在 Fenwick 查询里，再叠加 lowbit 单点修改支持动态更新luogu P1569[USACO ?] Generic Cow Protests【来源请求】B 的 DP 转移合法性判断复用 A 的前缀和差求区间和这一步：sum(j+1..i)=pre[i]-pre[j] 正是 prefix[r]-prefix[l-1] 取 l=j+1，再叠加 A 未教的前缀划分 DP 与 dp[j] 可达性约束。luogu P3948数据结构B 的离线海量查询阶段复用 A 教的前缀和作差：先标记每个位置是否合格再建 ans_sum，直接用 ans_sum[R]-ans_sum[L-1] O(1) 回答

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

给定一个长度为 nn 的序列，回答 mm 个闭区间 [l,r][l,r] 的元素和。

思路

令 prefix[i] 表示前 i 个数之和，则区间和为 prefix[r] - prefix[l - 1]。预处理一次后，每个询问只做一次减法。

Python 知识

  • accumulate(a, initial=0) 直接产生长度为 n+1n+1 的前缀和，参见 /home/rainboy/mycode/hugo-blog/content/program_language/python/itertools_recipes.md。
  • "\n".join(...) 一次输出多行答案，参见 /home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md。
  • 嵌套生成器按需读取每组 l, r，不必保存全部询问。

代码

python
import sys
from itertools import accumulate


input = sys.stdin.buffer.readline
n = int(input())
prefix = list(accumulate(map(int, input().split()), initial=0))
answers = (str(prefix[r] - prefix[l - 1]) for l, r in
           (map(int, input().split()) for _ in range(int(input()))))
print("\n".join(answers))

复杂度

时间复杂度 O(n+m)O(n+m)，空间复杂度 O(n)O(n)。

总结

固定数组上的大量区间和询问，是前缀和最直接的应用。