殷勤日记本

文章
5
资源
0
加入时间
3年0月21天

前缀和应用

文章目录一维前缀和二维前缀和定义:前缀和指一个数组的某下标之前的所有数组元素的和(包含其自身)。前缀和分为一维前缀和,以及二维前缀和。前缀和是一种重要的预处理,能够降低算法的时间复杂度。一维前缀和一维前缀和的公式:sum[i] = sum[i-1] + arr[i] ; sum是前缀和数组, arr是内容数组。拥有前缀和数组后, 我们可以在O(1)的时间复杂度内求出区间和。[i, j]的区间和公式: interval [i, j] = sum[j] - sum[i - 1]leetcode:和为