-
人工智能·前缀和
学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。
学习日记
一、什么是前缀和
前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素的和。
设b[]为前缀和数组，a[]为原数组，根据这句话可以得到前缀和的定义式和递推式：
定义式 递推式 一维前缀和 ![b[i]=\sum_{j=0}^{i}a[j]](https://1000bd.com/contentImg/2023/10/28/132301545.gif)
![b[i]=b[i-1]+a[i]](https://1000bd.com/contentImg/2023/10/28/132303267.gif)
二维前缀和 ![b[x][y]=\sum_{i=0}^{x}\sum_{j=0}^{y}a[i][j]](https://1000bd.com/contentImg/2023/10/28/132302219.gif)
![b[x][y]=b[x-1][y]+b[x][y-1]-b[x-1][y-1]+a[x][y]](https://1000bd.com/contentImg/2023/10/28/132300789.gif)
二、一维前缀和
根据上面的定义，我们可以很容易得到 sum[i] = sum[i-1] + a[i]
这样就可以得到前i个数的和。根据上述表达式我们可以以O(1)求出区间[i,j]的区间和
![sum[i,j]=b[j]-b[i-1]](https://1000bd.com/contentImg/2023/10/28/132301714.gif)
一般用于求区间[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]
-
相关阅读:
一篇文章全面解析Modbus协议中的消息帧
leetcode-判断是不是二叉搜索树-92
计算机网络(第四弹) --- TCP 套接字编程的通信模型及实现流程
【Mybatis编程：根据id查询相册数据详情】
Vue中组件间的传值（子传父，父传子）
uni-app:实现条件判断展示图片（函数判定+三目运算）
全球首个？竟在中国
XSS攻击
Java:Stream流
Java 服务 Docker 容器化最佳实践
- 原文地址：https://blog.csdn.net/m0_63794226/article/details/126687528