大家好，又见面了，我是你们的朋友全栈君。
介绍
查分数组是一个数据结构。相当于前缀和的逆运算。
查分数组的功能是修改区间，查询点。
修改区间的时间复杂度是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 */
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/130612.html原文链接：https://javaforall.net
