一、题目题意给定长度为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]432110432110432110区间[2,3][2,3][2,3]325325325输出两行依次为10、510、510、5。二、核心算法一维前缀和1. 前缀和定义定义前缀和数组sss其中s[i]s[i]s[i]代表原数组前iii项的总和s[i]a1a2⋯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代码#includebits/stdc.husingnamespacestd;intn,m;inta[100005],s[100005];intmain(){scanf(%d,n);for(inti1;in;i){scanf(%d,a[i]);s[i]s[i-1]a[i];}scanf(%d,m);for(inti1;im;i){intl,r;scanf(%d%d,l,r);printf(%d\n,s[r]-s[l-1]);}return0;}四、分步解题流程步骤1输入序列长度nnn读入原数组aaa循环从i1i1i1到nnn读取每个数字同步计算前缀和数组ssss[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]1s[0]0s[0]0s[0]0s[1]s[0]44s[1]s[0]44s[1]s[0]44s[2]s[1]37s[2]s[1]37s[2]s[1]37s[3]s[2]29s[3]s[2]29s[3]s[2]29s[4]s[3]110s[4]s[3]110s[4]s[3]110步骤2输入询问次数mmm循环处理每一组询问每次读入区间端点l、rl、rl、r。步骤3套用公式计算区间和并输出使用公式s[r]−s[l−1]s[r]-s[l-1]s[r]−s[l−1]快速得到答案询问1 41\ 414s[4]−s[0]10−010s[4]-s[0] 10-010s[4]−s[0]10−010询问2 32\ 323s[3]−s[1]9−45s[3]-s[1] 9-45s[3]−s[1]9−45五、代码逐段讲解数组定义inta[100005],s[100005];数组开到100005适配题目数据范围下标从1开始规避边界l1l1l1时l−10l-10l−10的特殊判断。前缀和预处理循环for(inti1;in;i){scanf(%d,a[i]);s[i]s[i-1]a[i];}边读入原数组边递推计算前缀和一次遍历完成预处理。批量处理区间询问for(inti1;im;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]拓展延伸二维前缀和、差分支持区间修改单点查询是该知识点的延伸进阶内容。