前缀和与差分

前缀和与差分的关系

前缀和

对于前缀和它的维护的时间复杂度与数据规模有关,但是对于求某个区间的和的操作的时间复杂度却为 $O(1)$
一维前缀和: 维护: s[i] = s[i-1] + a[i]
[l, r] 区间的和:s[r] - s[l-1]
二维前缀和: 维护: s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]
[x1, y1][x2, y2] 的和:s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
三维前缀和: 维护: s[i][j][k] = s[i-1][j][k] + s[i][j-1][k] + s[i][j][k-1] - s[i-1][j-1][k] - s[i-1][j][k-1] - s[i][j-1][k-1] + s[i-1][j-1][k-1] + a[i][j][k]
[x1, y1, z1][x2, y2, z2] 的和: s[x2][y2][z2] - s[x1-1][y2][z2] - s[x2][y1-1][z2] - s[x2][y2][z1-1] + s[x1-1][y1-1][z2] + s[x1-1][y2][z1-1] + s[x2][y1-1][z1-1] - s[x1-1][y1-1][z1-1]

差分

对于差分,维护时只需要$O(1)$的时间复杂度,但是求某个位置上元素的值却与数据规模有关
一维差分: 将[l, r]上的所有数 +c :b[l] += c , b[r+1] -= c
a[i]​ 的值: 其实就是求 b 数组的一位前缀和
二维差分: 将 [x1, y1]​ 到 [x2, y2]​ 上的数字 +c: b[x1][y1]+=c , b[x2+1][y1] -= c , b[x1][y2+1] -=c , b[x2+1][y2+1] +=c
a[i][j]​ 的值: 其实就是求 $b$ 数组的二维前缀和
三维差分: 将 [x1, y1, z1]​ 到 [x2, y2, z2]​ 上的数字 +c: b[x1][y1][z1]+=c , b[x2+1][y1][z1] -=c , b[x1][y2+1][z1] -= c , b[x1][y1][z2+1]-=c , b[x2+1][y2+1][z1] +=c , b[x2+1][y1][z2+1] +=c , b[x1][y2+1][z2+1] +=c , b[x2+1][y2+1][z2+1] -=c
a[i]​ 的值:其实就是求 $b$ 数组的三维前缀和

差分数组的前缀和数组即为原数组

一维前缀和

1
2
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
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
import java.io.*;

public class oneDimensionalPreSum {

/**
* AcWing 795. 前缀和
*/
static int N = 100010;
static int[] a = new int[N];
static int[] s = new int[N];

public static void preSum() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] tmp = br.readLine().split(" ");
int n = Integer.parseInt(tmp[0]);
int m = Integer.parseInt(tmp[1]);
String[] arr = br.readLine().split(" ");
for (int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(arr[i - 1]);
}
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i]; //前缀和初始化
while (m-- > 0) {
String[] q = br.readLine().split(" ");
int l = Integer.parseInt(q[0]);
int r = Integer.parseInt(q[1]);
System.out.println(s[r] - s[l - 1]); //区间和计算
}
br.close();
}
}

二维前缀和

1
2
3
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

AcWing 796.子矩阵的和

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
import java.io.*;

/**
* AcWing 796. 子矩阵的和
*/
public class twoDimensionalPreSum {

static int N = 1010;

static int[][] a = new int[N][N];

static int[][] s = new int[N][N];

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] tmp = br.readLine().split(" ");
int n = Integer.parseInt(tmp[0]);
int m = Integer.parseInt(tmp[1]);
int q = Integer.parseInt(tmp[2]);

for (int i = 1; i <= n; i++) {
String[] string1 = br.readLine().split(" ");
for (int j = 1; j <= m; j++) {
a[i][j] = Integer.parseInt(string1[j - 1]);
}
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
}

while (q-- > 0) {
String[] string2 = br.readLine().split(" ");
int x1 = Integer.parseInt(string2[0]);
int y1 = Integer.parseInt(string2[1]);
int x2 = Integer.parseInt(string2[2]);
int y2 = Integer.parseInt(string2[3]);
int result = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
System.out.println(result);

}
br.close();
}
}

一维差分

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

/**
* AcWing 797. 差分
*/

import java.io.*;
import java.util.*;

public class oneDimensionalDifference {

static int N = 100010;
static int[] a = new int[N];
//差分数组
static int[] b = new int[N];

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
insert(i, i, a[i]);
}


while (m-- > 0) {
int l = sc.nextInt();
int r = sc.nextInt();
int c = sc.nextInt();
insert(l, r, c);
}
for (int i = 1; i <= n; i++) b[i] += b[i - 1];

for (int i = 1; i <= n; i++) {
System.out.print(b[i] + " ");
}
}

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

二维差分

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
55
56
57
58
59
package basic_1.preSumAndDifference;
/**
* AcWing 798. 差分矩阵
*/

import java.io.*;
import java.util.*;

public class twoDimensionalDifference {

static int N = 1010;
static int[][] a = new int[N][N];
//差分数组
static int[][] b = new int[N][N];

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int q = sc.nextInt();

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = sc.nextInt();
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
insert(i, j, i, j, a[i][j]);
}
}
while (q-- > 0) {
int x1 = sc.nextInt();
int y1 = sc.nextInt();
int x2 = sc.nextInt();
int y2 = sc.nextInt();
int c = sc.nextInt();
insert(x1, y1, x2, y2, c);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
System.out.print(b[i][j] + " ");
}
System.out.println();
}
}

public static void insert(int x1, int y1, int x2, int y2, int c) {
b[x1][y1] += c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y1] -= c;
b[x2 + 1][y2 + 1] += c;
}
}

双指针算法

1
2
3
4
5
6
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;

// 具体问题的逻辑
}

常见问题分类:

  • 对于一个序列,用两个指针维护一段区间
  • 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

AcWing 795.前缀和

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
/**
* AcWing 795. 前缀和
*/

import java.util.*;

public class buchongfu_799 {

static final int N = 100010;
static int[] a = new int[N];
static int[] s = new int[N];


public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int result = 0;
for (int i = 0, j = 0; i < n; i++) {
s[a[i]]++;
while (s[a[i]] > 1) {
s[a[j]]--;
j++;
}
result = Math.max(result, i - j + 1);
}
System.out.println(result);
}
}

位运算

求 $n$ 的第 $k$ 位数字: n >> k & 1
返回 $n$ 的最后一位1:lowbit(n) = n & -n

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
package basic_1;

/**
* AcWing 801. 二进制中1的个数
*/

import java.util.*;
import java.io.*;

public class lowbit_801 {

static final int N = 100010;
static int[] A = new int[N];

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();

while (n-- > 0) {
int x = sc.nextInt();
int result = 0;
while (x != 0) {
x -= lowbit(x); //每次减去x的最后一位1
result++;
}
System.out.print(result + " ");
}
}

public static int lowbit(int x) {
return x & -x;
}
}

离散化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}

区间合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
vector<PII> res;

sort(segs.begin(), segs.end());

int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);

if (st != -2e9) res.push_back({st, ed});

segs = res;
}