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

相关文章

SQL Server配置管理器无法打开的四种解决方法

《SQLServer配置管理器无法打开的四种解决方法》本文总结了SQLServer配置管理器无法打开的四种解决方法,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录方法一:桌面图标进入方法二:运行窗口进入检查版本号对照表php方法三:查找文件路径方法四:检查 S

MyBatis-Plus 中 nested() 与 and() 方法详解(最佳实践场景)

《MyBatis-Plus中nested()与and()方法详解(最佳实践场景)》在MyBatis-Plus的条件构造器中,nested()和and()都是用于构建复杂查询条件的关键方法,但... 目录MyBATis-Plus 中nested()与and()方法详解一、核心区别对比二、方法详解1.and()

golang中reflect包的常用方法

《golang中reflect包的常用方法》Go反射reflect包提供类型和值方法,用于获取类型信息、访问字段、调用方法等,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值... 目录reflect包方法总结类型 (Type) 方法值 (Value) 方法reflect包方法总结

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

Python中注释使用方法举例详解

《Python中注释使用方法举例详解》在Python编程语言中注释是必不可少的一部分,它有助于提高代码的可读性和维护性,:本文主要介绍Python中注释使用方法的相关资料,需要的朋友可以参考下... 目录一、前言二、什么是注释?示例:三、单行注释语法:以 China编程# 开头,后面的内容为注释内容示例:示例:四

一文详解Git中分支本地和远程删除的方法

《一文详解Git中分支本地和远程删除的方法》在使用Git进行版本控制的过程中,我们会创建多个分支来进行不同功能的开发,这就容易涉及到如何正确地删除本地分支和远程分支,下面我们就来看看相关的实现方法吧... 目录技术背景实现步骤删除本地分支删除远程www.chinasem.cn分支同步删除信息到其他机器示例步骤

在Golang中实现定时任务的几种高效方法

《在Golang中实现定时任务的几种高效方法》本文将详细介绍在Golang中实现定时任务的几种高效方法,包括time包中的Ticker和Timer、第三方库cron的使用,以及基于channel和go... 目录背景介绍目的和范围预期读者文档结构概述术语表核心概念与联系故事引入核心概念解释核心概念之间的关系

MySQL追踪数据库表更新操作来源的全面指南

《MySQL追踪数据库表更新操作来源的全面指南》本文将以一个具体问题为例,如何监测哪个IP来源对数据库表statistics_test进行了UPDATE操作,文内探讨了多种方法,并提供了详细的代码... 目录引言1. 为什么需要监控数据库更新操作2. 方法1:启用数据库审计日志(1)mysql/mariad