前缀和与差分

前缀和与差分的关系

前缀和

对于前缀和它的维护的时间复杂度与数据规模有关，但是对于求某个区间的和的操作的时间复杂度却为 $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;
}