前缀和与差分

以下的代码中，统一使用arr表示原数组，sum表示前缀和数组，B表示差分数组

• 前缀和

  某个元素与它之前的所有元素之和。

  • 一维前缀和：

    sum[i] = sum[i-1] + arr[i];

  • 二维前缀和：

    sum[i][j] = arr[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];

  • 例题：acwing1230

    同余定理的性质：对于同一个除数，如果有两个整数同余，那么它们的差一定能被这个除数整除。

    所以在此题中，（sum[r]-sum[l-1])%k==0,则必有sum[r]%k==sum[l-1]%k。所以最后的答案为拥有相同的余数的点的组合。

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class Main {
    	private static int[] sum = new int[100005];
    
    	public static void main(String[] args) throws IOException {
    		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    		String[] str = bf.readLine().split(" ");
    		int n = Integer.parseInt(str[0]);
    		int k = Integer.parseInt(str[1]);
    		int[] cnt = new int[k];
            
            //只要sum[r]%k==0,[0,r]肯定是所要区间
            //在下面的循环中，0这个点无法取到，所以先加上1
    		cnt[0] = 1;
    		for (int i = 1; i <= n; i++) {
    			int num = Integer.parseInt(bf.readLine());
                //对前缀和取模
    			sum[i] = (num + sum[i - 1]) % k;
                //持有该余数的端点数量加1
    			cnt[sum[i]]++;
    		}
            
    		long ans = 0;
            //持有相同余数的各端点两两组合
            //余数肯定在0~k-1范围内
    		for (int i = 0; i < k; i++)
    		//转为long，否则在没有赋值之前，计算时已经溢出；也可直接将cnt定义为long[]
    			ans += (long)cnt[i] * (cnt[i] - 1) / 2;
            
    		System.out.println(ans);
    
    

• 差分

  每个元素与前一个元素的差值。

  • 一维差分：

    B[i] = arr[i] - arr[i-1];
    //给[l,r]区间里的元素都加上c
    B[l] += c;
    B[r+1] -= c;
    //后面再求差分数组的前缀和就得到原数组了

    可以这样理解，将左端点处的值从数组上向右推移，而它右边的值与它的相对位置不变（差值不变），自然就相当于都加上了c；再把右端点右边的值往左推移c的长度，抵消之前左端点推移对他的作用。

  • 二维差分：

    B[i][j] = arr[i][j] - arr[i][j-1] - arr[i-1][j] + arr[i-1][j-1];

    这个公司是由二维前缀和公示得出，将原数组看作前缀和数组，差分数组自然就是原数组了。

• 前缀和与差分的关系：

  前缀和与差分互为逆运算。所以知道了前缀和怎么求，就知道了差分怎么求。