数据结构——查分数组

数据结构——查分数组介绍查分数组是一个数据结构。相当于前缀和的逆运算。查分数组的功能是修改区间,查询点。修改区间的时间复杂度是O(1).查询点的时间复杂度是O(n)。若配合树状数组时间复杂度可达到O(logn)。修改区间操作x位置加上修改量,y+1位置减去修改量。这样就相当于整个区间的元素都修改了。staticvoidupdate(intx,inty,intz){ b[x]+=z; b[y+1]-=z;}查询刚刚修改方便了,但是查询的时候就需要全部都加一遍了。staticint

大家好,又见面了,我是你们的朋友全栈君。

介绍

查分数组是一个数据结构。相当于前缀和的逆运算。
查分数组的功能是修改区间,查询点。
修改区间的时间复杂度是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 */
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130612.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 软件测试用例模板

    软件测试用例模板软件测试用例模板

  • python的第三方库在哪里_第三方付款情况说明

    python的第三方库在哪里_第三方付款情况说明Python第三方库说明在哪里?0.可以跳过的介绍1.找到要第三方库0.可以跳过的介绍近期开始补习各种Python的知识,看着网上大神们python用得出神入化轻舞飞扬,虽然跟着一起安装了几十个第三方库却不会怎么用,这就尴尬了,网上找了一圈没有一个明说的,遂写此文。1.找到要第三方库Pycharm途径:1.点击File———>Setting———>搜索栏关键字pr…

  • 线程和进程有什么区别(简单介绍)[通俗易懂]

    线程和进程有什么区别(简单介绍)[通俗易懂] 线程和进程有什么区别(简单介绍) 简单介绍一、线程的基本概念  线程是进程中执行运算的最小单位,是进程中的一个实体,是被系统独立调度和分派的基本单位,线程自己不拥有系统资源,只拥有一点在运行中必不可少的资源,但它可与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和撤消另一个线程,同一进程中的多个线程之间可以并发执行。   …

  • Valid Number

    Valid Number

  • navicat15激活码序列号(注册激活)

    (navicat15激活码序列号)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html83PVI25FMO-eyJsaWNlbnNlSW…

  • 环境变量和shell变量

    环境变量和shell变量变量分类变量分为环境变量和shell变量环境变量相当于全局变量,适用于当前SHELL(父进程)和由父进程调用的子进程,如打开编辑器vi、脚本、应用或是再打开一个子shell。shell变量就是当前shell使用的变量了,它只是“本地“有效,相当于本地变量,不适用于其他子进程,只在当前shell生命周期内有效永久变量不管是自定义的变量还是通过export导为环境变量的自定义变量都只是在shell生命周期内有效,这样的变量就是临时变量,如果我想设置一个变量使其永久生效怎么办呢?可以修改两个配置文

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号