一维差分

一、算法思想

差分定义：前缀和的逆运算。

当给定一个数组 $A$，我们需要构造一个数组 $B$，使得 $A$ 是 $B$ 的前缀和，此时我们称 $B$ 是 $A$ 的差分。

1.1 计算方法

$b_i = a_i - a_{i-1}$

说明

一般不会用这种构造方法，$B$ 数组的构造可以看作是全 $0$ 的 $A$ 数组进行 $n$ 次的 $[i,i]$ 的元素累加操作，这样可以将差分的构造与应用进行统一。

1.2 作用

根据差分的定义，$O(n)$ 的时间内就可以通过 $B$ 数组还原出 $A$ 数组，因此可以将它们看作是等价的。

那么来看这样的操作，对 $A$ 数组中 $[l,r]$ 区间内的元素加上 $c$。

• 如果在 $A$ 数组操作，那么时间复杂度是 $O(n)$ 的；
• 如果在 $B$ 数组操作，那么就可以在 $O(1)$ 时间内完成，具体方法如下：

b[l] += c;
b[r + 1] -= c;

二、算法模板

Go

type Difference1D struct {
    diff []int
    n    int
}

// NewDifference1D 初始化一维差分数组
func NewDifference1D(n int) *Difference1D {
    return &Difference1D{
        diff: make([]int, n+2),
        n:    n,
    }
}

// 给 l 到 r 区间内的元素加上 c
func (df *Difference1D) insert(l, r, c int) {
    df.diff[l] += c
    df.diff[r+1] -= c
}

// 获取最终数组
func (df *Difference1D) final() (ans []int) {
    ans = make([]int, df.n+1)
    for i := range ans {
        ans[i] = df.diff[i]
    }
    for i := 1; i <= df.n; i++ {
        ans[i] += ans[i-1]
    }
    ans = ans[1:]
    return
}

三、代码实战

AcWing 0797

---

题目：差分

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

$1 \le n, m \le 10^5$

$1 \le l \le r \le n$

$-1000 \le c \le 1000$

$-1000 \le \text{整数序列中元素的值} \le 1000$

输入样例：

6 3

1 2 2 1 2 1

1 3 1

3 5 1

1 6 1

输出样例：

3 4 5 3 4 2

解答代码：

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        insert(i, i, a[i]);
    }
    
    while (m--) {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1];
        printf("%d ", b[i]);
    }
    
    return 0;
}

package main

import (
    "bufio"
    . "fmt"
    "io"
    "os"
)

type Difference1D struct {
    diff []int
    n    int
}

// NewDifference1D 初始化一维差分数组
func NewDifference1D(n int) *Difference1D {
    return &Difference1D{
        diff: make([]int, n+2),
        n:    n,
    }
}

// 给 l 到 r 区间内的元素加上 c
func (df *Difference1D) insert(l, r, c int) {
    df.diff[l] += c
    df.diff[r+1] -= c
}

// 获取最终数组
func (df *Difference1D) final() (ans []int) {
    ans = make([]int, df.n+1)
    for i := range ans {
        ans[i] = df.diff[i]
    }
    for i := 1; i <= df.n; i++ {
        ans[i] += ans[i-1]
    }
    ans = ans[1:]
    return
}

func run(_r io.Reader, out io.Writer) {
    in := bufio.NewReader(_r)

    var n, m int
    Fscan(in, &n, &m)

    df := NewDifference1D(n)

    var x int
    for i := 0; i < n; i++ {
        Fscan(in, &x)
        df.insert(i+1, i+1, x)
    }

    for i := 0; i < m; i++ {
        var l, r, c int
        Fscan(in, &l, &r, &c)
        df.insert(l, r, c)
    }

    ans := df.final()

    for _, num := range ans {
        Fprintf(out, "%d ", num)
    }
}

func main() {
    run(os.Stdin, os.Stdout)
}