人工智能·前缀和

在这里插入图片描述

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。

学习日记

一、什么是前缀和

前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素的和。

设b[]为前缀和数组，a[]为原数组，根据这句话可以得到前缀和的定义式和递推式：

定义式递推式
一维前缀和 $b[i]=\sum_{j=0}^{i}a[j]$
二维前缀和 $b[x][y]=\sum_{i=0}^{x}\sum_{j=0}^{y}a[i][j]$

二、一维前缀和

根据上面的定义，我们可以很容易得到 sum[i] = sum[i-1] + a[i] 　　

这样就可以得到前i个数的和。根据上述表达式我们可以以O(1)求出区间[i,j]的区间和

一般用于求区间[L,R]之间元素的和:

ans[1]=ans[0]+q[1]

ans[2]=ans[1]+q[2]

……… ………

ans[i]=ans[i-1]+q[i]

[L,R]之间元素的和tmp=ans[R]-ans[L-1]

三、二维前缀和练习

原数组q[ ][ ]

0

1

2

3

4

5

6

7

8

9

1

1

2

1

0

-1

0

2

0

0

2

1

0

0

1

2

1

1

0

0

3

2

1

1

3

1

-1

0

0

0

4

1

1

-1

0

-1

1

1

0

0

5

1

1

2

1

3

1

4

0

0

6

0

0

0

0

0

0

0

0

0

7

0

0

0

0

0

0

0

0

0

前缀和数组ans[ ][ ]

0

1

2

3

4

5

6

7

8

1

1

3

4

4

3

2

2

4

5

6

7

3

4

7

9

13

15

4

5

(i-1,j)

5

6

(i,j-1)

(i , j)

6

7

求ans[ ][ ] ans[I,j]=ans[i-1,j]+ans[I,j-1]-ans[i-1][j-1]+q[i][j]:

0

1

2

3

4

5

6

7

8

1

2

(x1-1,y1-1)

(x1-1,y2)

3

(x1,y1)

4

5

(x2,y1-1)

(x2,y2)

6

7

求指定矩形内元素和：

左上（x1,y1）右下(x2,y2)

tmp=ans[x2][y2]-ans[x2][y1-1]-ans[x1-1][y2]+ans[x1-1][y1-1]

相关阅读:
influxdb 2.*版本与1.*版本区别
C++从零开始(day47)——set，map学习使用
Teamcity NuGet Installer
4.4 Go语言中的单元测试
从四个角度全面认识 ChatGPT
freeswitch 变声模块mod_soundtouch、mod_ladspa
广和通&高通物联网技术开放日成功举办
DP读书：《openEuler操作系统》（四）鲲鹏处理器
浅谈c/c++中main(),int main(),void main(),int main(void)四者之间的区别
SpringBoot 配置文件这样加密，才足够安全！

原文地址：https://blog.csdn.net/m0_63794226/article/details/126687528

	定义式	递推式
一维前缀和	$b[i]=\sum_{j=0}^{i}a[j]$
二维前缀和	$b[x][y]=\sum_{i=0}^{x}\sum_{j=0}^{y}a[i][j]$

0	1	2	3	4	5	6	7	8	9
1	1	2	1	0	-1	0	2	0	0
2	1	0	0	1	2	1	1	0	0
3	2	1	1	3	1	-1	0	0	0
4	1	1	-1	0	-1	1	1	0	0
5	1	1	2	1	3	1	4	0	0
6	0	0	0	0	0	0	0	0	0
7	0	0	0	0	0	0	0	0	0

0	1	2	3	4	5	6	7	8	9
1	1	2	1	0	-1	0	2	0	0
2	1	0	0	1	2	1	1	0	0
3	2	1	1	3	1	-1	0	0	0
4	1	1	-1	0	-1	1	1	0	0
5	1	1	2	1	3	1	4	0	0
6	0	0	0	0	0	0	0	0	0
7	0	0	0	0	0	0	0	0	0

0	1	2	3	4	5	6	7	8	9
1	1	2	1	0	-1	0	2	0	0
2	1	0	0	1	2	1	1	0	0
3	2	1	1	3	1	-1	0	0	0
4	1	1	-1	0	-1	1	1	0	0
5	1	1	2	1	3	1	4	0	0
6	0	0	0	0	0	0	0	0	0
7	0	0	0	0	0	0	0	0	0