第四章 前缀和，差分

目录

1 前缀和

1.1 什么是前缀和？

1.2 前缀和的作用

注意事项：

1.3 一维前缀和

1.3.1 代码模板

1.3.2 例题

分析： 

 代码：

1.4 二维前缀和

 1.4.1 代码模板

2 差分

2.1 什么是差分？

2.2 差分的作用

注意事项：

 2.3 一维差分

2.3.1 代码模板

 2.4 二维差分

2.4.1 代码模板

3 前缀和与差分比较

4 例题

 蓝桥杯省赛 3514 子串简写

分析：

代码：

 蓝桥杯省赛 3533 棋盘

分析：

代码：

1 前缀和

1.1 什么是前缀和？

前缀和概念源于数列知识，其核心思想是将数列的前n项和视为一个新的数组，这个数组即被称为前缀和数组。通过前缀和数组，我们可以高效地处理与数列部分和相关的计算问题

1.2 前缀和的作用

前缀和是求解区间和的高效工具。其预处理过程的时间复杂度为O(n)，即遍历一次原数组即可得到前缀和数组。一旦前缀和数组构建完成，查询任意区间和的时间复杂度可降至O(1)。

然而，需要注意的是，前缀和算法适用于数组元素不变的情况。若数组频繁变动，则需重新构建前缀和数组，这将再次引入O(n)的时间复杂度。

注意事项：

• 从数组的第一个元素开始遍历以构建前缀和数组。（建议角标从1开始）
• 考虑到大数问题，建议使用long long类型存储前缀和及计算结果

1.3 一维前缀和

一维前缀和的本质是在一维坐标轴上计算线段长度（即区间和）。

1.3.1 代码模板

• a[i] 为原数组，
  标签：前缀,int,差分,数组,区间,简写,第四章
  From： https://blog.csdn.net/2302_81681363/article/details/141022056