贡献者: 有机物
前缀和算法分为一维和二维,一维前缀和可以很快速的求序列中某一段的和。而二维前缀和可以快速求一个矩阵中某个子矩阵的和(以下讲的是以
一维前缀和的朴素做法是一个 for
循环求和,时间复杂度为:
而前缀和的时间复杂度为:预处理
一维前缀和:
预处理:
如何预处理?
即:
如何求答案?
还有要注意的是
朴素代码
前缀和
二维前缀和的朴素做法是两重循环暴力求和。时间复杂度为:
而二维前缀和的时间复杂度为
二维前缀和:
预处理:
如何预处理?
在预处理
即:
如何求答案?
即:
二维前缀和可能有点抽象,可以根据几张图片来对二维前缀和有个更好的理解。
求前缀和的公式类似推导预处理的过程。
朴素代码
二维前缀和代码:
友情链接: 超理论坛 | ©小时科技 保留一切权利