前缀和是一种用于快速计算数组中子数组和的技巧，它的核心思想是通过预先计算一个数组的前缀和数组，使得后续的区间和查询可以在常数时间内完成
#include <stdio.h>
#define MAX_SIZE 100// 1. 基本前缀和
void basicPrefixSum() {int arr[] = { 1, 2, 3, 4, 5 };int n = sizeof(arr) / sizeof(arr[0]);int prefix[MAX_SIZE] = { 0 };// 计算前缀和prefix[0] = arr[0];for (int i = 1; i < n; i++) {prefix[i] = prefix[i - 1] + arr[i];}// 打印原数组printf("原始数组：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");// 打印前缀和数组printf("前缀和数组：");for (int i = 0; i < n; i++) {printf("%d ", prefix[i]);}printf("\n");// 区间和查询示例int left = 1, right = 3;printf("区间[%d,%d]的和为：%d\n", left, right,prefix[right] - (left > 0 ? prefix[left - 1] : 0));
}// 2. 二维前缀和
void matrix2DPrefixSum() {int matrix[4][4] = {{1, 2, 3, 4},{5, 6, 7, 8},{9, 10, 11, 12},{13, 14, 15, 16}};int n = 4, m = 4;int prefix[4][4] = { 0 };// 计算二维前缀和prefix[0][0] = matrix[0][0];// 处理第一行for (int j = 1; j < m; j++) {prefix[0][j] = prefix[0][j - 1] + matrix[0][j];}// 处理第一列for (int i = 1; i < n; i++) {prefix[i][0] = prefix[i - 1][0] + matrix[i][0];}// 处理其余部分for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] -prefix[i - 1][j - 1] + matrix[i][j];}}// 打印原矩阵printf("\n原始矩阵：\n");for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {printf("%3d ", matrix[i][j]);}printf("\n");}// 打印前缀和矩阵printf("\n前缀和矩阵：\n");for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {printf("%3d ", prefix[i][j]);}printf("\n");}// 计算子矩阵和的示例 (2,2)到(3,3)的子矩阵int x1 = 1, y1 = 1, x2 = 2, y2 = 2;int subMatrixSum = prefix[x2][y2];if (x1 > 0) subMatrixSum -= prefix[x1 - 1][y2];if (y1 > 0) subMatrixSum -= prefix[x2][y1 - 1];if (x1 > 0 && y1 > 0) subMatrixSum += prefix[x1 - 1][y1 - 1];printf("\n子矩阵(%d,%d)到(%d,%d)的和为：%d\n",x1, y1, x2, y2, subMatrixSum);
}// 3. 差分数组（前缀和的逆运算）
void differenceArray() {int arr[] = { 1, 2, 3, 4, 5 };int n = sizeof(arr) / sizeof(arr[0]);int diff[MAX_SIZE] = { 0 };// 构建差分数组diff[0] = arr[0];for (int i = 1; i < n; i++) {diff[i] = arr[i] - arr[i - 1];}// 打印原数组printf("\n原始数组：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");// 打印差分数组printf("差分数组：");for (int i = 0; i < n; i++) {printf("%d ", diff[i]);}printf("\n");// 区间增加操作示例int left = 1, right = 3, val = 2;diff[left] += val;if (right + 1 < n) diff[right + 1] -= val;// 还原数组int result[MAX_SIZE] = { 0 };result[0] = diff[0];for (int i = 1; i < n; i++) {result[i] = result[i - 1] + diff[i];}printf("区间[%d,%d]增加%d后的数组：", left, right, val);for (int i = 0; i < n; i++) {printf("%d ", result[i]);}printf("\n");
}int main() {printf("1. 一维前缀和示例：\n");basicPrefixSum();printf("\n2. 二维前缀和示例：");matrix2DPrefixSum();printf("\n3. 差分数组示例：");differenceArray();return 0;
}运行结果：
