一、算法说明

Floyd 算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与 Dijkstra 算法类似。 该算法名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

Floyd 算法是解决多源最短路径问题的经典动态规划算法，它能在 O(n^3) 时间复杂度内求出图中所有节点对之间的最短路径，支持有向和无向图，支持权值为负数的情况（负权边），但不支持负权环（若图中存在负权环，环上节点的最短路径无意义）。

二、核心思想

1.邻接矩阵(二维数组)dist 储存路径，数组中的值开始表示点点之间初始直接路径，最终是点点之间的最小路径，有两点需要注意的， 第一是如果没有直接相连的两点那么默认为一个很大的值(不要因为计算溢出成负数)，第二是自己和自己的距离要为 0。

2 .从第 1 个到第 n 个点依次加入松弛计算，每个点加入进行试探枚举是否有路径长度被更改(自己能否更新路径)。顺序加入(k 枚举)松 弛的点时候，需要遍历图中每一个点对(i,j 双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化，如果发生改变(变 小)，那么两点(i,j)距离就更改。

3 .重复上述直到最后插点试探完成。 其中第 2 步的状态转移方程为: 

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])

其中 dp[a][b]的意思可以理解为点 a 到点 b 的最短路径,所以 dp[i][k]的意思可以理解为 i 到 k 的最短路径 dp[k][j]的意思为 k 到 j 的最短 路径. 

三、算法步骤

1. 1.初始化：

• 若 i == j，dp[i][j] = 0（自身到自身距离为 0）；

• 若 i 和 j 之间有直接边，dp[i][j] = 边权；

• 若 i 和 j 之间无直接边，dp[i][j] = 无穷大（如 0x3f3f3f3f）。

• 构建邻接矩阵 dist，其中 dp[i][j] 表示节点 i 到 j 的初始距离：

2. 2.状态转移：

   遍历所有可能的中间节点 k（1~n），再遍历所有起点 i 和终点 j，执行松弛操作：

    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

1. 3.结果输出：

   最终 dist[i][j] 即为 i 到 j 的最短路径长度；若仍为无穷大，说明 i 无法到达 j。

四、过程图解

我们使用以下有向图（顶点数为 4）：

顶点: 0, 1, 2, 3  边与权值:  0 ->1: 3  0 ->2： 6  1 ->2：-2  2 ->3： 2  3 ->0： 1

注意：图中存在负权边（1->2: -2 )

初始矩阵D(0)

k = 0（允许经过顶点 0 作为中间点）

更新规则：对于所有 i, j，检查 D[i][0] + D[0][j] 是否小于 D[i][j]。

• i=1, j=2: D[1][0]=INF, 不加。

• i=3, j=1: D[3][0]=1, D[0][1]=3, 和=4，原来 D[3][1]=INF → 更新为 4。

• i=3, j=2: D[3][0]=1, D[0][2]=6, 和=7，原来 INF → 更新为 7。

• 其他无更新。

  
  
  

结果D(1)

k = 1（允许经过顶点 0,1 作为中间点）

• i=0, j=2: D[0][1]=3, D[1][2]=-2, 和=1，原来 D[0][2]=6 → 更新为 1。

• i=0, j=3: D[0][1]=3, D[1][3]=INF → 无更新。

• i=2, j=0: D[2][1]=INF → 无。

• i=3, j=2: D[3][1]=4, D[1][2]=-2, 和=2，原来 D[3][2]=7 → 更新为 2。

• i=3, j=0: D[3][1]=4, D[1][0]=INF → 无。

  
  
  

结果D(2)

k = 2（允许经过顶点 0,1,2 作为中间点）

• i=0, j=3: D[0][2]=1, D[2][3]=2, 和=3，原来 INF → 更新为 3。

• i=1, j=3: D[1][2]=-2, D[2][3]=2, 和=0，原来 INF → 更新为 0。

• i=1, j=0: D[1][2]=-2, D[2][0]=INF → 无。

• i=3, j=0: D[3][2]=2, D[2][0]=INF → 无。

• i=3, j=1: D[3][2]=2, D[2][1]=INF → 无。

  
  
  

结果D(3)

k = 3（允许经过所有顶点作为中间点）

• i=0, j=0: D[0][3]=3, D[3][0]=1, 和=4 > 0，不更新。

• i=0, j=1: D[0][3]=3, D[3][1]=4, 和=7 > 3，不更新。

• i=0, j=2: D[0][3]=3, D[3][2]=2, 和=5 > 1，不更新。

• i=1, j=0: D[1][3]=0, D[3][0]=1, 和=1，原来 INF → 更新为 1。

• i=1, j=1: 无意义。

• i=1, j=2: D[1][3]=0, D[3][2]=2, 和=2 > -2，不更新。

• i=2, j=0: D[2][3]=2, D[3][0]=1, 和=3，原来 INF → 更新为 3。

• i=2, j=1: D[2][3]=2, D[3][1]=4, 和=6，原来 INF → 更新为 6。

• i=3, j=0: 已是最优。

• i=3, j=1: 已是最优。

• i=3, j=2: 已是最优。

D(4)

4. 结果解释

最终矩阵给出了所有点对的最短路径长度：

• 0 → 2 最短路径是 0→1→2，长度 3 + (-2) = 1。

• 1 → 0 最短路径是 1→3→0，长度 0 + 1 = 1。

• 2 → 1 最短路径是 2→3→0→1，长度 2 + 1 + 3 = 6。

• 图中包含负权边（1→2 权重 -2），但没有负权回路，因此所有最短路径都有确定值。

五、参考代码

1.基本版本

#include <iostream>  #include <climits>  using namespace std;  const int MAXN = 100;  // 最大节点数  const int INF = 1e9;  // 表示无穷大  // Floyd算法  void floyd(int n, int dist[MAXN][MAXN]) {      // Floyd算法核心      for (int k = 0; k < n; k++) {          for (int i = 0; i < n; i++) {              if (dist[i][k] == INF) continue;  // 跳过无效路径              for (int j = 0; j < n; j++) {                  if (dist[k][j] == INF) continue;  // 跳过无效路径                  if (dist[i][j] > dist[i][k] + dist[k][j]) {                      dist[i][j] = dist[i][k] + dist[k][j];                  }              }          }      }  }    // 示例使用  int main() {      int n,m,w;  // 节点数,边，权重       int dist[MAXN][MAXN];      n=4;//假设4个顶点       // 初始化距离矩阵      for (int i = 0; i < n; i++) {          for (int j = 0; j < n; j++) {              if (i == j) {                  dist[i][j] = 0;              } else {                  dist[i][j] = INF;              }          }      }            // 添加边（测试输入）       dist[0][1] = 3;      dist[0][2] = 6;      dist[1][2] = -2;      dist[2][3] = 2;      dist[3][0] = 1;        //     题目输入   //     for (int i = 0; i < m; ++i) {  //        int u, v;  //        int w;  //        cin >> u >> v >> w;  //        dist[u][v] = min(dist[u][v], w);   //		//有向边；无向边需加 dist[v][u] = min(dist[v][u], w)  //    }            // 运行Floyd算法      floyd(n, dist);            // 输出结果      cout << "最短路径：" <<endl;          for (int i = 0; i < n; ++i) {          for (int j = 0; j < n; ++j) {              cout << i << "→" << j << "：";              if (dist[i][j] == INF) cout << "INF"<<endl;              else cout << dist[i][j] <<endl ;          }          cout << endl;      }      return 0;  }

2.带路径的

在上一个版本的基础上增加前驱矩阵，支持还原任意节点对的最短路径

#include <iostream>  #include <climits>  using namespace std;   const int MAXN = 100;  const int INF = 1e9;    // Floyd算法  void floyd(int n, int dist[MAXN][MAXN], int path[MAXN][MAXN]) {      // 初始化路径矩阵      for (int i = 0; i < n; i++) {          for (int j = 0; j < n; j++) {              if (i == j || dist[i][j] == INF) {                  path[i][j] = -1;  //不能走               } else {                  path[i][j] = i;  // 初始时，i到j的直接前驱是i              }          }      }            // Floyd算法核心      for (int k = 0; k < n; k++) {          for (int i = 0; i < n; i++) {              if (dist[i][k] == INF) continue;              for (int j = 0; j < n; j++) {                  if (dist[k][j] == INF) continue;                  if (dist[i][j] > dist[i][k] + dist[k][j]) {                      dist[i][j] = dist[i][k] + dist[k][j];                      path[i][j] = path[k][j];  // 更新路径                  }              }          }      }  }    // 递归打印路径  void print_path(int i, int j, int path[MAXN][MAXN]) {      if (path[i][j] == -1) {          cout << "无路径";          return;      }            if (i == j) {          cout << i;      } else if (path[i][j] == i) {           cout << i << " -> " << j;      } else {          print_path(i, path[i][j], path);          cout << " -> " << j;      }  }    // 示例使用  int main() {      int n,m,w; //节点，边，权重       n=4;//假设4个节点       int dist[MAXN][MAXN];      int path[MAXN][MAXN];      // 初始化      for (int i = 0; i < n; i++) {          for (int j = 0; j < n; j++) {              if (i == j) {                  dist[i][j] = 0;              } else {                  dist[i][j] = INF;              }          }      }             // 添加边（测试输入）       dist[0][1] = 3;      dist[0][2] = 6;      dist[1][2] = -2;      dist[2][3] = 2;      dist[3][0] = 1;            // 运行算法      floyd(n, dist, path);            // 输出结果      cout << "从0到3的最短路径：" << endl;      cout << "距离: " << dist[0][3] << endl;      cout << "路径: ";      print_path(0, 3, path);      cout << endl;      return 0;  }

六、负权环问题

负权环（回路）

Floyd算法可以处理负权边，但是不能处理负权回路。

什么是负权回路？

负权回路是有向图中从某节点出发回到自身的路径，所有边的权值之和为负数（无向图中负权边直接构成负环）。例如路径 1→2→3→1 权值和为 -2，则该回路为负环。

原因是：负权回路会导致路径长度可以无限减小，破坏了 “最短路径存在且有限” 的前提，进而让算法的核心逻辑（松弛操作）失去意义。

比如下面的例子:

我们使用以下有向图（顶点数为 4）：

顶点: 0, 1, 2, 3  边与权值:  0 -> 1: 3  0 -> 3: 5  1 -> 2: -2  2 -> 3: 1  3 -> 1: -1

初始距离矩阵 D⁽⁰⁾

我们用 D[i][j] 表示从 i 到 j 的当前最短距离估计。INF 表示不可达（这里用 ∞ 表示）。

解释：

• 对角线为 0（自己到自己的距离）。

• 有直接边的填入权值（如 D[0][1]=3）。

• 无直接边的填入 ∞。

一、核心思想

1. 贪心策略：每次从未确定最短路径的节点中，选择距离源节点最近的节点，将其标记为 “已确定”；

2. 松弛操作：以该节点为中介，更新其邻接节点到源节点的距离；

3. 重复上述步骤，直到所有节点都被标记为 “已确定”。

二、算法步骤（以无向带权图为例）

1. 初始化：

• 距离数组 dist[]：dist[s] = 0（源节点到自身距离为 0），其余节点 dist[i] = ∞（无穷大）；

• 标记数组 visited[]：所有节点初始为 false（未确定最短路径）；

• 优先队列（小顶堆）：存储 (当前距离, 节点)，初始入队 (0, s)。（朴素解法不使用优先队列）

2. 迭代求解：

• 取出优先队列中距离最小的节点 u，若 u 已访问则跳过；

• 标记 u 为已访问（visited[u] = true）；

• 遍历 u 的所有邻接节点 v，若 dist[v] > dist[u] + 权值(u,v)，则更新 dist[v] = dist[u] + 权值(u,v)，并将 (dist[v], v) 入队；

3. 终止条件：优先队列为空，此时 dist[] 数组存储源节点到所有节点的最短路径。（朴素解法不使用优先队列）

一、定义

区间DP是动态规划的一种特殊形式，主要用于解决涉及区间操作的问题，比如合并区间、分割区间、区间匹配等。

其核心思想是通过枚举区间的划分点，将大区间的问题分解为小区间的子问题，逐步求解并保存中间结果。

二、基本特征

• 问题定义：通常涉及一个序列或区间，如数组、字符串等。

• 状态表示：一般用 dp[i][j] 表示区间 [i, j] 的最优解。

• 转移方程：通过枚举区间内的某个分割点 k，将 [i, j] 拆分为 [i, k] 和 [k+1, j]，然后合并子问题的解。

• 初始化：通常 dp[i][i] 表示单个元素的最优解（如 dp[i][i] = 0 或 dp[i][i] = cost[i]）。

• 遍历顺序：一般采用区间长度从小到大的顺序计算，确保子问题先被求解。

三、区间DP模板

for (int len = 1; len <= n; len++) {          // 枚举区间长度      for (int i = 0; i + len - 1 < n; i++) {   // 枚举起点i          int j = i + len - 1;                  // 计算终点j          if (len == 1) {                       // 初始化              dp[i][j] = ...;              continue;          }          for (int k = i; k < j; k++) {         // 枚举分割点k              dp[i][j] = min/max(dp[i][j], dp[i][k] + dp[k+1][j] + cost);          }      }  }

四、例题：石子合并

题目：【题解】石子合并 - 青少年编程知识记录

问题描述：有 n 堆石子排成一排，每次只能合并相邻的两堆，合并的代价是两堆石子的总数。求将所有石子合并成一堆的最小总代价。

输入: stones = [3, 1, 2, 4]  输出: 20  解释:  1. 合并 [1, 2] → 代价=3, 剩余 [3, 3, 4]  2. 合并 [3, 3] → 代价=6, 剩余 [6, 4]  3. 合并 [6, 4] → 代价=10, 总代价=3+6+10=19

(1) 状态定义

• dp[i][j]：表示合并区间 [i, j] 的所有石子堆的最小总代价。

• 初始化：

• 如果 i == j（即区间长度为1），dp[i][j] = 0（因为不需要合并）。

• 否则 dp[i][j] = +∞（初始化为极大值，方便后续取最小值）。

(2) 状态转移方程

• 对于区间 [i, j]，枚举所有可能的分割点 k（i ≤ k < j），将其分成两个子区间：

• [i, k] 和 [k+1, j]。

• 合并这两个子区间的总代价是：

• dp[i][k]（合并 [i, k] 的代价）

• dp[k+1][j]（合并 [k+1, j] 的代价）

• sum(i, j)（当前合并的代价，即区间 [i, j] 的石子总重量）。

• 因此，状态转移方程为：

  $$dp[i][j]=\underset{i\le k<j}{\min }(dp[i][k]+dp[k+1][j]+\text{sum}(i,j))$$

(3) 计算顺序

• 按区间长度从小到大计算：

• 先计算所有长度为2的区间，再计算长度为3的区间，依此类推，直到计算整个区间 [0, n-1]。

• 前缀和优化：

• 为了快速计算 sum(i, j)，可以预先计算前缀和数组 prefix：

  $$\text{sum}(i,j)=\text{prefix}[j+1]-\text{prefix}[i]$$

一、基本思想

归并排序的核心思想是将两个已经有序的子序列合并成一个有序序列。整个过程分为两个主要步骤：

 1.分解：将待排序的序列不断二分，直到每个子序列只包含一个元素（此时自然有序） 

 2.合并：将两个有序的子序列合并为一个有序序列

注意1：若将两个有序表合并成一个有序表，称为2-路归并。

注意2：归并排序则类似于二叉树的后序遍历：它会持续划分区间，直到区间内元素有序，然后利用额外空间对元素进行排序，并将它们合并回原区间，直至整个序列有序。这个过程中，划分区间相当于达到树的最底层，而归并排序则相当于从树的底层开始向上遍历。

二、算法步骤

1.分解阶段：

• 将长度为n的序列分成两个长度为n/2的子序列

• 递归地对这两个子序列进行归并排序

• 直到子序列长度为1（此时已经有序）

2.合并阶段：

• 申请空间，大小为两个已排序子序列之和

• 设定两个指针，分别指向两个子序列的起始位置

• 比较两个指针所指的元素，选择较小的放入合并空间，并移动指针到下一位置

• 重复上一步直到某一指针超出子序列范围

• 将另一子序列的剩余元素直接复制到合并序列的末尾

动图如下：

三、时间复杂度

• 最优情况：O(n log n)

• 最坏情况：O(n log n)

• 平均情况：O(n log n)

归并排序的时间复杂度始终是O(n log n)，因为它总是将序列分成两半，需要进行log₂n次分解，每次合并操作的时间复杂度为O(n)。

四、空间复杂度

归并排序需要额外的空间来存储临时合并的数组，因此其空间复杂度为O(n)。

五、稳定性

归并排序是稳定的排序算法，因为在合并过程中，当两个元素相等时，可以保证左边的元素先被放入结果数组中。

六、优缺点

优点：

• 时间复杂度稳定为O(n log n)

• 适用于大规模数据排序

• 稳定排序算法

缺点：

• 需要额外的存储空间（非原地排序）

• 对于小规模数据排序效率可能不如简单排序算法

【题目描述】

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

【输入描述】

输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。

【输出描述】

输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。

【样例输入】

2	1

【样例输出】

0

一、单调栈

单调栈（Monotonic Stack）是一种特殊的栈结构，其核心思想是维护栈内元素的单调性（单调递增或单调递减）。单调栈通常用于解决与元素大小关系相关的问题，例如：

1. 找到数组中每个元素的下一个更大（或更小）元素。

2. 计算数组中每个元素左边或右边的第一个更大（或更小）元素。

3. 解决与区间最值相关的问题（如最大矩形面积）。

二、特点

1. 单调性：栈内元素始终保持单调递增或单调递减。

2. 操作规则：

   如果新元素满足单调性，直接压入栈。

如果新元素破坏了单调性，则弹出栈顶元素，直到满足单调性为止。

3. 时间复杂度：由于每个元素最多入栈和出栈一次，因此时间复杂度通常为O(n)

三、应用场景

1. 下一个更大元素：
   
   给定一个数组，找到每个元素的下一个更大元素。

2. 每日温度：
   
   给定一个温度数组，计算每天需要等待多少天才能遇到更高的温度。

3. 最大矩形面积：
   
   给定一个柱状图，计算其中最大的矩形面积。

4. 滑动窗口最大值：
   
   在滑动窗口中快速找到最大值。

四、步骤

以找到数组中每个元素的下一个更大元素为例：

1. 初始化：创建一个空栈和一个结果数组。

2. 遍历数组：

• 如果当前元素大于栈顶元素，则栈顶元素的下一个更大元素就是当前元素。

• 弹出栈顶元素，并更新结果数组。

• 重复上述过程，直到当前元素小于等于栈顶元素或栈为空。

• 将当前元素压入栈。

3. 处理剩余元素：遍历结束后，栈中剩余的元素没有下一个更大元素，将其结果设置为 -1。

一、定义

滑动窗口算法（Sliding Window Algorithm）是一种用于解决数组或字符串中子数组或子串问题的优化技术。它通过维护一个窗口（通常是数组或字符串的一个连续子区间），在遍历过程中动态调整窗口的起始和结束位置，从而高效地解决问题。

滑动窗口的核心思想是：

• 窗口大小固定：窗口的大小在滑动过程中保持不变。

• 窗口大小可变：窗口的大小根据条件动态调整。

二、使用场景

滑动窗口算法通常用于以下场景：

1. 1.子数组/子串问题：

• 求满足条件的最大或最小子数组/子串。

• 例如：最大子数组和、最小覆盖子串、最长无重复字符子串等。

2. 2.固定窗口大小问题：

• 例如：计算大小为 k 的子数组的平均值。

3. 3.优化暴力解法：

• 将时间复杂度从 O(n²) 优化到 O(n)。

三、示例

1.例题1：固定窗口大小

【题目描述】给定一个数组和一个整数 k，计算所有大小为 k 的子数组的平均值。

【题目分析】

（1） 什么是子数组？

• 子数组是数组中连续的一段元素。

• 例如，数组 [1, 3, 2, 6, -1] 的子数组包括 [1, 3, 2]、[3, 2, 6] 等。

（2）什么是大小为 k 的子数组？

• 大小为 k 的子数组是指长度为 k 的连续子数组。

• 例如，如果 k = 3，那么子数组的长度必须是 3。

（3）什么是子数组的平均值？

• 子数组的平均值是指子数组中所有元素的和除以子数组的长度。

• 例如，子数组 [1, 3, 2] 的平均值是 (1 + 3 + 2) / 3 = 2。

（4）问题的目标

• 对于数组中的每一个大小为 k 的子数组，计算其平均值，并返回所有平均值的集合。

【解题思路】

（1）暴力解法

• 遍历数组，对于每一个起始位置 i，计算从 i 到 i + k - 1 的子数组的和，然后除以 k 得到平均值。

• 时间复杂度：O(n * k)，其中 n 是数组的长度。

（2）滑动窗口优化

• 使用滑动窗口技术，避免重复计算子数组的和。

• 初始化第一个窗口的和，然后在滑动窗口时，加上新元素，减去旧元素。

• 时间复杂度：O(n)。

#include <iostream>  using namespace std;  void sw(int nums[], int n, int k) {      if (n < k) return; // 如果数组长度小于k，直接返回      double windowSum = 0;      // 初始化窗口      for (int i = 0; i < k; i++) {          windowSum += nums[i];      }      cout << windowSum / k << " ";      // 滑动窗口      for (int i = k; i < n; i++) {          windowSum += nums[i] - nums[i - k]; // 加上新元素，减去旧元素          cout << windowSum / k << " ";      }      cout << endl;  }    int main() {      int nums[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};      int n = sizeof(nums) / sizeof(nums[0]);      int k = 5;      sw(nums, n, k);      return 0;  }

【过程解释】

1. 初始化窗口：

• 计算第一个窗口的和 windowSum，即 nums[0] 到 nums[k-1] 的和。

• 输出第一个窗口的平均值 windowSum / k。

2. 滑动窗口：

• 从第 k 个元素开始，滑动窗口。

• 每次滑动时，加上新元素 nums[i]，减去旧元素 nums[i - k]。

• 输出当前窗口的平均值 windowSum / k。

图示：

第一次：（1+3+2）/3 

第二次：(3+2+6)/3 ，对比上一次，少了第一个数1，多了后一个数6

第二次：(2+6-1)/3 ，对比上一次，少了上一个数2，多了后一个数-1

一、差分：一维数组的差分可看作是一维数组前缀和的逆运算。

二、差分数组

首先给定一个原数组a:   a[1]、a[2]、a[3]、......

然后构造一个数组b: b[1]、b[2]、b[3]....

使得a[i]=b[1]+b[2]+b[3]+b[4]+.....b[i]。

那么根据上一节讲的，a数组就是b数组的前缀和数组。 

也就是说，a数组就是b数组的前缀和数组，反过来，我们把b数组叫做a数组的差分数组。话句话说，每一个a[i]数组都是b数组中从头开始的一段区间和。

三、功能及作用

    给区间[L,R]中每个数加上 c:  B[L] +=c， B[R+1] -=c

四、构造

考虑如何构造差分数组b：

最为直接的方法：

a[0]=0  b[1]=a[1]-a[0];  b[2]=a[2]-a[1];  b[3]=a[3]-a[2];  ......  b[n]=a[n]-a[n-1];

五、应用

【问题描述】给定区间[L,R]，让我们把a数组中的[L,R]区间中的每一个数都加上c， 即a[L]+c,  a[L+1]+c,  a[L+2]=c , ....  a[R]+c

解法一：暴力解法

用for循环，从L到R区间，时间复杂度O（n），如果我们需要对原数组执行m次这样的操作，那么时间复杂度就会变成O(n*m)。

解法二：差分

始终要记住一点：a数组是b数组的前缀和数组。比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。

首先让差分b数组中的b[L]+c，通过前缀和运算，a数组变成a[L]+c,... a[L+1]+c,.... a[n]+c

然后我们打个补丁， b[R+1] -c ，通过前缀和运算， a数组变成 a[R+1]-c,  ...  a[R+2]-c, ...   a[n] -c, ...

图解过程：

b[L]+c, 效果使得a数组中a[L]及以后的数都加上了c(红色部分)，但是我们只要求L到R区间加上c，因此还需要执行b[R+1]-c， 让a数组中a[R+1]以及往后的区间再减去c(绿色部分)，这样对于a[r]以后区间的数组相当于没有发生改变。

结论：给a数组中的[L,R]区间中的每一个数加上c。只需要对差分数组b做b[L]+=c，b[R+]-=c，时间复杂度为O（1）。

如果上面的描述不够清楚，我们可以借助下面方式来表示，我们假设a数组是原始数组，b数组是差分数组。我们的目的是让a数组的某个区间段加上一个数c。初始状态如下：

需求1：我们要将[1,4]范围内所有的数都加上3

规律：当对一个区间进行增减某个值的时候，他的差分数组对应的区间左端点的值会同步变化，而他的右端点的后一个值则会相反地变化。

那么用代码表示：

while(t--){//操作次数  	cin>>x>>y>>change;//左右端点值   	cin>>c;//c是每次加减的值   	b[x]=b[x]+c;  	b[y+1]=b[y+1]-c;  }

那么能不能反过来求a[i]呢，因为b数组是差分数组，满足公式b[i]=a[i]-a[i-1]

那么a[i]=a[i-1]+b[i]

六、题目

【题目描述】

输入一个长度为n的整数序列。

接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。

请你输出进行完所有操作后的序列。

【输入描述】

第一行包含两个整数n和m。

第二行包含n个整数，表示整数序列。

接下来m行，每行包含三个整数l，r，c，表示一个操作。

【输出描述】

共一行，包含n个整数，表示最终序列。

【样例输入】

6 3  1 2 2 1 2 1  1 3 1  3 5 1  1 6 1

【样例输出】

3 4 5 3 4 2

【数据范围】

1≤n,m≤100000,

1≤l≤r≤n,

−1000≤c≤1000,

−1000≤整数序列中元素的值≤1000