【P8218 求区间和】一维前缀和入门完整题解博客
一、题目题意
给定长度为nnn的整数序列，再给出mmm次区间询问，每次给出区间左右端点l,rl,rl,r，输出区间[l,r][l,r][l,r]内所有数字的总和。
样例解读
输入：
4 4 3 2 1 2 1 4 2 3序列：[4,3,2,1][4,3,2,1][4,3,2,1]
- 区间[1,4][1,4][1,4]：4+3+2+1=104+3+2+1=104+3+2+1=10
- 区间[2,3][2,3][2,3]：3+2=53+2=53+2=5
输出两行依次为10、510、510、5。
二、核心算法：一维前缀和
1. 前缀和定义
定义前缀和数组sss，其中s[i]s[i]s[i]代表原数组前iii项的总和：
s[i]=a1+a2+⋯+ai s[i] = a_1 + a_2 + \dots + a_is[i]=a1+a2+⋯+ai
递推公式：
s[0]=0,s[i]=s[i−1]+a[i] s[0]=0,\quad s[i] = s[i-1] + a[i]s[0]=0,s[i]=s[i−1]+a[i]
2. 区间和计算公式
对于任意区间[l,r][l,r][l,r]，区间总和等于「前rrr项和」减去「前l−1l-1l−1项和」：
sum(l,r)=s[r]−s[l−1] sum(l,r) = s[r] - s[l-1]sum(l,r)=s[r]−s[l−1]
原理：s[r]s[r]s[r]包含1∼r1\sim r1∼r全部数字，s[l−1]s[l-1]s[l−1]包含1∼l−11\sim l-11∼l−1全部数字，两者相减恰好剩下l∼rl\sim rl∼r的数字之和。
3. 算法优势
- 预处理仅需O(n)O(n)O(n)时间；
- 每次区间查询仅O(1)O(1)O(1)常数时间；
- 对比暴力每次循环累加O(n)O(n)O(n)查询，海量询问下效率提升巨大。
三、完整AC代码
#include<bits/stdc++.h>usingnamespacestd;intn,m;inta[100005],s[100005];intmain(){scanf("%d",&n);for(inti=1;i<=n;i++){scanf("%d",&a[i]);s[i]=s[i-1]+a[i];}scanf("%d",&m);for(inti=1;i<=m;i++){intl,r;scanf("%d%d",&l,&r);printf("%d\n",s[r]-s[l-1]);}return0;}四、分步解题流程
步骤1：输入序列长度nnn，读入原数组aaa
循环从i=1i=1i=1到nnn读取每个数字，同步计算前缀和数组sss：
- s[0]s[0]s[0]程序默认初始为0；
- 每一步s[i]=s[i−1]+a[i]s[i] = s[i-1] + a[i]s[i]=s[i−1]+a[i]，完成预处理。
以样例数据演示前缀和数组生成：
a[1]=4, a[2]=3, a[3]=2, a[4]=1a[1]=4,\ a[2]=3,\ a[3]=2,\ a[4]=1a[1]=4,a[2]=3,a[3]=2,a[4]=1
s[0]=0s[0]=0s[0]=0
s[1]=s[0]+4=4s[1]=s[0]+4=4s[1]=s[0]+4=4
s[2]=s[1]+3=7s[2]=s[1]+3=7s[2]=s[1]+3=7
s[3]=s[2]+2=9s[3]=s[2]+2=9s[3]=s[2]+2=9
s[4]=s[3]+1=10s[4]=s[3]+1=10s[4]=s[3]+1=10
步骤2：输入询问次数mmm
循环处理每一组询问，每次读入区间端点l、rl、rl、r。
步骤3：套用公式计算区间和并输出
使用公式s[r]−s[l−1]s[r]-s[l-1]s[r]−s[l−1]快速得到答案：
- 询问1 41\ 414：s[4]−s[0]=10−0=10s[4]-s[0] = 10-0=10s[4]−s[0]=10−0=10
- 询问2 32\ 323：s[3]−s[1]=9−4=5s[3]-s[1] = 9-4=5s[3]−s[1]=9−4=5
五、代码逐段讲解
数组定义
inta[100005],s[100005];数组开到100005，适配题目数据范围；下标从1开始，规避边界l=1l=1l=1时l−1=0l-1=0l−1=0的特殊判断。
前缀和预处理循环
for(inti=1;i<=n;i++){scanf("%d",&a[i]);s[i]=s[i-1]+a[i];}边读入原数组，边递推计算前缀和，一次遍历完成预处理。
批量处理区间询问
for(inti=1;i<=m;i++){intl,r;scanf("%d%d",&l,&r);printf("%d\n",s[r]-s[l-1]);}每次查询直接通过前缀和差值算出区间和，无需再次遍历原数组。
六、题型总结
- 适用场景：静态数组（无单点修改）、大量区间求和查询；
- 模板记忆点：前缀和递推s[i]=s[i−1]+a[i]s[i]=s[i-1]+a[i]s[i]=s[i−1]+a[i]，区间公式s[r]−s[l−1]s[r]-s[l-1]s[r]−s[l−1]；
- 拓展延伸：二维前缀和、差分（支持区间修改+单点查询）是该知识点的延伸进阶内容。