自定义投票网站怎么做,色彩设计网站,wordpress 主题 love,购物电商型网站怎么做1. 初始化扩展的二维前缀和数组
创建一个大小为 (rows 1) x (cols 1) 的二维前缀和数组#xff0c;其中 rows 和 cols 分别是原始数组的行数和列数。然后#xff0c;我们按以下方式填充这个数组#xff1a;
void initPrefixSum(vectorvectorint pr…1. 初始化扩展的二维前缀和数组
创建一个大小为 (rows 1) x (cols 1) 的二维前缀和数组其中 rows 和 cols 分别是原始数组的行数和列数。然后我们按以下方式填充这个数组
void initPrefixSum(vectorvectorint prefixSum, const vectorvectorint matrix) {int rows matrix.size();int cols matrix[0].size();// 初始化扩展了的前缀和数组prefixSum.resize(rows 1, vectorint(cols 1, 0));for (int i 1; i rows; i) {for (int j 1; j cols; j) {prefixSum[i][j] matrix[i - 1][j - 1] prefixSum[i - 1][j] prefixSum[i][j - 1]- prefixSum[i - 1][j - 1];}}
}2. 查询扩展的二维前缀和数组
由于我们的前缀和数组是扩展过的因此查询时的坐标也需要相应地调整。例如如果我们要查询原始数组中从 (x1, y1) 到 (x2, y2) 的子矩阵的和我们可以使用以下代码进行查询
int queryPrefixSum(const vectorvectorint prefixSum, int x1, int y1, int x2, int y2) {// 调整索引因为前缀和数组是扩展了的int sum prefixSum[x2 1][y2 1]- prefixSum[x1][y2 1]- prefixSum[x2 1][y1] prefixSum[x1][y1];return sum;
}注意在查询时我们需要对原始数组的索引进行加1处理因为我们的前缀和数组的起始索引是从1开始的而非0。这种方式简化了边界检查的需求因为所有的从原点到(x, y)的查询都可以直接使用上面的公式不再需要特别处理边界情况。
3.二维前缀和数组还原原始数组
前缀和数组是通过累加原始数组中的元素构建的因此还原原始数组实质上是一个逆累加或逆差分的过程。下面是一个实现这一过程的C函数示例。前缀和数组大小为 (rows 1) x (cols 1)并且我们希望从这个扩展的前缀和数组还原出原始的大小为 rows x cols 的数组
vectorvectorint restoreOriginalArray(const vectorvectorint prefixSum) {int rows prefixSum.size() - 1; // 原始数组的行数int cols prefixSum[0].size() - 1; // 原始数组的列数vectorvectorint originalArray(rows, vectorint(cols, 0));for (int i 1; i rows; i) {for (int j 1; j cols; j) {// 还原原始数组的值originalArray[i - 1][j - 1] prefixSum[i][j]- prefixSum[i - 1][j]- prefixSum[i][j - 1] prefixSum[i - 1][j - 1];}}return originalArray;
}在这个函数中我们遍历扩展后的前缀和数组使用类似于查询前缀和的反向过程来计算原始数组的每个元素。每个元素的值是由当前位置的前缀和减去其上方和左侧的前缀和再加上其左上角即前一个的前缀和得到的。这正好是构建前缀和时使用的逆过程。这个函数返回的 originalArray 就是还原后的原始二维数组。
4.完整代码附测试样例
#include iostream
#include vectorusing namespace std;// 初始化扩展的二维前缀和数组
void initPrefixSum(vectorvectorint prefixSum, const vectorvectorint matrix) {int rows matrix.size();int cols matrix[0].size();prefixSum.resize(rows 1, vectorint(cols 1, 0));for (int i 1; i rows; i) {for (int j 1; j cols; j) {prefixSum[i][j] matrix[i - 1][j - 1] prefixSum[i - 1][j] prefixSum[i][j - 1]- prefixSum[i - 1][j - 1];}}
}// 查询扩展的二维前缀和数组中子矩阵的和
int queryPrefixSum(const vectorvectorint prefixSum, int x1, int y1, int x2, int y2) {int sum prefixSum[x2 1][y2 1]- prefixSum[x1][y2 1]- prefixSum[x2 1][y1] prefixSum[x1][y1];return sum;
}// 从扩展的二维前缀和数组还原原始数组
vectorvectorint restoreOriginalArray(const vectorvectorint prefixSum) {int rows prefixSum.size() - 1;int cols prefixSum[0].size() - 1;vectorvectorint originalArray(rows, vectorint(cols, 0));for (int i 1; i rows; i) {for (int j 1; j cols; j) {originalArray[i - 1][j - 1] prefixSum[i][j]- prefixSum[i - 1][j]- prefixSum[i][j - 1] prefixSum[i - 1][j - 1];}}return originalArray;
}int main() {vectorvectorint matrix {{1, 2, 3},{4, 5, 6},{7, 8, 9}};vectorvectorint prefixSum;initPrefixSum(prefixSum, matrix);cout Prefix Sum Array: endl;for (const auto row : prefixSum) {for (int val : row) {cout val ;}cout endl;}int sum queryPrefixSum(prefixSum, 1, 1, 2, 2); // 查询从(1, 1)到(2, 2)的子矩阵的和cout Queried sum: sum endl;vectorvectorint restoredArray restoreOriginalArray(prefixSum);cout Restored Original Array: endl;for (const auto row : restoredArray) {for (int val : row) {cout val ;}cout endl;}return 0;
}
