前缀和
220 字
1 分钟
前缀和
一维前缀和
- 核心思想
- 预处理：提前计算并储存数组的累加和，空间换时间；
- 查询优化：
O(n)->O(1);
- 构建前缀和数组
- 原数组
a[i],前缀和数组f[i];
f[0] = 0； f[i] = f[i-1] + a[i]； (1 ≤ i ≤n)- 区间和查询
- 查询闭区间
[l,r]的和
sum(l, r) = f[r] - f[l-1]；二维前缀和
- 核心思想
- 扩展一维思想到矩阵，快速求子矩阵的和
- 构建前缀和矩阵
- 原矩阵
a[m][n]，前缀和矩阵f[i][j]（（1，1）到（i，j）矩阵中所有元素和）;
f[0][j] = f[i][0] = 0; (边界置0) f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + a[i][j]；- 子矩阵查询
- 查询左上角（x1,y1）右下角（x2,y2）的子矩阵和；
sum = f[x2][y2] - f[x1-1][y2] - f[x2][y1-1] + f[x1-1][y1-1]；几何意义： 全区域-上侧区域-左侧区域+重叠减去的部分
- 时间复杂度
- 预处理O(nm);
- 单次查询O（1）；
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
字符串哈希
算法hash(s) = \sum{i=0}^{n-1} s[i] \times p^{n-i-1} \pmod{M}
2
Trie树（字典树）
算法定义：快速插入和查询字符串的数据结构 特点：利用字符串的公告前缀，将字符串组成树形结构 优势：相比map，可以高效查找公共前缀
3
差分
算法核心思想：把「区间 [L,R] 全部元素 +k」 时间优化：O(R−L+1) 降到 O(1) 差分数组 f 是原数组 a 的相邻元素之差序列 差分数组两种构造方式
4
查并集
算法维护“集合”的三件套：查询/合并/判同
5
离散化
算法空间换时间 时间复杂度O（n log n）sort排序
随机文章随机推荐