前缀和与差分_前缀和与差分 求和

图示：

a数组是b数组的前缀和

b数组是a数组的差分

公式：

前缀和与差分两者互为逆运算

前缀和：

a[i]=a[i-1]+b[i]
我们可以得出a[i]就是b数组的前i项之和。

差分：

b[i]=a[i]-a[i-1]
我们可以得出b[i]就是a[i]与a[i-1]的差。

用途：

前缀和可以将数组区间的求和运算从O(n)级别降低到O(1)级别

差分可以将一个区间的增加与减少运算从O(n)级别降低到O(1)级别

差分例题：

题目： D. Constant Palindrome Sum.

分析：

每次判断当前数目可变的区间与变化个数，对区间进行差分运算

AC代码：

package C636;

import java.util.*;

public class D {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		while(t-->0){
			int n=sc.nextInt(),k=sc.nextInt();
			int arr[]=new int[n];
			int c[]=new int[2*k+1];
			for(int i=0;i<n;i++){
				arr[i]=sc.nextInt();
			}
			for(int i=0;i<n/2;i++){
				int x=i,y=n-i-1;
				int min=Math.min(arr[x], arr[y])+1;
				int max=Math.max(arr[x], arr[y])+k;
				int mid=arr[x]+arr[y];
				c[1]+=2;
				c[min]--;
				c[mid]--;
				if(mid!=2*k){
					c[mid+1]++;
				}
				if(max!=2*k){
					c[max+1]++;
				}
			}
			int ans=2*n;
			for(int i=1;i<=2*k;i++){
				c[i]+=c[i-1];
				ans=Math.min(ans, c[i]);
			}
			System.out.println(ans);
		}
	}
}


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