数据结构——查分数组

数据结构——查分数组介绍查分数组是一个数据结构。相当于前缀和的逆运算。查分数组的功能是修改区间,查询点。修改区间的时间复杂度是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)


相关推荐

  • 机器学习之KNN(k近邻)算法详解

    机器学习之KNN(k近邻)算法详解1-1机器学习算法分类一、基本分类:①监督学习(Supervisedlearning)数据集中的每个样本有相应的“正确答案”,根据这些样本做出预测,分有两类:回归问题和分类问题。步骤1:数据集的创建和分类步骤2:训练步骤3:验证步骤4:使用(1)回归问题举例例如:预测房价,根据样本集拟合出一条连续曲线。(2)…

  • docker中宿主机与容器(container)互相拷贝传递文件的方法「建议收藏」

    docker中宿主机与容器(container)互相拷贝传递文件的方法「建议收藏」转载请注明出处:http://blog.csdn.net/dongdong9223/article/details/71425077本文出自【我是干勾鱼的博客】前面讲解过如何进入、退出docker的container。今天来讲一下在docker中宿主机与容器(container)互相拷贝传递文件的方法。1从宿主机拷贝文件到容器拷贝方式为:dockercp容器名:要拷贝的宿主机的文件名

  • fun.xls.exe病毒分析、查杀及批处理清除「建议收藏」

    fun.xls.exe病毒分析、查杀及批处理清除「建议收藏」大家经常用U盘,也许就和我一样,遇到过这种叫fun.xls.exe的病毒.fun.xle.exe是一种叫做U盘病毒tel.xls.exe的变种,会在电脑里注入文件,这个病毒目前应该有四个变种.用记事本打开AUTORUN是如下代码:[AutoRun]open=fun.xls.exeshellexecute=fun.xls.exeshell\Auto\command=fu…

  • s3c2440启动过程分析

    s3c2440启动过程分析2440启动过程分析作者:王辉 2440启动过程算是一个难点,不太容易理解,而对于2440启动过程的理解,影响了后面裸机代码执行流程的分析,从而看出2440启动过程的重要性。 1 2440启动方式和启动方式选择在S3C2440的datasheet《S3C2440A_UserManual_Rev13.pdf》中搜索map,可以在第5章中搜索到下图。 从此

  • 单片机引脚控制继电器最简单的电路方式

    单片机引脚控制继电器最简单的电路方式首先要明确一点:单片机不能直接控制继电器,不管是3v的继电器还是5v的继电器。原因:比如51单片机和msp430单片机,引脚不能直接接继电器。虽然引脚的电压足够,但是由于电流不够,所以本应该闭合的线圈不会闭合。需要增加一个三极管来放大电流。说是放大电流,其实本质上是把引脚当成一个开关来控制真正3.3v电压的开合。下图是在实践中自己设计的可以正常工作的继电器模块。

  • 惠普电脑u盘重装系统步骤_惠普电脑优盘装系统步骤「建议收藏」

    惠普电脑u盘重装系统步骤_惠普电脑优盘装系统步骤「建议收藏」惠普是一家全球性的科技公司,旗下有三大业务,计算机就是其中一种。购买惠普电脑的朋友不在少数,给我们提供了科技领先的产品和服务。那么惠普电脑如何安装系统呢?下面就教大家惠普电脑优盘装系统步骤,有需要的朋友们赶紧来学习一下吧。惠普电脑优盘装系统步骤阅读1、打开浏览器搜索云骑士官网,找到云骑士官网并点击打开。2、首先在官网下载云骑士一键重装系统软件,下载好以后打开云骑士装机大师。3、将U盘插在电脑的U…

发表回复

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

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