IT 面试题库

什么是前缀和(Prefix Sum)?如何用它 O(1) 求出任意区间的和?一维与二维有何区别?

中级简答题算法工程师Java后端工程师前缀和区间求和二维前缀和差分

题目

考察点:前缀和数组 pre[i]=arr[0..i-1] 的构造与查询 sum(l,r)=pre[r+1]-pre[l];把每次区间求和从 O(n) 降到 O(1);二维前缀和的容斥公式。属简答题。

参考答案

内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 79 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

要点:

pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1];

任意子矩阵和同样用四角容斥 O(1) 取出,常用于图像/网格题。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题