数据结构——查分数组

介绍

查分数组是一个数据结构。相当于前缀和的逆运算。 查分数组的功能是修改区间，查询点。 修改区间的时间复杂度是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; } 查询 刚刚修改方便了，但是查询的时候就需要全部都加一遍了。 static int sum(int x){ int ans=0; for(int i=1;i<=x;i++) ans+=b[i]; return ans; } 预处理 b[1]=a[1]; for(int i=2;i<=n;i++) b[i]=a[i]=a[i-1];

算法思路

地推建立查分数组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 */