文和906

分类

未归档(4) 项目笔记(5) 题解(103)

/ 注册

全部文章（共2篇）

题解 | #【模板】二维前缀和#

思路是用一个二维数组sum来储存(0, 0)到该点所形成的子矩阵中所有数的和。即sum.at(i).at(j)储存着以(0,0)(i,j)为反对角线的矩阵的所有元素的和。当要计算(x1, y1)与(x2, y2)所形成的矩阵中所有元素的和时，只需要用(0, 0)(x2, y2)这个大的矩形，减去(0...

C++ 前缀和动态规划

2021-10-28

0 517

题解 | #【模板】前缀和#

经典前缀和问题。具体做法是在接受输入数字创建数组时，同时创建一个前缀和数组sum，sum.at(i)维护的是数组前i+1项的和(0为首项)。在处理每一组l与r时，直接让前r项的和减去前l项的和在加上第l项的和即可。时间复杂度O(n)，空间复杂度O(n)。 #include <iostream&...

C++ 动态规划前缀和

2021-10-28

0 330