数据结构——查分数组

介绍

查分数组是一个数据结构。相当于前缀和的逆运算。
查分数组的功能是修改区间，查询点。
修改区间的时间复杂度是O(1).
查询点的时间复杂度是O(n)。若配合树状数组时间复杂度可达到O(log n)。

• 修改区间操作
  x位置加上修改量，y+1位置减去修改量。这样就相当于整个区间的元素都修改了。

static void update(int x,int y,int z){
	b[x]+=z;
	b[y+1]-=z;
}
1
2
3
4

• 查询
  刚刚修改方便了，但是查询的时候就需要全部都加一遍了。

static int sum(int x){
	int ans=0;
	for(int i=1;i<=x;i++) ans+=b[i];
	return ans;
}
1
2
3
4
5

• 预处理

	b[1]=a[1];
	for(int i=2;i<=n;i++) b[i]=a[i]=a[i-1];
1
2

算法思路

地推建立查分数组s。使用递推式:c[i]=a[i-1]-a[i]。
将s[left]+k,s[right+1]-k可以实现区间修改的目的。
单点查询：求前缀和。
还原原数组的方式：s[i]+=s[i-1]

D - Tallest Cow

原题链接
这道题数据卡的很死。这种方法应该不是最优。我按原题给的最大数据范围开了数组空间。然后超了内存。

import java.io.IOException;
import java.util.Scanner;

public class Main {
	/*
	 * POJ-3263  D - Tallest Cow 
	 * 查分数组+前缀和
	 */
	static int N,I,R,H,a,b,M,cf[];
	static boolean vis[][];
	
	public static void main(String []args)throws IOException {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();I=sc.nextInt();
		H=sc.nextInt();R=sc.nextInt();
		M=N+1;
		vis=new boolean [M][M];
		cf=new int [N+1];
		for(int i=1;i<=R;i++) {
			a=sc.nextInt();
			b=sc.nextInt();
			if(a>b) { int temp=a;a=b;b=temp; }
			if(!vis[a][b]) {
				cf[a+1]--;
				cf[b]++;
				vis[a][b]=true;
			}
		}
		int res=0;
		for(int i=1;i<=N;i++) {
			res+=cf[i];
			System.out.println(H+res);
		}
	}
}
/*
9 3 5 5
1 3
5 3
4 3
3 7
9 8

5
4
5
3
4
4
5
5
5
*/
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