差分

快速处理区间加减(前缀和的逆运算)

for(int i=n-1;i>=0;i--)
{
 if(i==0)
 d[i]=a[i];
 else
 d[i]=a[i]-a[i-1];
}

1 1 1 1 1 1 1 1
前缀和得到 差分得到
1 2 3 4 1 0 0 0
差分得到 前缀和得到
1 1 1 1 恢复为原数组 1 1 1 1 恢复为原数组

和前缀和互为逆运算：

前缀和数组做差分:

• $$s_i = a_0 + a_1 + \dots + a_{i-1} + a_i$$
• ($i$ 位置的前缀和是 $0$ 到 $i$ 的总和)
• $$s_{i-1} = a_0 + a_1 + \dots + a_{i-1}$$
• ($i-1$ 位置的前缀和是 $0$ 到 $i-1$ 的总和)
• 相减得出： $$s_i - s_{i-1} = a_i$$
• 这意味着：前缀和数组的差分（相邻项相减）就是原数组的元素。

差分数组计算前缀和:

• $$d_i = a_i - a_{i-1}$$
• $$d_{i-1} = a_{i-1} - a_{i-2}$$
• … （中间省略）
• $$d_1 = a_1 - a_0$$
• $$d_0 = a_0$$
• 左边相加：
  $d_0 + d_1 + \dots + d_i$这实际上就是在对差分数组 $d$ 求前缀和。

$a[l, r] + k \Longleftrightarrow d[l] + k, \quad d[r+1] - k$

如果你想给原数组 $a$ 的区间 $[l, r]$ 内的所有数字都加上 $k$，你只需要在差分数组 $d$ 的左边界 $l$ 处加上 $k$，并在右边界的下一个位置 $r+1$ 处减去 $k$。

二维差分

先对每一列差分,再对每一行差分

异或差分

第一步：构造异或差分数组

将原数组转化为一个“异或差分”序列。

• 计算规则： 差分数组 $d[i] = a[i] \oplus a[i-1]$（规定 $a[0] = 0$）。
• 图片示例： 原数组 [1, 2, 3, 4, 5, 6] 经过“差分”后变为 [1, 3, 1, 7, 1, 3]。
  • $1 \oplus 0 = 1$
  • $2 \oplus 1 = 3$
  • $3 \oplus 2 = 1$
  • 以此类推。

    第二步：执行区间异或操作

    假设要在区间 $[l, r]$ 上统一异或一个值 $k$。在差分数组上，这只需要修改两个点。
• 操作公式：
  1. $d[l] = d[l] \oplus k$
  2. $d[r+1] = d[r+1] \oplus k$
• 图片示例： 对区间 $[2, 5]$ 执行 ^ 2（异或 2）。
  • 修改左端点（索引 2）：原来的 $3 \oplus 2 = 1$。
  • 修改右端点外侧（索引 6）：原来的 $3 \oplus 2 = 1$。
  • 修改后的差分数组变为：[1, 1, 1, 7, 1, 1]。

    第三步：还原结果（前缀异或和）

    通过对修改后的差分数组求前缀异或和，得到最终的修改结果。
• 计算公式： $a’[i] = d[1] \oplus d[2] \oplus \dots \oplus d[i]$。
• 图片示例： 对 [1, 1, 1, 7, 1, 1] 求前缀异或和。
  1. 第 1 位：$1$
  2. 第 2 位：$1 \oplus 1 = 0$
  3. 第 3 位：$0 \oplus 1 = 1$
  4. 第 4 位：$1 \oplus 7 = 6$
  5. 第 5 位：$6 \oplus 1 = 7$
  6. 第 6 位：$7 \oplus 1 = 6$
• 最终数组： [1, 0, 1, 6, 7, 6]。
  对于区间 $[l, r]$ 进行异或 $k$ 的操作，其差分逻辑为：

$$d[l] = d[l] \oplus k$$ $$d[r+1] = d[r+1] \oplus k$$

利用多重差分来解决多项式形式的区间修改

1. 核心概念：差分与导数的关系

在离散数学中，差分（Difference）之于数列，就相当于导数（Derivative）之于连续函数。

• 常数的导数是 0。
• $x$（一次函数）的导数是常数。
• $x^2$（二次函数）的导数是一次函数。
  差分也是同理：
  每一次差分操作，都会把多项式的最高次幂降低 1 次。

  2. 图片公式逐行详解

  图片中列举了不同复杂度的修改（$add_x$），以及它们对应的处理方式。

  第一行：$add_x = a$ （常数修改）

• 含义：这是最基础的区间修改。比如“给区间 $[L, R]$ 的每个数都加上常数 $a$”。
• 多项式次数：$0$ 次（因为 $a = a \cdot x^0$）。
• 所需差分阶数：一阶差分。
• 原理：
  常数序列（如 $3, 3, 3, 3$）做一次差分后，中间全是 $0$（除了边界）。
  • 原数：$0, 0, 3, 3, 3, 3, 0$
  • 一阶差分：$0, 0, 3, 0, 0, 0, -3$
  • 结论：只需要修改两个点（$L$ 和 $R+1$），就能代表整个区间的修改。

    第二行：$add_x = a + bx$ （线性/等差数列修改）

• 含义：给区间加上一个等差数列。比如“给第 $x$ 个数加上 $2x+1$”。
• 多项式次数：$1$ 次。
• 所需差分阶数：二阶差分。
• 原理：
  • 原增量序列（线性）：$1, 3, 5, 7, 9$ （这是一个一次函数）
  • 一阶差分：$1, 2, 2, 2, 2$ （变成了常数序列，除了开头）
  • 二阶差分：$1, 1, 0, 0, 0$ （中间变成了 0）
  • 结论：对一个线性增长的区间修改，维护二阶差分数组，只需要在边界处进行 $O(1)$ 的修改。

    第三行：$add_x = a + bx + cx^2$ （二次函数修改）

• 含义：给区间加上一个平方级别的增长量。比如“物理中的匀加速运动位移”。
• 多项式次数：$2$ 次。
• 所需差分阶数：三阶差分。

• 原理：

  • $x^2$ 做差分变成 $(x+1)^2 - x^2 = 2x+1$（降级为一次函数）。
  • 再做差分变成常数。
  • 再做差分变成 0。
  • 结论：只要是 $n$ 次多项式，做 $n+1$ 次差分后，区间内部的值就会变成 0，只剩下边界有值。

    3. 为什么是“多项式累加 $\Longrightarrow$ 多重差分”？

    这张图推导出的通用法则是：

1. 降维打击：利用差分性质，把复杂的曲线（高次多项式）通过多次差分“打平”成 0。
2. 操作：
   • 如果你要加一个 $k$ 次多项式。
   • 你就建立一个 $k+1$ 阶差分数组。
   • 你只需要在这个高阶差分数组的 $L$（起点） 和 $R$（终点） 附近修改少数几个值。
3. 还原：
   • 当询问最终结果时，对这个 $k+1$ 阶差分数组做 $k+1$ 次前缀和（Prefix Sum），就能还原出原始数组的增量。

差分的正负性反应了原数组的增减性

1. 核心逻辑：从“面”到“点”的降维

• 左边（原数组视角）：
  • 操作：任选 [L, R]，让区间内所有元素加 1 或减 1。
  • 难点：每次操作涉及很多个数，状态难以穷举。
  • 目标：想让原数组变成递增、递减或者所有数相等。
• 右边（差分数组视角）：
  • 操作：由于差分的性质（$D[L]+v, D[R+1]-v$），原数组的一次区间修改，等价于在差分数组中任选两个位置，一个加 1，一个减 1。
    • _特殊情况_：如果只选一个位置修改（比如只改 $L$ 处），其实是因为另一个位置选在了 $N+1$（越界无效位置），图中的 X | 1 2 3 4 | X 就在暗示这种边界处理。
  • 优势：操作从“修改一排数”变成了“修改两个数”，复杂度大大降低。
  • 目标：
    • 原数组递增 $\Longleftrightarrow$ 差分数组每一项（除第一项外）都 $\ge 0$。
    • 原数组递减 $\Longleftrightarrow$ 差分数组每一项（除第一项外）都 $\le 0$。
    • 原数组相等 $\Longleftrightarrow$ 差分数组每一项（除第一项外）都 $= 0$。

      2. 经典案例解析：IncDec Sequence

      这张图其实对应了一道非常经典的算法题（NOIp 2011 提高组《IncDec Sequence》）。
      问题描述
      给定一个数组，每次可以选择一个区间 $[L, R]$ 进行 $+1$ 或 $-1$ 操作。问最少操作多少次，能让数组中所有元素都相等？
      结合这张图的解法：

1. 转化目标：
   让“原数组所有元素相等”，等价于让“差分数组 $D[2], D[3] \dots D[n]$ 全部变为 0”。（注意 $D[1]$ 不需要为 0，因为 $D[1]$ 决定了最终相等的那个数值是多少）。
2. 分析现状：
   计算出初始的差分数组后，你会发现 $D[2 \dots n]$ 中有一些正数（需要减），有一些负数（需要加）。
3. 匹配操作（图中的“任选两个位置”）：
   • 贪心策略 1：优先在 $D[2 \dots n]$ 内部找一正一负进行配对。比如 $D[i] > 0, D[j] < 0$，我们就对区间 $[i, j-1]$ 操作。这样能一次性解决两个数的偏差（“一个加，一个减”），效率最高。
   • 贪心策略 2：如果正负无法配对（比如只剩下正数了），那就只能和边界（$D[1]$ 或 $D[n+1]$）配对。这对应图中“任选一个位置，增加/减少”。
4. 结论：
   通过把复杂的区间问题转化为差分数组上的正负数抵消游戏，我们可以瞬间得出最少操作次数公式：$\max(\text{正数和}, |\text{负数和}|)$。

   3. 总结

   这张图想表达的是差分技术的最高境界：
   不仅仅是用它来快速修改数据（如前两张图所述），而是用它来重构问题的定义。

• 看到“区间加减” $\rightarrow$ 转化为 “差分数组的两点修改”。
• 看到“单调性/相等”目标 $\rightarrow$ 转化为 “差分数组的正负/零”目标。