C++基础算法前缀和和差分篇

**C++基础算法篇：前缀和和差分**

在计算机科学中，前缀和（Prefix Sum）和差分（Difference）是两个非常重要的概念，它们广泛应用于数据处理、分析和可视化等领域。在本文中，我们将介绍这些基本算法，并提供C++代码示例。

### 前缀和前缀和是一种将原始数据转换为新数据的方法，新数据中的每个元素是原始数据中相应位置元素与其左边所有元素之和。例如，如果我们有一个数组 `[1,2,3,4,5]`，则其前缀和数组为 `[1,3,6,10,15]`。

#### 前缀和算法要计算前缀和，我们可以使用以下公式：

cpp前缀和[i] = 原始数据[0] + 原始数据[1] + ... + 原始数据[i]

cpp#include <iostream>
using namespace std;

int main() {
 int arr[] = {1,2,3,4,5};
 int n = sizeof(arr) / sizeof(arr[0]);
 // 前缀和数组 int prefix_sum[n];
 prefix_sum[0] = arr[0];
 for (int i =1; i < n; i++) {
 prefix_sum[i] = prefix_sum[i -1] + arr[i];
 }
 cout << "原始数据：";
 for (int i =0; i < n; i++) {
 cout << arr[i] << " ";
 }
 cout << endl;
 cout << "前缀和数组：";
 for (int i =0; i < n; i++) {
 cout << prefix_sum[i] << " ";
 }
 cout << endl;
 return0;
}

cpp差分[i] = 原始数据[i] - 原始数据[i +1]

cpp#include <iostream>
using namespace std;

int main() {
 int arr[] = {1,2,3,4,5};
 int n = sizeof(arr) / sizeof(arr[0]);
 // 差分数组 int difference[n -1];
 for (int i =0; i < n -1; i++) {
 difference[i] = arr[i +1] - arr[i];
 }
 cout << "原始数据：";
 for (int i =0; i < n; i++) {
 cout << arr[i] << " ";
 }
 cout << endl;
 cout << "差分数组：";
 for (int i =0; i < n -1; i++) {
 cout << difference[i] << " ";
 }
 cout << endl;
 return0;
}