前缀和 & 差分

• OI Wiki: https://oi-wiki.org/basic/prefix-sum/

题目	难度
523. 连续的子数组和	中等
560. 和为 K 的子数组	中等
930. 和相同的二元子数组	中等	同 560
974. 和可被 K 整除的子数组	中等	取模
1371. 每个元音包含偶数次的最长子字符串	中等	状态压缩 + 取模
1542. 找出最长的超赞子字符串	困难	状态压缩 + 取模
1590. 使数组和能被 P 整除	中等	取模 974
1915. 最美子字符串的数目	中等	状态压缩 + 取模 T3

题目	难度
1124. 表现良好的最长时间段	中等	哈希 首次出现下标
面试题 17.05. 字母与数字	中等	哈希 首次出现下标

题目	难度
2132. 用邮票贴满网格图	困难	二维前缀和 & 二维差分 T4
2536. 子矩阵元素加 1	中等	二维差分 T2

高维前缀和

题目	难度
数对统计【算法赛】		SOSDP，Sum over Subsets dynamic programming

定义

前缀和 & 差分 模板

public class PrefixSum {
    private final int len;
    private final int[] preSum;
    private final int[] diff;

    public PrefixSum(int[] nums) {
        this.len = nums.length;
        // 前缀和
        preSum = new int[len + 1];
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        // 差分 init
        diff = new int[len + 1];
    }

    /**
     * 前缀和：求 nums [i,j] 的累加和
     */
    public int sumRange(int i, int j) {
        return preSum[j + 1] - preSum[i];
    }

    /**
     * 差分：nums [i,j] 增加 inc
     */
    public void rangeAdd(int i, int j, int inc) {
        diff[i] += inc;
        diff[j + 1] -= inc;
    }

    /**
     * 差分：获取原数组
     */
    public int[] originalArray() {
        int[] res = new int[len];
        res[0] = diff[0];
        for (int i = 1; i < len; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}

前缀和（取模/哈希表）

560. 和为 K 的子数组

import java.util.HashMap;
import java.util.Map;

public class Solution560 {
    public int subarraySum(int[] nums, int k) {
        // 前缀和
        int sum = 0;
        // 前缀和 频次
        Map<Integer, Integer> sumCntMap = new HashMap<>();
        sumCntMap.put(0, 1);
        int res = 0;
        for (int num : nums) {
            sum += num;
            int find = sum - k;
            res += sumCntMap.getOrDefault(find, 0);
            sumCntMap.put(sum, sumCntMap.getOrDefault(sum, 0) + 1);
        }
        return res;
    }
}

974. 和可被 K 整除的子数组

public class Solution974 {
    public int subarraysDivByK(int[] nums, int k) {
        // 模 k 下的前缀和
        int sumMod = 0;

        // 前缀和 频次
        int[] modCnt = new int[k];
        modCnt[0] = 1;
        for (int num : nums) {
            sumMod = ((sumMod + num) % k + k) % k;
            modCnt[sumMod]++;
        }

        int res = 0;
        for (int x : modCnt) {
            res += x * (x - 1) / 2;
        }
        return res;
    }
}

1371. 每个元音包含偶数次的最长子字符串

import java.util.HashMap;
import java.util.Map;

public class Solution1371 {
    public int findTheLongestSubstring(String s) {
        int len = s.length();

        // 前缀和（sumMod2Mask[i] = 0 表示该字母出现偶数次，sumMod2Mask[i] = 1 表示该字母出现奇数次）
        int sumMod2Mask = 0;

        // 首次出现下标
        Map<Integer, Integer> sumModFirstMap = new HashMap<>();
        sumModFirstMap.put(0, -1);
        int max = 0;
        for (int j = 0; j < len; j++) {
            char ch = s.charAt(j);
            if ("aeiou".indexOf(ch) >= 0) {
                // 模2 下的加法相当于 异或
                sumMod2Mask ^= 1 << (ch - 'a');
            }

            if (sumModFirstMap.containsKey(sumMod2Mask)) {
                int i = sumModFirstMap.get(sumMod2Mask);
                max = Math.max(max, j - i);
            } else {
                sumModFirstMap.put(sumMod2Mask, j);
            }
        }
        return max;
    }
}

1542. 找出最长的超赞子字符串

import java.util.HashMap;
import java.util.Map;

public class Solution1542 {
    public int longestAwesome(String s) {
        int len = s.length();

        // 前缀和（sumMod2Mask[i] = 0 表示该字母出现偶数次，sumMod2Mask[i] = 1 表示该字母出现奇数次）
        int sumMod2Mask = 0;

        // 首次出现下标
        Map<Integer, Integer> sumModFirstMap = new HashMap<>();
        sumModFirstMap.put(0, -1);
        int max = 0;
        for (int j = 0; j < len; j++) {
            // 模2 下的加法 相当于 异或
            sumMod2Mask ^= 1 << (s.charAt(j) - '0');

            // 所有字母均出现偶数次
            if (sumModFirstMap.containsKey(sumMod2Mask)) {
                int i = sumModFirstMap.get(sumMod2Mask);
                max = Math.max(max, j - i);
            } else {
                sumModFirstMap.put(sumMod2Mask, j);
            }

            // 枚举其中一个字母出现奇数次
            for (int k = 1; k < (1 << 10); k = k << 1) {
                int mask = sumMod2Mask ^ k;
                if (sumModFirstMap.containsKey(mask)) {
                    int i = sumModFirstMap.get(mask);
                    max = Math.max(max, j - i);
                }
            }
        }
        return max;
    }
}

1915. 最美子字符串的数目

public class Solution1915 {
    public long wonderfulSubstrings(String word) {
        // 前缀和（sumMod2Mask[i] = 0 表示该字母出现偶数次，sumMod2Mask[i] = 1 表示该字母出现奇数次）
        int sumMod2Mask = 0;

        // 该字符串由前十个小写英文字母组成（'a' 到 'j'）
        // 某个前缀和出现了多少次
        int[] cnt = new int[1 << 10];
        cnt[0] = 1;
        long res = 0L;
        for (char ch : word.toCharArray()) {
            // 模2 下的加法 相当于 异或
            sumMod2Mask ^= 1 << (ch - 'a');

            // 所有字母均出现偶数次
            res += cnt[sumMod2Mask];

            // 枚举其中一个字母出现奇数次
            for (int k = 1; k < (1 << 10); k = k << 1) {
                res += cnt[sumMod2Mask ^ k];
            }
            cnt[sumMod2Mask]++;
        }
        return res;
    }
}

哈希 首次出现下标

1124. 表现良好的最长时间段

import java.util.HashMap;
import java.util.Map;

public class Solution1124 {
    public int longestWPI(int[] hours) {
        int n = hours.length;
        Map<Integer, Integer> sumMap = new HashMap<>();
        int sum = 0;
        int max = 0;
        for (int j = 0; j < n; j++) {
            // 求解区间分数和大于 0 的最长区间长度
            sum += hours[j] > 8 ? 1 : -1;
            if (sum > 0) {
                // [0, j]
                max = Math.max(max, j + 1);
            } else {
                if (sumMap.containsKey(sum - 1)) {
                    int i = sumMap.get(sum - 1);
                    // [0,j] - [0,i] = (i,j]
                    max = Math.max(max, j - i);
                }
            }
            if (!sumMap.containsKey(sum)) {
                sumMap.put(sum, j);
            }
        }
        return max;
    }
}

二维前缀和 & 二维差分

2132. 用邮票贴满网格图

public class Solution2132 {
    public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
        int M = grid.length;
        int N = grid[0].length;

        PrefixSum2d prefixSum2d = new PrefixSum2d(grid);
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                // 每个格子要么为 0 （空）要么为 1 （被占据）。
                if (grid[i][j] == 0) {
                    int row2 = i + stampHeight - 1;
                    int col2 = j + stampWidth - 1;
                    // 可以贴邮票
                    if (row2 < M && col2 < N && prefixSum2d.sumRegion(i, j, row2, col2) == 0) {
                        prefixSum2d.rangeAdd(i, j, row2, col2, 1);
                    }
                }
            }
        }

        // 原数组
        int[][] originArr = prefixSum2d.originalArray();
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 0 && originArr[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    private static class PrefixSum2d {
        private final int M;
        private final int N;
        private final int[][] preSum2d;
        private final int[][] diff2d;

        public PrefixSum2d(int[][] matrix) {
            this.M = matrix.length;
            this.N = matrix[0].length;
            // 预处理前缀和
            preSum2d = new int[M + 1][N + 1];
            for (int i = 1; i <= M; i++) {
                for (int j = 1; j <= N; j++) {
                    // 当前格 = 上 + 左 - 左上 + 原值
                    preSum2d[i][j] = preSum2d[i - 1][j] + preSum2d[i][j - 1] - preSum2d[i - 1][j - 1] + matrix[i - 1][j - 1];
                }
            }
            // 差分 init
            diff2d = new int[M + 1][N + 1];
        }

        // 二维前缀和：求 matrix [row1,col1] 到 [row2,col2] 的累加和
        public int sumRegion(int row1, int col1, int row2, int col2) {
            return preSum2d[row2 + 1][col2 + 1] - preSum2d[row2 + 1][col1] - preSum2d[row1][col2 + 1] + preSum2d[row1][col1];
        }

        // 二维差分：matrix [row1,col1] 到 [row2,col2] 全部增加 inc
        public void rangeAdd(int row1, int col1, int row2, int col2, int inc) {
            diff2d[row1][col1] += inc;
            diff2d[row1][col2 + 1] -= inc;
            diff2d[row2 + 1][col1] -= inc;
            diff2d[row2 + 1][col2 + 1] += inc;
        }

        // 二维差分：获取原数组
        public int[][] originalArray() {
            int[][] res = new int[M][N];
            // 0 行
            res[0][0] = diff2d[0][0];
            for (int j = 1; j < N; j++) {
                res[0][j] = res[0][j - 1] + diff2d[0][j];
            }
            // 0 列
            for (int i = 1; i < M; i++) {
                res[i][0] = res[i - 1][0] + diff2d[i][0];
            }
            // 1 行 1 列。。。
            for (int i = 1; i < M; i++) {
                for (int j = 1; j < N; j++) {
                    res[i][j] = res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1] + diff2d[i][j];
                }
            }
            return res;
        }
    }
}

高维前缀和

LQ231209T4

SOSDP，Sum over Subsets dynamic programming

import java.util.Scanner;

public class LQ231209T4 {
    static int n;
    static int[] a;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(solve());
    }

    private static String tle() {
        long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if ((a[i] & a[j]) == 0) {
                    ans++;
                }
            }
        }
        return String.valueOf(ans);
    }

    static final int K = 20;

    private static String solve() {
        long[] f = new long[1 << K];
        for (int v : a) {
            f[v]++;
        }
        // 高维前缀和
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < 1 << K; j++) {
                if ((j >> i & 1) == 1) {
                    f[j] += f[j ^ (1 << i)];
                }
            }
        }

        int full = (1 << 20) - 1;
        long ans = 0;
        for (int v : a) {
            ans += f[full & ~v];
        }
        return String.valueOf(ans);
    }
}

（全文完）