忆の風

Acg | 0x03

前缀和：\(O(1)\)求某个区间或区域的和

差分：\(O(1)\)为某个连续区间或区域加一个固定的值

「一维前缀和」

  1. Analyse

求一段区间的和 $$sum(l,r) = b[r]-b[l-1]$$

  1. code

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    # input, 0位置存储0,从1开始存数
n,m=map(int, input().split())
a=[0]
a.extend(list(map(int, input().split())))
b=[0]*(n+1)

# 前缀和
for i in range(1,n+1):
	b[i] = b[i-1]+a[i]

# output
while m:
	m-=1
	l,r=map(int, input().split())
	print(b[r]-b[l-1])

「二维前缀和」

  1. Analyse

  1. code

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

    # input
n,m,q=map(int,input().split())
a=[[0 for i in range(m+1)] for j in range(n+1)]
b=[[0 for i in range(m+1)] for j in range(n+1)]

for i in range(1,n+1):
	temp=list(map(int, input().split()))
	for j in range(m):
		a[i][j+1] = temp[j]

# 前缀和
for i in range(1,n+1):
	for j in range(1,m+1):
		b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j]

# output
while q:
	q-=1
	x1,y1,x2,y2=map(int, input().split())
	print(b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1])

「一维差分」

  1. Analyse
  • 想让\([l,r]\)区间的数\(+c\),如果让\(b[l]+c\),会使$b$的前缀和数组$l$位置后面的所有数都会\(+c\), 所以问题来了，怎么能使\(r\)位置后面的数不加\(c\)呢？ \(b[r+1]-c\)即可。
  1. code
 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

const N = int(1e5) + 10

var (
	n, m int
	a, b [N]int
)

func main() {
	defer ot.Flush()

    // 输入
	n, m = rnI(), rnI()
	for i := 1; i <= n; i++ {
		a[i] = rnI()
	}
	InitChaFen() // 初始化差分数组

    // m个区间加c操作
	for ; m != 0; m-- {
		l, r, c := rnI(), rnI(), rnI()
		add(l, r, c)
	}

	// 前缀和计算,得到最终数组
	for i := 1; i <= n; i++ {
		b[i] += b[i-1]
	}

    // 输出
	for i := 1; i <= n; i++ {
		fmt.Fprintf(ot, "%d ", b[i])
	}

}

// 让区间[l,r]所有数加上c
func add(l, r, c int) {
	b[l] += c
	b[r+1] -= c
}

// 差分数组构造
func InitChaFen() {
	for i := 1; i <= n; i++ {
		add(i, i, a[i])
	}
}

「二维差分」

  1. Analyse
  • 同一维差分原理一致，从给某个区间变成给某个矩形区域加 c,只需推导公式即可.
$$ \begin{cases} b_{x_1,y_1}+=c, \\ b_{x_2+1,y_1}-=c, \\ b_{x1,y_2+1}-=c, \\ b_{x_2+1,y_2+1}+=c.\\ \end{cases} $$
  1. Code
 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

# 某个面积区域内加c
def insert(x1,y1,x2,y2,c):
	b[x1][y1]     += c
	b[x1][y2+1]   -= c
	b[x2+1][y1]   -= c
	b[x2+1][y2+1] += c

# input
n,m,q=map(int, input().split())
a=[[0 for i in range(m+2)] for j in range(n+2)]
b=[[0 for i in range(m+2)] for j in range(n+2)]
for i in range(1,n+1):
	temp=list(map(int, input().split()))
	for j in range(m):
		a[i][j+1] = temp[j]

# b数组差分初始化
for i in range(1,n+1):
	for j in range(1,m+1):
		insert(i,j,i,j,a[i][j])
# op
while q:
	q-=1
	x1,y1,x2,y2,c=map(int, input().split())
	insert(x1,y1,x2,y2,c)

# 求前缀和
for i in range(1,n+1):
	for j in range(1,m+1):
		b[i][j] += b[i-1][j] + b[i][j-1] -b[i-1][j-1]

# output
for i in range(1,n+1):
	for j in range(1,m+1):
		print(b[i][j],end=' ')
	print()