用前缀和求任意连续区间的总和
OI Wiki 以主题目录串起算法竞赛知识,基础、数据结构和各类算法都可独立查阅。适合从一道题暴露的薄弱点反查词条,例如从区间求和查到前缀和。读页内代码前先确定下标与区间约定,以便和自己的题面对应。
条目把方法与适用条件放在一起阅读。例如前缀和能快速回答很多区间查询,但需要先说清楚下标从哪里开始、区间是否包含端点。
区间左右端点为何要用不同的下标
数组为 3、−2、5、4,按第 1 至第 4 项编号。定义 S[0]=0 且 S[i] 是前 i 项和,就得前缀值 0、3、1、6、10。第 2 至第 4 项的和是 S[4]−S[1]=7。减掉的是左端点以前的部分,所以这里要减 S[1] 而非 S[2]。
试做一次学习任务
在站内找“前缀和”,给数组 2、1、4、3 写出从 0 开始的累计和。
用累计和之差计算第 2 至第 4 项之和,再逐项相加作检验。
把查询改为只含一个元素或整段数组,确定自己公式中的端点都正确。
换个条件,自己试试
用同一组前缀值分别求第 2 项本身、第 1 至第 3 项之和。再说明为什么额外存一个 S[0] 可以少写一次特殊判断。
参考与自查
单项和 S[2]−S[1]=−2,前三项和 S[3]−S[0]=6。区间从第一项起时,左端之前的和自然是零,可沿用同一公式。
使用时留意什么
部分代码与数学符号面向有竞赛基础的读者,遇到陌生概念可先补相邻基础章节。
访问与使用条件
网站公开提供中文条目、例子与参考资料。
手机查看提示
在 390 像素宽的手机视口中已读到入口正文。音视频播放、登录及后续操作依设备和网络而异。
资料来源:OI Wiki 算法竞赛知识库官方页面
入口核对日期: