区间加减-差分数组、前缀和数组

区间加减-差分数组、前缀和数组

简介

差分数组是本质上就是一个辅助性质的数组，可以实现$O(1)$时间复杂度的区间批量加减。

前缀和数组是可以在$O(1)$时间复杂度下获取区间数值和的辅助性质的数组。

在使用差分数组进行区间批量修改后要配合前缀和数组（差分数组的前缀和）获取修改后的结果，然后进行单点查询。

eg

• 原数组为长度7全为零的数组a[7] = {0,0,0,0,0,0,0}

• 其差分数组初始化状态是长度7全零

• 进行区间修改
  • [1,3] +3
  • [4,5] +2
  • [2,4] -4

• 获取差分数组的前缀和，即修改后的数组

差分数组公式
d i f f [ i ] = { a [ i ] − a [ i − 1 ] , i f    i > 0 a [ i ] , i f    i = 0 diff[i] = {a[i]−a[i−1],if  i>0a[i],if  i=0

diff[i]={a[i]−a[i−1]a[i]​,if  i>0,if  i=0​

练习题

力扣-面试题 16.10. 生存人数

代码

Go语言

func maxAliveYear(birth []int, death []int) int {
    res,temp := 0,0
    n := len(birth)
    diff := make([]int,102)
    sums := make([]int,102)
    for i := 0; i < n; i ++ {
        diff[birth[i]-1900]++
        diff[death[i]-1900+1]--
    }
    sums[0] = diff[0]
    for i := 1; i < 102; i++ {
        sums[i] = sums[i-1]+diff[i]
        if temp < sums[i] {
            temp = sums[i]
            res = i+1900
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

c++

class Solution {
public:
    int maxAliveYear(vector<int>& birth, vector<int>& death) {
        int res = 0, temp = 0, n = birth.size();
        int diff[102] = {0},sums[102] = {0};
        for (int i = 0; i < n; i++) {
            diff[birth[i]-1900]++;
            diff[death[i]-1900+1]--;
        }
        sums[0] = diff[0];
        for (int i = 1; i < 102; i++) {
            sums[i] = diff[i]+sums[i-1];
            if (temp < sums[i]) {
                temp = sums[i];
                res = i+1900;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

AcWing-1952. 金发姑娘和 N 头牛

Go语言

package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, x, y, z int
	var a, b, a_, b_ [20005]int
	var c [40005]int
	var diff, sums [40005]int
	res := 0
	mp := make(map[int]int)
	fmt.Scan(&n, &x, &y, &z)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i], &b[i])
	}
	// 离散化
	for i := 0; i < n; i++ {
		c[2*i], c[2*i+1] = a[i], b[i]
	}
	sort.Ints(c[:2*n])
	ln := 0
	for i := 0; i < 2*n; i++ {
		if _, ok := mp[c[i]]; !ok {
			mp[c[i]] = ln
			ln++
		}
	}
	// 差分化
	for i := 0; i < n; i++ {
		a_[i] = mp[a[i]]
		b_[i] = mp[b[i]]
	}
	for i := 0; i < n; i++ {
		diff[0] += x
		diff[a_[i]] -= x
		diff[a_[i]] += y
		diff[b_[i]+1] -= y
		diff[b_[i]+1] += z
		diff[ln] -= z
	}
	sums[0] = diff[0]
	// 求最值
	for i := 1; i < ln; i++ {
		sums[i] = diff[i] + sums[i-1]
		if res < sums[i] {
			res = sums[i]
		}
	}
	fmt.Println(res)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54