029.一维差分与等差数列差分

前置知识：无，知道什么是数组就行

一维差分 §

问题描述 §

有一个一维 int 数组，要对其进行多次范围操作，如果每次操作都修改每个位置的元素，就比较慢；可以用一维差分方法来做：每次操作只修改几个位置的元素，最后将所有位置刷对

比如有一个数组 [0, 0, 0, 0, 0, 0, 0, 0, 0]，要对其进行一系列操作：

1. [2, 5] +3
2. [1, 6] -2
3. [4, 7] +5

普通方法：

arr           [0,  0,  0,  0,  0,  0,  0,  0,  0]
idx            0   1   2   3   4   5   6   7   8
[2, 5] +3     [        3,  3,  3,  3,           ]
[1, 6] -2     [   -2,  1,  1,  1,  1, -2,       ]
[4, 7] +5     [   -2,  1,  1,  6,  6,  3,  5,   ]
              [0, -2,  1,  1,  6,  6,  3,  5,  0]

一维差分的过程 §

• set 方法：[L, R]+V，L 位置 +V, R+1 位置 -V
  • 可以理解为效果从 L 开始生效，到 R+1 失效
  • R+1 越界就不用设置了，因为后序没有元素了，设置了也没有意义
• build 方法：从左往右累加前缀和

arr           [0,  0,  0,  0,  0,  0,  0,  0,  0]
idx            0   1   2   3   4   5   6   7   8

set:
[2, 5] +3     [        3,             -3,       ]
[1, 6] -2     [   -2,  3,             -3,  2,   ]
[4, 7] +5     [   -2,  3,      5,     -3,  2, -5]

build:
              [0, -2,  3,  0,  5,  0, -3,  2, -5]
              [0, -2,  1,  1,  6,  6,  3,  5,  0]

题目1.航班预订统计 §

题目描述 §

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

测试链接 §

1109.航班预订统计

答案 §

func corpFlightBookings(bookings [][]int, n int) []int {
	// 为了方便书写，0 位置不用，最后一个位置防止 R+1 越界
	ans := make([]int, n+2)
	for _, booking := range bookings {
		ans[booking[0]] += booking[2]
		ans[booking[1]+1] -= booking[2]
	}
	// 加工前缀和
	for i := 1; i < n+2; i++ {
		ans[i] += ans[i-1]
	}
	return ans[1 : n+1]
}

备注 §

一维差分很简单，没有理解难度

• 它不支持边操作、边查询（边操作、边查询用一维差分没有意义，还不如普通方法）
• 边操作、边查询用线段树、树状数组

等差数列差分 §

问题描述 §

一开始 $1\backsim n$ 范围上的数字都是 0。接下来一共有 $m$ 个操作。

每次操作：$l\backsim r$ 范围上依次加上首项 $s$、末项 $e$、公差 $d$ 的数列

最终 $1\backsim n$ 范围上的每个数字都要正确得到

等差数列差分的过程 §

1. 每个操作调用 set 方法
2. 所有操作完成后在 arr 上生成两遍前缀和，即调用 build 方法

func set(l, r, s, e, d int) {
	arr[l] += s
	arr[l+1] += d-s
	arr[r+1] -= d+e
	arr[r+2] += e
}
 
func build() {
	// 两次前缀和
	for i := 1; i < len(arr); i++ {
		arr[i] += arr[i-1]
	}
	for i := 1; i < len(arr); i++ {
		arr[i] += arr[i-1]
	}
}

解释 §

拿 $1\backsim 5$ 范围上依次加上首项 $s$、末项 $e$、公差 $d$ 的数列举例，从最终结果逆推证明 set 函数为何这样设置

只是为了理解，实际直接记忆即可

题目1.等差数列差分模板 §

题目描述 §

一开始 $1\backsim n$ 范围上的数字都是 0，一共有 $m$ 个操作，每次操作为 $(l,r,s,e,d)$ 表示在 $l\backsim r$ 范围上依次加上首项为 $s$、末项为 $e$、公差为 $d$ 的数列

$m$ 个操作做完之后，统计 $1\backsim n$ 范围上所有数字的异或和和最大值

测试链接 §

P4231 三步必杀

答案 §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)
 
const (
	MAXN = 10000005
)
 
var (
	arr = [MAXN]int{}
	n   int
	m   int
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		tmp := strings.Fields(in.Text())
		n, _ = strconv.Atoi(tmp[0])
		m, _ = strconv.Atoi(tmp[1])
		for ; m > 0; m-- {
			in.Scan()
			tmp = strings.Fields(in.Text())
			l, _ := strconv.Atoi(tmp[0])
			r, _ := strconv.Atoi(tmp[1])
			s, _ := strconv.Atoi(tmp[2])
			e, _ := strconv.Atoi(tmp[3])
			d := (e - s) / (r - l)
			set(l, r, s, e, d)
		}
		build()
		xor := 0
		maxx := 0
		for i := 1; i <= n; i++ {
			xor ^= arr[i]
			maxx = max(maxx, arr[i])
		}
		fmt.Fprintln(out, xor, maxx)
	}
	out.Flush()
}
 
func set(l, r, s, e, d int) {
	arr[l] += s
	arr[l+1] += d - s
	arr[r+1] -= d + e
	arr[r+2] += e
}
 
func build() {
	for i := 1; i <= n; i++ {
		arr[i] += arr[i-1]
	}
	for i := 1; i <= n; i++ {
		arr[i] += arr[i-1]
	}
}

题目2.一群人落水后求每个位置的水位高度 §

题目描述 §

把一条湖泊看作一条长度为 m 的直线，一开始水深都在水平线 0 上，有 n 个人落水，每个人都有落水深度 v 和落水位置 i，落水导致水平面如下图所示变化，求这 n 个人同时落水后，水平面的状态

测试链接 §

P5026 Lycanthropy

思路 §

一个人落水造成 4 个等差数列差分

答案 §

package main
 
import (
	"bufio"
	"os"
	"strconv"
)
 
const (
	MAXN = 1000001 // 湖泊最大宽度
	// 为了简化代码，不进行边界讨论，将湖泊宽度扩大
	// 左侧影响最远的位置到达了 i - 3 * v + 1
	// 右侧影响最远的位置到达了 i + 3 * v - 1
	// i 如果是正式的位置(1~m)，那么左、右侧可能超过正式位置差不多 30000 的规模
	OFFSET = 30001
)
 
var (
	arr = [OFFSET + MAXN + OFFSET]int{}
	m   int
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ := strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		if m <= 0 {
			continue
		}
		for ; n > 0; n-- {
			in.Scan()
			v, _ := strconv.Atoi(in.Text())
			in.Scan()
			i, _ := strconv.Atoi(in.Text())
			set(i-3*v+1, i-2*v, 1, v, 1)
			set(i-2*v+1, i, v-1, -v, -1)
			set(i+1, i+2*v, -v+1, v, 1)
			set(i+2*v+1, i+3*v-1, v-1, 1, -1)
		}
		build()
		// 真正的位置是 [1 + OFFSET, m + OFFSET]
		start := 1 + OFFSET
		out.WriteString(strconv.Itoa(arr[start]))
		start++
		for i := 2; i <= m; i++ {
			out.WriteByte(' ')
			out.WriteString(strconv.Itoa(arr[start]))
			start++
		}
		out.WriteByte('\n')
	}
	out.Flush()
}
 
func set(l, r, s, e, d int) {
	arr[l+OFFSET] += s
	arr[l+1+OFFSET] += d - s
	arr[r+1+OFFSET] -= d + e
	arr[r+2+OFFSET] += e
}
 
func build() {
	for i := 1; i <= m+OFFSET; i++ {
		arr[i] += arr[i-1]
	}
	for i := 1; i <= m+OFFSET; i++ {
		arr[i] += arr[i-1]
	}
}

备注 §

等差数列差分在大厂笔试、面试中还不常见，是比赛必备技巧，但预计会流行

二维差分会在后续的【必备】课程里进一步讲述，支持边操作、边查询的结构会在【扩展】课程讲述

差分方法对原始数组的要求 §

对数组进行差分时，要求数组的元素都是 0，否则答案错误

如果数组元素非 0，需要将元素都置为 0，然后每一位对原始值进行差分

func startup(arr []int) []int {
	n := len(arr)
	ans := make([]int, n) // 将元素都置为 0
	for i := 0; i < n; i++ {
		set(ans, i, i, arr[i]) // 每一位对原始值进行差分
	}
	return ans
}

一维差分 §

package main
 
import (
	"fmt"
	"math/rand"
)
 
const (
	MINN       = 10
	MAXN       = 80
	MINV       = -999
	MAXV       = 1000
	TEST_TIMES = 3000
	OP_TIMES   = 10000
)
 
func main() {
	for i := 0; i < TEST_TIMES; i++ {
		arr := generateArr()
		arr2 := startup(arr)
		n := len(arr)
		for j := 0; j < OP_TIMES; j++ {
			l := rand.Intn(n >> 1)
			r := n>>1 + rand.Intn(n>>1-1)
			if l > r || r >= n {
				panic("测试数据生成有误！")
			}
			v := MINV + rand.Intn(MAXV-MINV)
			f1(arr, l, r, v)
			set(arr2, l, r, v)
		}
		build(arr2)
		for j := 0; j < n; j++ {
			if arr[j] != arr2[j] {
				panic("error")
			}
		}
	}
	fmt.Println("success")
}
 
// 普通方法
func f1(arr []int, l, r, v int) {
	for i := l; i <= r; i++ {
		arr[i] += v
	}
}
 
// 一维差分
func startup(arr []int) []int {
	n := len(arr)
	ans := make([]int, n+1) // 加一个长度，set 方法不用越界判断
	for i := 0; i < n; i++ {
		set(ans, i, i, arr[i])
	}
	return ans
}
 
func set(arr []int, l, r, v int) {
	arr[l] += v
	arr[r+1] -= v
}
 
func build(arr []int) {
	n := len(arr)
	for i := 1; i < n; i++ {
		arr[i] += arr[i-1]
	}
}
 
func generateArr() []int {
	n := MINN + rand.Intn(MAXN-MINN)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = MINV + rand.Intn(MAXV-MINV)
	}
	return arr
}

等差数列差分 §

package main
 
import (
	"fmt"
	"math/rand"
)
 
const (
	MINN       = 10
	MAXN       = 80
	MINV       = -999
	MAXV       = 1000
	MIND       = -9
	MAXD       = 10
	TEST_TIMES = 3000
	OP_TIMES   = 10000
)
 
func main() {
	for i := 0; i < TEST_TIMES; i++ {
		arr := generateArr()
		arr2 := startup(arr)
		n := len(arr)
		for j := 0; j < OP_TIMES; j++ {
			l := rand.Intn(n >> 1)
			r := n>>1 + rand.Intn(n>>1-1)
			if l > r || r >= n {
				panic("测试数据生成有误！")
			}
			s := MINV + rand.Intn(MAXV-MINV)
			d := MIND + rand.Intn(MAXD-MIND)
			e := s + (r-l)*d
			f1(arr, l, r, s, d)
			set(arr2, l, r, s, e, d)
		}
		build(arr2)
		for j := 0; j < n; j++ {
			if arr[j] != arr2[j] {
				panic("error")
			}
		}
	}
	fmt.Println("success")
}
 
// 普通方法
func f1(arr []int, l, r, s, d int) {
	for i := l; i <= r; i++ {
		arr[i] += s + (i-l)*d
	}
}
 
// 等差数列差分
func startup(arr []int) []int {
	n := len(arr)
	ans := make([]int, n+2) // 加两个长度，set 方法不用越界判断
	for i := 0; i < n; i++ {
		set(ans, i, i, arr[i], arr[i], 0)
	}
	return ans
}
 
func set(arr []int, l, r, s, e, d int) {
	arr[l] += s
	arr[l+1] += d - s
	arr[r+1] -= d + e
	arr[r+2] += e
}
 
func build(arr []int) {
	n := len(arr)
	for i := 1; i < n; i++ {
		arr[i] += arr[i-1]
	}
	for i := 1; i < n; i++ {
		arr[i] += arr[i-1]
	}
}
 
func generateArr() []int {
	n := MINN + rand.Intn(MAXN-MINN)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = MINV + rand.Intn(MAXV-MINV)
	}
	return arr
}

二维差分 §

二维差分