一、什么是前缀和
前缀和是一种预处理，用于降低查询时的时间复杂度。
举个例子：给定 n 个整数，然后进行 m 次询问，每次询问求一个区间内值的和。
如果用暴力写法，那每次询问都需要从区间左端点循环到区间右端点求和，时间复杂度较大。
这种时候就可以预先求出该数组的一维前缀和。
则 ans=s[R]-s[L-1] ，其中 L 和 R 是给定的区间。每次询问可直接输出答案，这样时间复杂度就降到了 O(N+M)
二、前缀和的实现
1、一维前缀和: 用数组preSum[i]表示nums的前i项和，i从1开始
preSum[ i ]=preSum[ i-1 ] + nums[ i ]
一般用于求区间[l,r]的值
ans = preSum[ r ] - preSum[ l-1 ]
2、二维前缀和: 用数组S[i][j]表示前i项，前j项的总和, i , j 从1开始
preSum[ i ][ j ] = preSum[ i-1 ][ j ] + preSum[ i ][ j-1 ] + nums[ i ][ j ] - preSum[ i-1 ][ j-1 ]
用于求子矩阵 (x1,y1) (x2,y2)的值
ans = preSum[ x2 ][ y2 ] - preSum[ x2 ][ y1-1 ] - preSum[ x1-1 ][ y2 ] + preSum[ x1-1 ][ y1-1 ]
内容来源于网络如有侵权请私信删除
文章来源: 博客园
原文链接: https://www.cnblogs.com/carrotbinbin1F/p/17317642.html
- 还没有人评论，欢迎说说您的想法！
客服
