HDU1556 树状数组,线段树区间更新两种方法(主要树状数组)

2023-10-12 02:08

本文主要是介绍HDU1556 树状数组,线段树区间更新两种方法(主要树状数组),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

树状数组
#include <stdio.h>
#include <string.h>
const int MAXN=110000;
int n,c[MAXN];
int lowbit(int x)
//计算2^k
{x=x&-x;return x;
}
void update(int num,int val)
//向下查询,num是要更新的子节点,val是要修改的值
{while(num>0){c[num]+=val;num-=lowbit(num);}
}
int getSum(int num)
//向上统计每个区间被染色的次数
{int sum=0;while(num<=n){sum+=c[num];num+=lowbit(num);}return sum;
}
int main()
{int a,b;while(scanf("%d",&n),n){memset(c,0,sizeof(c));for(int i=0;i<n;i++){scanf("%d%d",&a,&b);//将b以下区间+1update(b,1);//将a以下区间-1update(a-1,-1);}for(int j=1;j<n;j++){printf("%d ",getSum(j));}printf("%d\n",getSum(n));}return 0;
}

线段树

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;int ans[1000000],n;struct node
{int l,r,n;
} a[1000000];void init(int l,int r,int i)
{a[i].l = l;a[i].r = r;a[i].n = 0;if(l!=r){int mid = (l+r)>>1;init(l,mid,2*i);init(mid+1,r,2*i+1);}
}void insert(int i,int x,int y)
{if(a[i].l == x && a[i].r == y)//找到要刷的气球区间,更新其被刷的次数+1a[i].n++;else{int mid = (a[i].l+a[i].r)>>1;if(y<=mid)insert(2*i,x,y);else if(x>mid)insert(2*i+1,x,y);else{insert(2*i,x,mid);insert(2*i+1,mid+1,y);}}
}void add(int x)
{int i;for(i = a[x].l; i<=a[x].r; i++)//该区间所有编号都被刷了一次ans[i]+=a[x].n;if(a[x].l == a[x].r)return;add(2*x);add(2*x+1);
}int main()
{int x,y,i;while(~scanf("%d",&n),n){init(1,n,1);for(i = 1; i<=n; i++){scanf("%d%d",&x,&y);insert(1,x,y);}memset(ans,0,sizeof(ans));add(1);printf("%d",ans[1]);for(i = 2; i<=n; i++)printf(" %d",ans[i]);printf("\n");}return 0;
}

这里转载了两个别人的代码。感觉树状数组简单好多。。。

这篇关于HDU1556 树状数组,线段树区间更新两种方法(主要树状数组)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/192474

相关文章

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

Nginx安全防护的多种方法

《Nginx安全防护的多种方法》在生产环境中,需要隐藏Nginx的版本号,以避免泄漏Nginx的版本,使攻击者不能针对特定版本进行攻击,下面就来介绍一下Nginx安全防护的方法,感兴趣的可以了解一下... 目录核心安全配置1.编译安装 Nginx2.隐藏版本号3.限制危险请求方法4.请求限制(CC攻击防御)

SpringBoot中六种批量更新Mysql的方式效率对比分析

《SpringBoot中六种批量更新Mysql的方式效率对比分析》文章比较了MySQL大数据量批量更新的多种方法,指出REPLACEINTO和ONDUPLICATEKEY效率最高但存在数据风险,MyB... 目录效率比较测试结构数据库初始化测试数据批量修改方案第一种 for第二种 case when第三种

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

MyBatis-Plus通用中等、大量数据分批查询和处理方法

《MyBatis-Plus通用中等、大量数据分批查询和处理方法》文章介绍MyBatis-Plus分页查询处理,通过函数式接口与Lambda表达式实现通用逻辑,方法抽象但功能强大,建议扩展分批处理及流式... 目录函数式接口获取分页数据接口数据处理接口通用逻辑工具类使用方法简单查询自定义查询方法总结函数式接口

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、

JAVA中安装多个JDK的方法

《JAVA中安装多个JDK的方法》文章介绍了在Windows系统上安装多个JDK版本的方法,包括下载、安装路径修改、环境变量配置(JAVA_HOME和Path),并说明如何通过调整JAVA_HOME在... 首先去oracle官网下载好两个版本不同的jdk(需要登录Oracle账号,没有可以免费注册)下载完

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

Java 方法重载Overload常见误区及注意事项

《Java方法重载Overload常见误区及注意事项》Java方法重载允许同一类中同名方法通过参数类型、数量、顺序差异实现功能扩展,提升代码灵活性,核心条件为参数列表不同,不涉及返回类型、访问修饰符... 目录Java 方法重载(Overload)详解一、方法重载的核心条件二、构成方法重载的具体情况三、不构