前缀和（仅代码部分付费）

bangbang-ande · 发表于 2023-7-19 09:32:01

前缀和，专门用于解决区间和问题。这是静态区间问题的最轻松想得到的方法。这种数据结构非常容易构建，但是可变动性并不强，我们今天就来看看这种数据结构……

我们依旧使用一个常规的数组进行演示：

数组	0	1	2	3	4	5
a[]	0	2	5	17	1	9

首先我们先创建一个新的数组b[]，作为前缀和的数据结构进行存储。以及我们再创建一个变量ans（作为累加的变量），此时的ans设为0。

数组	0	1	2	3	4	5
a[]	0	2	5	17	1	9
b[]

接着从左到右遍历，遍历到第1个位置上的2，将2加入ans，然后存入b数组的第1个位置
然后往下遍历到第2个位置的5，将5加入ans，此时ans为2+5=7，然后存入b数组的第2个位置。之后步骤同理：

数组	1	2	3	4	5
a[]	2	5	17	1	9
b[]	2	7	24	25	34

那么这就是加完之后的样子，大家会发现，b数组的每一位其实就是a数组的前几位的和。（比如b[3]=a[1]+a[2]+a[3]）所以才叫前缀和。所以前缀和其实就是前几位的和……

然后我们来说说前缀和的最大作用：快速计算区间和
计算区间和的方法很简单，比如说以上面例子为例：我需要计算[2,5]的区间的和，那么我只需要用b[5]-b[1]就可以得到结果了。此时相信很多人都不理解，为什么呢？这就不得不提到数学的精妙之处了。
∵b[5]=a[1]+a[2]+a[3]+a[4]+a[5]
b[1]=a[1]
∴b[5]-b[1]=a[1]+a[2]+a[3]+a[4]+a[5]-a[1]
=a[2]+a[3]+a[4]+a[5]
大家换做其余的数字也是同理，在[x, y]区间的和就是b[y]-b[x-1]的值。

它的时间复杂度也很好求，就O(1)嘛……

但是前缀和的最优作用也只有在求区间和了，如果此时有其余的功能，那么它的实用性就很低了……
其余功能一：在区间中加上一个数，并不是在数组中加上一个数，我们是直接在前缀和中加入……，那根据前缀和的定义，加入的方式就很特殊了，我们依旧用以上面的例子说明：

数组	0	1	2	3	4	5
b[]	0	2	7	24	25	34

我们假设要在区间[1,4]加上一个数4，那么我们的做法应该是这样子的：
首先循环1~4个位置，在第一个位置的b[]加上4，第二个数就要加上8，第三个就要加12，直到第四个位置以此类推……然后继续从第四个位置往后循环到结尾，不过不需要叠加了，只需要一直加上16即可。
最后变化如下：

数组	0	1	2	3	4	5
b[]	0	6	15	36	41	50

解释一下上面的做法：
位置1加4；位置2则先加了位置1的4，自己再加4（因为使用的是前缀和的数据结构）；位置3也是同理，直到区间内都同理。但是到区间之后的位置就不是这样了，因为自身不用+4，所以只需要加上前面区间中加过的4即可……

时间复杂度为O(n)。
其余功能二：求某段区间的最大值……这个的做法很简单，我们刚刚知道区间和的求法，那么这里找数组中第i个数的方法很简单了，就是a[\i]（误），其实应该是b[\i]-b[i-1]（理由是我们的加法程序没有同步在数组中），然后我们用普通数组那样循环找最大即可……
（这里用了\是为了防止触发斜体样式）

时间复杂度为O(n)，可见时间很慢很慢……多几次操作就可以达到很久的运行时长了……
当然还有其它的功能，在某段区间乘上一个数也是可以的，大致方法跟加法基本一致……还有什么样的功能其实都差不多了，就大约可以归为这三类

购买主题 已有 1 人购买 本主题需向作者支付 2 鱼币 才能浏览

jasonpzc · 发表于 2023-7-19 10:55:24

本帖最后由 jasonpzc 于 2023-7-19 10:56 编辑

账号		自动登录	找回密码
密码			立即注册

[技术交流] 前缀和（仅代码部分付费）