前缀和

方法

当计算一个数组多个区间的和时，我们可能首先想到的是使用多重for循环,比如给了一个长度为n的序列，有m个询问，每个询问代表一个区间l r 那么就要计算n*m次时间复杂度是次方，如果n和m稍微大一点很容易会造成超时，那么此时就要用到前缀和

用一个sum数组保存原数组前i个元素的和 sum[i] 表示前i个元素的和，sum[R]-sum[ L-1] 就是 [L,R] 的区间和

计算[0,i] 的前缀和时 sum[0]=arr[0] sum[i]=sum[i-1]+arr[i]

在这里插入图片描述但是要考虑一种情况就是L=0 那么sum[L,R]=sum[R]

蓝桥杯例题

在这里插入图片描述

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
      // 读取数列的长度 n 和 k
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        // 存储数列元素的数组
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        // 前缀和数组，长度为 n + 1，prefixSum[0] 初始为 0
        long[] prefixSum = new long[n + 1];
        // 记录每个余数出现的次数，长度为 k
        int[] count = new int[k];
        // 余数为 0 的情况初始有一个，即 prefixSum[0] = 0
        count[0] = 1;
        long res = 0;
        // 遍历数组计算前缀和
        for (int i = 1; i <= n; i++) {
            // 计算当前位置的前缀和
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
            // 计算前缀和对 k 取模的余数
            int r = (int) (prefixSum[i] % k);
            // 累加满足条件的区间个数
            res += count[r];
            // 更新该余数出现的次数
            count[r]++;
        }
        System.out.println(res);
	        scanner.close();
    }
}

差分

方法

差分的情况的适用于对一个区间[L,R] +value的操作差分实际上就是前缀和的逆运算将差分数组进行前缀和运算得到的就是原数组

在这里插入图片描述算法：[L,R]+val <=> d[L]+val,d[R+1] -val 那么为什么是这样算？

如果现在有个差分数组全为0 的情况在这里插入图片描述在d[1] 的位置加上1 那么得到的sum中 sum[ 1，N] 都会加上1 如果我想只对于某个区间进行加1的操作一定需要在某个位置d[？]进行-1的操作来抵消在这区间以后的加1操作那么这个位置就是d[R+1]

蓝桥杯例题

在这里插入图片描述



import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int count = scan.nextInt();
        long[] arr = new long[n];
        long[] diff = new long[n];

        for (int i = 0; i < n; i++) {
            arr[i] = scan.nextLong();
            if (i == 0) {
                diff[i] = arr[i];
            } else {
                diff[i] = arr[i] - arr[i - 1];
            }
        }

        for (int i = 0; i < count; i++) {
            int l = scan.nextInt();
            int r = scan.nextInt();
            long x = scan.nextLong();
            diff[l - 1] += x;
            if (r < n) {
                diff[r] -= x;
            }
        }

        arr[0] = diff[0];
        if (arr[0] < 0) {
            arr[0] = 0;
        }
        for (int i = 1; i < n; i++) {
            arr[i] = arr[i - 1] + diff[i];
            if (arr[i] < 0) {
                arr[i] = 0;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(' ');
            }
        }
    }
}

查看 CSDN 原文

前缀和与差分（一维）

前缀和

方法

蓝桥杯例题

差分

方法

蓝桥杯例题