1. 前缀和算法差分算法本章将详细讲解前缀和与差分两种基础核心算法的核心定义、原理、使用场景及代码模板两种算法是算法竞赛中高频出现的基础优化手段适配区间操作类题型。本章所有代码案例已统一收录至代码仓库。代码仓库链接1.1 算法核心定义与原理1.1.1 前缀和算法前缀和算法是区间求和专用的高效预处理优化算法核心作用是将多次区间求和的时间复杂度大幅降低完美解决大数据量区间求和超时问题。在未优化的暴力解法中若数组长度为x xx存在m mm次区间查询单次查询遍历区间长度为n nn整体时间复杂度为O ( m ⋅ n ) O(m \cdot n)O(m⋅n)。当数据量达到10 5 10^5105级别时暴力解法会直接超时。而前缀和算法通过一次预处理、多次查询的思路预处理时间复杂度为O ( x ) O(x)O(x)单次区间查询仅为O ( 1 ) O(1)O(1)海量查询场景下效率碾压暴力解法是算法竞赛区间求和题型的必备技巧。算法核心简述定义原数组为a aa本文统一采用0下标存储新建前缀和数组p r e prepre。其中p r e [ i ] pre[i]pre[i]表示原数组a aa中前i 1 i1i1个元素的总和即a [ 0 ] a[0]a[0]到a [ i ] a[i]a[i]的累加和。前缀和数组递推规律如下p r e [ 0 ] a [ 0 ] p r e [ 1 ] a [ 0 ] a [ 1 ] p r e [ 2 ] a [ 0 ] a [ 1 ] a [ 2 ] ⋯ p r e [ n ] ∑ k 0 n a [ k ] pre[0] a[0] \\ pre[1] a[0]a[1] \\ pre[2] a[0]a[1]a[2] \\ \cdots \\ pre[n] \sum_{k0}^n a[k]pre[0]a[0]pre[1]a[0]a[1]pre[2]a[0]a[1]a[2]⋯pre[n]k0∑na[k]通过递推公式可快速推导原数组任意区间 0下标包含两端的元素和p r e [ r ] − p r e [ l − 1 ] pre[r] - pre[l-1]pre[r]−pre[l−1]。特殊地当l 0 l0l0时区间和直接等于p r e [ r ] pre[r]pre[r]。经典模板题题目描述给定长度为x xx的数组a aa以及n nn次区间查询每次给出区间[ l , r ] [l, r][l,r]求数组第l ll项到第r rr项的区间和逐行输出每次查询结果。输入格式第一行x , n x, nx,n数组长度、查询次数第二行a 1 , a 2 , … , a x a_1, a_2, \dots, a_xa1,a2,…,ax数组元素后续n nn行每行两个数l i , r i l_i, r_ili,ri查询区间数据范围0 ≤ l ≤ r ≤ x ≤ 10 5 0 \le l \le r \le x \le 10^50≤l≤r≤x≤1050 n ≤ 10 5 0 \lt n \le 10^50n≤105代码模板代码路径1/prefix_sum.cpp#includebits/stdc.husingnamespacestd;constintmaxn1e510;inta[maxn],pre[maxn];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intx,n;cinxn;// 读入原数组for(inti0;ix;i){cina[i];}// 预处理前缀和数组pre[0]a[0];for(inti1;ix;i){pre[i]pre[i-1]a[i];}// 处理n次区间查询intl,r;for(inti0;in;i){cinlr;// 适配0下标区间求和公式if(l0)coutpre[r]\n;elsecoutpre[r]-pre[l-1]\n;}return0;}1.1.2 差分算法差分算法是区间批量修改专用的高效预处理算法核心场景为对数组多次执行「区间统一加/减固定数值」的操作最后输出修改后的完整数组。暴力区间修改的时间复杂度为O ( m ⋅ n ) O(m \cdot n)O(m⋅n)大数据量下极易超时差分算法通过预处理差分数组将整体复杂度优化至O ( x q ) O(xq)O(xq)是区间批量更新题型的最优解。算法核心简述差分是前缀和的逆运算。基于原数组a aa0下标构建差分数组d i f f diffdiff数组元素对应规则如下d i f f [ 0 ] a [ 0 ] d i f f [ 1 ] a [ 1 ] − a [ 0 ] d i f f [ 2 ] a [ 2 ] − a [ 1 ] ⋯ d i f f [ i ] a [ i ] − a [ i − 1 ] ( i ≥ 1 ) diff[0] a[0] \\ diff[1] a[1] - a[0] \\ diff[2] a[2] - a[1] \\ \cdots \\ diff[i] a[i] - a[i-1] \quad (i \ge 1)diff[0]a[0]diff[1]a[1]−a[0]diff[2]a[2]−a[1]⋯diff[i]a[i]−a[i−1](i≥1)核心操作原理对原数组区间[ l , r ] [l, r][l,r]统一增加数值q qq仅需对差分数组执行两步操作d i f f [ l ] q diff[l] qdiff[l]q区间起点生效后续所有元素累加qd i f f [ r 1 ] − q diff[r1] - qdiff[r1]−q区间终点后一位抵消保证区间外元素不受影响所有区间修改完成后对d i f f diffdiff数组求一次前缀和即可还原得到修改后的原数组。手动推演示例设原数组a { 1 , 5 , 3 , 7 , 8 , 2 , 4 } a \{1,5,3,7,8,2,4\}a{1,5,3,7,8,2,4}构建初始差分数组d i f f { 1 , 4 , − 2 , 4 , 1 , − 6 , 2 } diff \{1,4,-2,4,1,-6,2\}diff{1,4,−2,4,1,−6,2}。执行操作对区间[ 2 , 4 ] [2,4][2,4]0下标所有元素加3。差分更新d i f f [ 2 ] 3 diff[2] 3diff[2]3、d i f f [ 5 ] − 3 diff[5] - 3diff[5]−3更新后d i f f { 1 , 4 , 1 , 4 , 1 , − 9 , 2 } diff \{1,4,1,4,1,-9,2\}diff{1,4,1,4,1,−9,2}前缀和还原数组得到新数组a { 1 , 5 , 6 , 10 , 11 , 2 , 4 } a \{1,5,6,10,11,2,4\}a{1,5,6,10,11,2,4}效果验证仅区间[ 2 , 4 ] [2,4][2,4]元素全部3其余元素保持不变符合预期。经典模板题题目描述给定长度为x xx的数组a aa进行n nn次区间修改操作每次操作将区间[ l , r ] [l, r][l,r]内所有元素增加数值q qq最终输出修改后的完整数组。输入格式第一行x , n x, nx,n第二行a 1 , a 2 , … , a x a_1, a_2, \dots, a_xa1,a2,…,ax后续n nn行每行三个数l i , r i , q i l_i, r_i, q_ili,ri,qi数据范围同前缀和模板题所有数据保证在 int 范围内。代码模板优化版代码路径1/difference.cpp#includebits/stdc.husingnamespacestd;constintmaxn1e55;inta[maxn],diff[maxn];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intx,n;cinxn;// 读入原数组for(inti0;ix;i){cina[i];}// 构建差分数组diff[0]a[0];for(inti1;ix;i){diff[i]a[i]-a[i-1];}// 批量处理区间修改操作for(inti0;in;i){intl,r,q;cinlrq;// 转换为0下标l--,r--;diff[l]q;// r1越界时无需抵消无后续元素不影响结果if(r1x)diff[r1]-q;}// 前缀和还原修改后的数组for(inti1;ix;i){diff[i]diff[i-1];}// 输出结果for(inti0;ix;i){coutdiff[i] ;}return0;}1.1.3 算法小结前缀和与差分是算法竞赛入门最基础、最实用的成对算法二者互为逆运算核心价值均为优化区间操作时间复杂度彻底解决暴力解法的超时问题。前缀和专攻多查询、无修改的区间求和场景一次预处理O(1)快速查询差分专攻多修改、最后查询的区间批量更新场景一次预处理高效完成批量修改两种算法逻辑简洁、代码量小是后续进阶算法二维前缀和、差分约束等的基础必须熟练掌握模板与核心原理。
1. 前缀和算法差分算法本章将详细讲解前缀和与差分两种基础核心算法的核心定义、原理、使用场景及代码模板两种算法是算法竞赛中高频出现的基础优化手段适配区间操作类题型。本章所有代码案例已统一收录至代码仓库。代码仓库链接1.1 算法核心定义与原理1.1.1 前缀和算法前缀和算法是区间求和专用的高效预处理优化算法核心作用是将多次区间求和的时间复杂度大幅降低完美解决大数据量区间求和超时问题。在未优化的暴力解法中若数组长度为x xx存在m mm次区间查询单次查询遍历区间长度为n nn整体时间复杂度为O ( m ⋅ n ) O(m \cdot n)O(m⋅n)。当数据量达到10 5 10^5105级别时暴力解法会直接超时。而前缀和算法通过一次预处理、多次查询的思路预处理时间复杂度为O ( x ) O(x)O(x)单次区间查询仅为O ( 1 ) O(1)O(1)海量查询场景下效率碾压暴力解法是算法竞赛区间求和题型的必备技巧。算法核心简述定义原数组为a aa本文统一采用0下标存储新建前缀和数组p r e prepre。其中p r e [ i ] pre[i]pre[i]表示原数组a aa中前i 1 i1i1个元素的总和即a [ 0 ] a[0]a[0]到a [ i ] a[i]a[i]的累加和。前缀和数组递推规律如下p r e [ 0 ] a [ 0 ] p r e [ 1 ] a [ 0 ] a [ 1 ] p r e [ 2 ] a [ 0 ] a [ 1 ] a [ 2 ] ⋯ p r e [ n ] ∑ k 0 n a [ k ] pre[0] a[0] \\ pre[1] a[0]a[1] \\ pre[2] a[0]a[1]a[2] \\ \cdots \\ pre[n] \sum_{k0}^n a[k]pre[0]a[0]pre[1]a[0]a[1]pre[2]a[0]a[1]a[2]⋯pre[n]k0∑na[k]通过递推公式可快速推导原数组任意区间 0下标包含两端的元素和p r e [ r ] − p r e [ l − 1 ] pre[r] - pre[l-1]pre[r]−pre[l−1]。特殊地当l 0 l0l0时区间和直接等于p r e [ r ] pre[r]pre[r]。经典模板题题目描述给定长度为x xx的数组a aa以及n nn次区间查询每次给出区间[ l , r ] [l, r][l,r]求数组第l ll项到第r rr项的区间和逐行输出每次查询结果。输入格式第一行x , n x, nx,n数组长度、查询次数第二行a 1 , a 2 , … , a x a_1, a_2, \dots, a_xa1,a2,…,ax数组元素后续n nn行每行两个数l i , r i l_i, r_ili,ri查询区间数据范围0 ≤ l ≤ r ≤ x ≤ 10 5 0 \le l \le r \le x \le 10^50≤l≤r≤x≤1050 n ≤ 10 5 0 \lt n \le 10^50n≤105代码模板代码路径1/prefix_sum.cpp#includebits/stdc.husingnamespacestd;constintmaxn1e510;inta[maxn],pre[maxn];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intx,n;cinxn;// 读入原数组for(inti0;ix;i){cina[i];}// 预处理前缀和数组pre[0]a[0];for(inti1;ix;i){pre[i]pre[i-1]a[i];}// 处理n次区间查询intl,r;for(inti0;in;i){cinlr;// 适配0下标区间求和公式if(l0)coutpre[r]\n;elsecoutpre[r]-pre[l-1]\n;}return0;}1.1.2 差分算法差分算法是区间批量修改专用的高效预处理算法核心场景为对数组多次执行「区间统一加/减固定数值」的操作最后输出修改后的完整数组。暴力区间修改的时间复杂度为O ( m ⋅ n ) O(m \cdot n)O(m⋅n)大数据量下极易超时差分算法通过预处理差分数组将整体复杂度优化至O ( x q ) O(xq)O(xq)是区间批量更新题型的最优解。算法核心简述差分是前缀和的逆运算。基于原数组a aa0下标构建差分数组d i f f diffdiff数组元素对应规则如下d i f f [ 0 ] a [ 0 ] d i f f [ 1 ] a [ 1 ] − a [ 0 ] d i f f [ 2 ] a [ 2 ] − a [ 1 ] ⋯ d i f f [ i ] a [ i ] − a [ i − 1 ] ( i ≥ 1 ) diff[0] a[0] \\ diff[1] a[1] - a[0] \\ diff[2] a[2] - a[1] \\ \cdots \\ diff[i] a[i] - a[i-1] \quad (i \ge 1)diff[0]a[0]diff[1]a[1]−a[0]diff[2]a[2]−a[1]⋯diff[i]a[i]−a[i−1](i≥1)核心操作原理对原数组区间[ l , r ] [l, r][l,r]统一增加数值q qq仅需对差分数组执行两步操作d i f f [ l ] q diff[l] qdiff[l]q区间起点生效后续所有元素累加qd i f f [ r 1 ] − q diff[r1] - qdiff[r1]−q区间终点后一位抵消保证区间外元素不受影响所有区间修改完成后对d i f f diffdiff数组求一次前缀和即可还原得到修改后的原数组。手动推演示例设原数组a { 1 , 5 , 3 , 7 , 8 , 2 , 4 } a \{1,5,3,7,8,2,4\}a{1,5,3,7,8,2,4}构建初始差分数组d i f f { 1 , 4 , − 2 , 4 , 1 , − 6 , 2 } diff \{1,4,-2,4,1,-6,2\}diff{1,4,−2,4,1,−6,2}。执行操作对区间[ 2 , 4 ] [2,4][2,4]0下标所有元素加3。差分更新d i f f [ 2 ] 3 diff[2] 3diff[2]3、d i f f [ 5 ] − 3 diff[5] - 3diff[5]−3更新后d i f f { 1 , 4 , 1 , 4 , 1 , − 9 , 2 } diff \{1,4,1,4,1,-9,2\}diff{1,4,1,4,1,−9,2}前缀和还原数组得到新数组a { 1 , 5 , 6 , 10 , 11 , 2 , 4 } a \{1,5,6,10,11,2,4\}a{1,5,6,10,11,2,4}效果验证仅区间[ 2 , 4 ] [2,4][2,4]元素全部3其余元素保持不变符合预期。经典模板题题目描述给定长度为x xx的数组a aa进行n nn次区间修改操作每次操作将区间[ l , r ] [l, r][l,r]内所有元素增加数值q qq最终输出修改后的完整数组。输入格式第一行x , n x, nx,n第二行a 1 , a 2 , … , a x a_1, a_2, \dots, a_xa1,a2,…,ax后续n nn行每行三个数l i , r i , q i l_i, r_i, q_ili,ri,qi数据范围同前缀和模板题所有数据保证在 int 范围内。代码模板优化版代码路径1/difference.cpp#includebits/stdc.husingnamespacestd;constintmaxn1e55;inta[maxn],diff[maxn];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intx,n;cinxn;// 读入原数组for(inti0;ix;i){cina[i];}// 构建差分数组diff[0]a[0];for(inti1;ix;i){diff[i]a[i]-a[i-1];}// 批量处理区间修改操作for(inti0;in;i){intl,r,q;cinlrq;// 转换为0下标l--,r--;diff[l]q;// r1越界时无需抵消无后续元素不影响结果if(r1x)diff[r1]-q;}// 前缀和还原修改后的数组for(inti1;ix;i){diff[i]diff[i-1];}// 输出结果for(inti0;ix;i){coutdiff[i] ;}return0;}1.1.3 算法小结前缀和与差分是算法竞赛入门最基础、最实用的成对算法二者互为逆运算核心价值均为优化区间操作时间复杂度彻底解决暴力解法的超时问题。前缀和专攻多查询、无修改的区间求和场景一次预处理O(1)快速查询差分专攻多修改、最后查询的区间批量更新场景一次预处理高效完成批量修改两种算法逻辑简洁、代码量小是后续进阶算法二维前缀和、差分约束等的基础必须熟练掌握模板与核心原理。
