给我一段c++封装的二维前缀和模板
时间: 2024-09-17 19:01:45 浏览: 32
C@C++复习--草稿1
在C++中,我们可以使用模板来创建一个通用的二维数组(如矩阵)的前缀和结构。前缀和是一种数据结构,用于快速查询数组元素之和,特别是对于区间和的问题。以下是一个简单的模板示例,用于计算二维数组每个子区域的累加和:
```cpp
template <typename T>
class TwoDimensionalPrefixSum {
private:
std::vector<std::vector<T>> prefixSum; // 二维前缀和数组
public:
// 构造函数,初始化所有元素为0
TwoDimensionalPrefixSum(std::vector<std::vector<T>>& matrix) : prefixSum(matrix.size()) {
for (std::size_t i = 0; i < matrix.size(); ++i) {
prefixSum[i].resize(matrix[i].size());
for (std::size_t j = 0; j < matrix[i].size(); ++j) {
if (i == 0 && j == 0) {
prefixSum[i][j] = matrix[i][j];
} else {
prefixSum[i][j] = matrix[i][j] + prefixSum[i - 1][j - 1];
}
}
}
}
// 获取指定范围的累加和
T getSum(std::size_t rowStart, std::size_t colStart, std::size_t rowEnd, std::size_t colEnd) const {
if (rowStart > rowEnd || colStart > colEnd) return 0;
return prefixSum[rowEnd][colEnd] - (rowStart > 0 ? prefixSum[rowStart - 1][colEnd] : 0) -
(colStart > 0 ? prefixSum[rowEnd][colStart - 1] : 0) +
(rowStart > 0 && colStart > 0 ? prefixSum[rowStart - 1][colStart - 1] : 0);
}
};
// 使用示例
int main() {
std::vector<std::vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
TwoDimensionalPrefixSum<int> sumMatrix(matrix);
int sum1 = sumMatrix.getSum(0, 0, 2, 2); // 返回15(1+2+3)
int sum2 = sumMatrix.getSum(1, 1, 2, 2); // 返回10(4+5)
return 0;
}
```
阅读全文