环球观察:树状数组和线段树有什么区别?树状数组和线段树有什么关系?
树状数组,学长很早之前讲过,最近才重视起来,enmmmm。。。
树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。
树状数组和线段树很像,但能用树状数组解决的问题,基本上都能用线段树解决,而线段树能解决的树状数组不一定能解决。相比较而言,树状数组效率要高很多。
【资料图】
观察这个图ヾ(◍°∇°◍)ノ゙ C1 = A1 C2 = A1 + A2 C3 = A3 C4 = A1 + A2 + A3 + A4 C5 = A5 C6 = A5 + A6 C7 = A7 C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 ... C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16 感觉很神奇,是怎么做到这样的呢。 哈,全靠 二进制。 将数组的节点序号都转化成二进制。 就是这样的: 1--->001 C1 = A1 2--->010 C2 = A1 + A2 3--->011 C3 = A3 4--->100 C4 = A1 + A2 + A3 + A4 5--->101 C5 = A5 6--->110 C6 = A5 + A6 7--->111 C7 = A7 8--->1000 C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 但是这又有什么关系呢?!!!∑(゚Д゚ノ)ノ 度娘说了: 这里有一个有趣的性质: 设节点编号为x,那么这个节点管辖的区间为2^k(其中k为x二进制末尾0的个数)个元素。因为这个区间最后一个元素必然为Ax, 所以很明显:Cn = A(n – 2^k + 1) + A(n-2^k+2)+... + An 什么意思呢?举个栗子,1对应的二进制是001,二进制末尾0的个数为0,所以k=0, 所以C1=A(1-2^k+1)+...An 就是C1=A(1-2^0+1)=A(1); 再来个栗子,4对应的二进制是100,二进制末尾0的个数为2,所以k=2, 所以C4=A(4-2^2+1)+A(4-2^2+2)+...+A(4)=A(1)+A(2)+A(3)+A(4); 再搞不懂就自己再手推几个数试试就可以了。 至于怎么得出来的这个神奇的东西,就是靠 二进制啦。总结出来这个式子的人好厉害((✧◡✧)) 接下来就是怎么代码实现这个呢? 就是要靠神奇的 lowbit了。
int lowbit(int x){ return x&(-x);}
x&(-x)就是整数x与其相反数(负号取反)的按位与:相同位的两个数字都为1,则为1;若有一个不为1,则为0,即:1&1=1,0&1=0,0&0=0;
计算机中负数使用对应正数的补码来表示。
-x就是x对应的二进制数先各位取反,0变成1,1变成0。然后最低位加1。
举个栗子,4对应二进制为100;-4对应的为011+1=100,所以为(100)&(100)所以为100。
知道这个又能干嘛呀,就可以进行区间查询啦。
区间查询利用C[i]求A数组前i个的和;
//代码1:int SUM(int n){ int s=0; while(n>0){ s+=c[n]; n-=lowbit(n); } return s;}
//代码2:int SUM(int n){ int s=0; for(int i=n;i>0;i-=lowbit(i)) s+=c[i]; return s;}
两个代码哪个好理解理解哪个。
接着刚刚举的栗子4,求A数组前4个数的和;
lowbit(4)得出100;然后100就是4,所以为s+=c[4];此时i=4,4-lowbit(4)=100-100=0;结束。
再举个栗子7,求前7个数的和,就是s+=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7];
因为
1--->001 C1 = A1 2--->010 C2 = A1 + A2 3--->011 C3 = A3 4--->100 C4 = A1 + A2 + A3 + A4 5--->101 C5 = A5 6--->110 C6 = A5 + A6 7--->111 C7 = A7 8--->1000 C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 所以为C[4]+C[6]+C[7]; 就是C[100]+C[110]+C[111]; 首先s+=c[7]; 然后lowbit[7]=(111)&(001)=001;此时i=7,所以为7-lowbit(7)=111-001=110,110就是6;s+=c[6]; lowbit(6)=(110)&(010)=010;此时i=6,所以为6-lowbit(6)=110-010=100,100就是4;s+=c[4]; lowbit(4)=(100)&(100)=100;此时i=4,所以为4-lowbit(4)=100-100=0,结束。 所以得到A数组中前7个数的和为C[7]+C[6]+C[4]; 不懂的话再自己手推一个数就差不多懂了。 接下来就是单点更新。 单点更新要从下往上依次更新。
//代码1:void add(int x){ while(x<=N){ ++a[x]; x+=lowbit(x); }}
//代码2:void add(int x,int y){ for(int i=x;i<=n;i+=lowbit(i)) c[i]+=y;}
更新过程仔细想一想就是查询过程的逆过程;
举个栗子,更新A1,还要继续更新C[1],C[2],C[4],C[8];
就是C[001],C[010],C[100],C[1000];
i=1;C[1]+=A[1];
lowbit(1)=(001)&(001)=001;此时i=1,所以为1+lowbit(1)=001+001=010,010就是2;C[2]+=A[1];
lowbit(2)=(010)&(110)=010;此时i=2,所以为2+lowbit(2)=010+010=100,100就是4;C[4]+=A[1];
lowbit(4)=(100)&(100)=100;此时i=4,所以为4+lowbit(4)=100+100=1000,1000就是8;C[8]+=A[1];结束。
好了,理解了树状数组就开始贴代码了。(;´д`)ゞ
HDU1541-Stars
Stars
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 10611 Accepted Submission(s): 4240
Problem DescriptionAstronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars. For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it"s formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3. You are to write a program that will count the amounts of the stars of each level on a given map. InputThe first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate. OutputThe output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1. Sample Input5 1 1 5 1 7 1 3 3 5 5 Sample Output1 2 1 1 0 代码:
1 #include2 #include3 #include4 #include5 #include6 #include7 #include8 #include9 #include10 #include11 #include12 #include13 #include14 #include15 #include16 #include17 #include18 #include19 using namespace std;20 typedef long long ll;21 22 const double PI=acos(-1.0);23 const double eps=1e-6;24 const ll mod=1e9+7;25 const int inf=0x3f3f3f3f;26 const int maxn=1e5+10;27 const int maxm=100+10;28 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);29 30 31 int a[maxn],ans[maxn];32 33 int lowbit(int x)34 {35 return x&(-x);36 }37 38 int getsum(int n)39 {40 int ans=0;41 for(int i=n;i>0;i-=lowbit(i))42 ans+=a[i];43 return ans;44 }45 46 void add(int x)47 {48 for(int i=x;i<=maxn;i+=lowbit(i))49 ++a[i];50 }51 52 int main(){53 int n,x,y;54 while(~scanf("%d",&n)){55 memset(a,0,sizeof(a));56 memset(ans,0,sizeof(ans));57 for(int i=0;i<N;I++){58 scanf(?%d%d?,&x,&y);59="" x++;60="" ans[getsum(x)]++;61="" add(x);62="" }63="" for(int="" i="0;i<n;i++)64" printf(?%d\n?,ans[i]);65="" }66="" return="" 0;67="" }溜了溜了。。。转载于:https://www.cnblogs.com/ZERO-/p/7523041.html
标签:
相关推荐:
精彩放送:
- []当前信息:【黑苹果】AMDRadeonX3000.kext驱动显卡方案
- []QQ登录超时怎么解决?解决QQ登录超时问题的办法
- []全球滚动:java基础知识:java绘图和Graphics类的含义是什么?
- []世界新动态:什么是单元测试?对开发程序有什么好处?
- []环球观察:树状数组和线段树有什么区别?树状数组和线段树有什么关系?
- []每日短讯:微心愿(2023.04.10)
- []佳能广角变焦镜头大全 收藏起来
- []环球观焦点:国产十大平板电脑排行榜 国产平板电脑哪款好?
- []【快播报】清明有什么来历?关于清明的来历的资料
- []中秋节手抄报模板制作大全 双节手抄大全
- []全球热议:dnf野猪怎么打?dnf打野猪有什么方法?
- []环球热点评!陈思诚和佟丽娅一起演了什么电影?看完你就明白了
- []360极速浏览器如何导出数据和收藏夹?360极速浏览器导出数据和收藏夹
- []视点!ios14.8系统好用吗?ios14.8值得更新吗?
- []世界观察:浦东建设一季度新签工程项目金额97.14亿元 同比增加80%
- []录音软件哪个好?推荐几款最常用的录机软件
- []西游降魔篇几几年上映的?主演阵容曝光
- []translate是什么意思?translate的用法介绍
- []焦点快报!如何清洗喷墨打印机的打印头?喷墨打印机喷头清洗的方法
- []环球要闻:round是什么意思?RUND32.dll加载出错怎么办?
- []资讯:360云盘怎么转存百度云盘?360云盘转存百度云盘详细步骤
- []母亲节发多少红包给妈妈合适?吉利数字含义介绍
- []蓖麻怎么种植?关于蓖麻种植的介绍
- []热门:电脑关不上机怎么办?shutdown定时关机命令详解
- []焦点观察:如何使用PTDD分区表?详细教程介绍
- []环球热头条丨java中的死锁如何优化?mysql之锁优化
- []【天天新视野】华为手机如何管理应用权限?华为手机管理应用权限步骤
- []成都特警基地内的网红打卡地 你去过几个?
- []天天快消息!诺基亚800c如何刷机?800c诺基亚刷机步骤介绍及刷机方法
- []【世界快播报】千金药业:公司千金大药房全国布局没有政策限制
- []全球快报:准考证怎么打印?计算机二级考试准考证打印流程及注意事项
- []世界热头条丨K8s安装部署怎么操作?K8S集群安装部署及操作说明
- []儿童玩具店怎么装修效果图?玩具店装修设计的七大要点
- []世界微动态丨腾讯手机管家怎么样?腾讯手机管家详情介绍
- []自行车变速器怎么调节?自行车变速怎么调?
- []环球滚动:明朝历代皇帝年号一览表 明朝帝王世系大全
- []世界新动态:500G硬盘价格多少?500G硬盘品牌价钱性能介绍
- []最新资讯:iPodnano7值不值得购买?iPod nano7配置介绍
- []今日播报!碳纤维发热电缆电地暖怎么样?碳纤维地暖和发热电缆电地暖有什么区别?
- []蚂蚁庄园太阳镜片颜色越深防紫外线效果越好吗?详情介绍
- []常青股份:公司2022年度向特定对象发行A股股票预案已提交交易所,目前处于审核阶段
- []当前热点-维信诺:截至2023年3月31日,公司股东人数为44422户
- []什么叫ied设备?什么是IE浏览器?
- []焦点速读:米老鼠微信主题红包怎么玩?米老鼠微信主题气泡设置教程方法
- []环球播报:dnf跨界石怎么得?地下城与勇士游戏介绍
- []每日热闻!三星大器7732怎么样?三星大器7732深度评测
- []世界通讯!何制作CDlinux的U盘启动方法 资源及下载地址
- []什么是家庭影院?家庭影院的播放系统有哪些?
- []如何使用iPhone手机的各种技巧?超全面iPhone实用技巧汇总
- []如何快速解决打印机喷头堵塞问题?清洗打印机喷头方法
- []世界热推荐:如何安装笔记本的双硬盘?笔记本双硬盘安装步骤
- []Linux新板子起不来及红外屏配置 linux服务器修改内核默认配置的方法
- []天天日报丨多立方浴霸有什么优点? 多立方浴霸优点详细介绍
- []环球微资讯!如何理解数据的保密性和完整性?数据的保密性与完整性
- []世界短讯!舒乐康空气净化器怎么样?空气净化效果好吗?
- []计算机病毒查杀方法有哪些?基于数据流的计算机病毒查杀方法及特征
- []每日速讯:联想平板android版本怎么升级?联想乐Pad A1平板安卓4.0升级操作详细教程
- []当前滚动:程控电话交换机原理是什么?数字程控交换机的基本构成
- []微速讯:知识点补充:什么是互质?互质的详情介绍
- []世界播报:拼多多猜拳游戏怎么玩?怎么进入游戏界面?
- []局域网上任意主机怎么控制?软件实现局域网流量控制
- []每日简讯:【游戏设计】3.2详细设计游戏的操作流程
- []全球时讯:抖音时间倒流是什么?抖音时光倒流使用方法
- []世界热讯:财面儿丨招商蛇口:前3月实现合同销售额722.66亿元 同比增加52.65%
- []最新消息:怎么申请miui12.5内测版本?miui12.5内测答案是什么?
- []windows7系统下的MTU值如何修改?具体操作方法
- []联通4G跳到3G无法上网的原因是什么?如何恢复4G上网?
- []【论文推荐】远程屏幕监控系统项目分析
- []如何用指针申请动态内存?函数的参数是一个指针吗?
- []看热讯:税收分类编码怎么用?开票软件上怎么操作?
- []快报:免费个人网站怎么建立?免费个人网站建立流程
- []全球新资讯:合肥今起恢复公积金异地贷款
- []【世界播资讯】郑州公布2023年680个市重点建设项目名单 总投资1.08万亿元
- []今日热搜:深圳罗湖区发放5000万购车补贴 个人最高获10万元补贴
- []环球快看点丨TD早报 | 锦江与雅高签署谅解备忘录;广州会展业回暖激活商旅市场
- []环球视讯!2021年养老金计算公式 2021养老金计算公式是怎样的
- []焦点速看:双预警!通州明后天阵风8级!伴有沙尘!注意防范——
- []社保卡激活了是不是金融功能就开通了,不一定
- []解局 | 建发一周三城拿地记:“保守观望”和“规模扩张”
- []公积金可以取几次,有以下四种情况
- []环球观天下!悟空保是什么保险如何退保
- []过户车保险费为什么这么贵,原因有以下三点
- []当前热点-公允价值计量的交易性金融资产_公允价值计量
- []动态:思科瑞2022年净利9742.6万同比增长0.38% 总经理马卫东薪酬100万
- []民和股份:公司种鸡减值确认后不转回,待种鸡淘汰时转销对应的减值金额
- []焦点热门:GQY视讯:公司将在提升内部管理促进工作效能提升的同时,更积极主动应对市场机会
- []快来,在这条“樱花大道”邂逅春日浪漫!
- []环球速讯:气垫鞋跑步好吗(气垫鞋跑步好)
- []msci中国指数是什么意思
- []消息!公司一上市就发财了吗
- []世界热点!中国a股总市值
- []路程除以耗油量等于什么
- []当前焦点!重庆证券公司怎么样啊
- []【时快讯】究极绿宝石叉字蝠怎么进化?双腿变翅膀,论叉字蝠神奇的演化路线
- []世界热议:保利发展前三月销售1141.3亿?月内57亿新增四宗地块
- []观天下!公司名称翻译成英文怎么写_公司名称翻译成英文
- []6折人才房将成历史?深圳明确:取消安居房和人才房!
- []观焦点:迎大运动起来 全国劳模与成都职工代表乐动全城
- []当前报道:动态市盈率是什么
- []焦点短讯!gloryhole是什么
- 当前视讯!同花顺模拟炒股输光了需要投资者返还资金吗
- 热点聚焦:股市开盘是什么意思
- 世界最资讯丨福布斯发布2023全球亿万富豪榜;海底捞高层指考核方式升级;爱马仕计划加速扩张中国市场;淘宝APP首页测试新增99特卖频道
- 环球最资讯丨股市怎么样才能赚钱
- 焦点短讯!常青科技:募资加码研发创新,推动核心技术自主可控
- 星期六股票代码是多少
- 当前焦点!金价还会跌吗
- 【环球速看料】电子体温计测量哪个部位最准确
- 世界新消息丨中铁隧道股份有限公司是国企还是央企
- 科创50有哪些股票
- 鳄鱼有舌头吗(鳄鱼的舌头可以防止水倒灌吗)
- 当前观察:每日净值是什么意思
- 当前看点!债权投资减值准备能够转回吗
- 天天滚动:政府为什么不强制贾跃亭回国
- 当前聚焦:福州期货开户哪家公司比较好
- 视焦点讯!汗斑怎么治疗彻底根除_汗斑的最佳治疗方法
- 焦点日报:一季度国家铁路客货运输两旺
- 滚动:刚买了三者没买不计免赔怎么办
- 实时:公积金提前还款
- 医保比例单位和个人怎么计算
- 当前头条:房屋结构安全鉴定报告_房屋结构
- 环球热门:共创储能新时代|比亚迪储能荣膺第十一届储能国际峰会暨展览会ESIE2023多项大奖
- 权威发布:科华数能用户侧储能系统出货量TOP1
- 世界热议:“风起水涌,能量聚拢”| 科陆重磅发布Aqua、Aero、Byzer储能新品
- 特变电工新能源携光储新品亮相储能国际峰会
- 环球焦点!聚焦ESIE2023 | 兴储世纪与行业一起迈步新征程
- 每日热讯!蜂巢能源叠片短刀L500型325Ah储能专用电芯首次亮相储能国际峰会
- 教人开网店的骗局_网上教开网店是真是假
- 【天天聚看点】瑞源电气与您相约第十一届储能国际峰会,我们在6号馆(S86)等您!
- 全球焦点!1八成干的香肠冷冻能放多久?
- 今日热议:房子,竟然成了万恶之源
- 天天简讯:透露大模型进展以及英伟达合作情况,AI操作系统龙头亮了!这些高增长低估值股热度爆棚
- 快资讯:鑫铂股份:修订后的考核指标2应是增长至的概念,公司已就上述笔误进行了更正,详见巨潮资讯网
- 招商银行信用卡咖啡风暴10元来袭!
- 尉氏附近有好玩的地方吗 尉氏有什么好玩儿的吗 尉氏附近有好玩的地方吗在哪
- 空客在华获160架新飞机订单;新东方将布局文旅产业 | 大公司简报
- 天天新消息丨特锐德:有一定的出口外销,但对公司充电业务总收入的影响不大
- 全民推方块好玩吗 全民推方块玩法简介
- 世界信息:qdll基金是什么意思
- 股票分红分的是不是自己的钱
- 新股申购可以撤单吗
- 当前滚动:赵薇娱乐公司叫什么
- 做空为什么跌了还赚钱
- 【世界快播报】中国在台海军演可不是“炸鱼”,而是炸台独的心和胆,矫正美台对台海形势的预期
- 天天时讯:仅租金收入就高达百亿 新城控股连续五年经营性现金流净流入
- 视讯!企业为什么选择在科创板上市
- 【全球新要闻】TE Connectivity @2023年储能国际峰会暨展览会
- 长城是由谁建造的
- 【环球报资讯】创业板指数基金有哪些
- 跨国公司有哪些
- 今日热讯:工银价值是什么基金
- 保障额度是什么意思,保险金额
- 环球关注:被车撞了怎么跟保险公司沟通赔偿,有以下四步
- 当前资讯!社保买两年不买可退回钱吗,满足条件可以退
- 环球短讯!新能源汽车自燃保险公司赔付吗,购买了自燃险会赔付
- 私企有公积金吗,有
- 【环球时快讯】直击现场!沃太能源亮相北京ESIE展,"新一代"能源技术备受瞩目!
- 环球新消息丨a股和美股哪个适合散户
- 每日短讯:深化储能业务布局 首航携光储系统解决方案亮相ESIE2023
- 【独家】杠杆效应是什么
- 注册制有什么特点
- 风投基金是什么意思
- “数”说数字政府建设“山东样本”
- 今日热议:ipo啥意思
- 创业板和科创板的区别
- 震荡股票怎么操作
- 环球播报:龙腾光电荣膺电博会金奖,卓越技术引领行业
- 前沿热点:股市大跌的原因
- 天天快消息!权重股是指哪些股票
- 权重股什么意思
- 观点:交通运输部部署开展2023年中国航海日活动
- 世界滚动:“豫”见恐龙骨架化石数字作品限量发行
- 腾讯视频与抖音达成合作,推动长短视频融合发展
- 每日信息:3600亿巨头出手!联手两大新能源公司,要干这件大事
- 【全球速看料】这群HUSTer,在山沟沟里种出“金坨坨”!
- 焦点短讯!买瓶洗发水送女票
- 国潮吸引创业者
- 每日报道:李国庆羡慕周鸿祎平和离婚背后,与俞渝离婚大战鸡飞狗跳
- 阳光车险为啥便宜,阳光车险的理赔流程有哪些
- 配置占比大幅提升 机构频频现身科创板股
- 环球微资讯!股票行情快报:天元股份(003003)4月7日主力资金净买入55.04万元
- 中交地产2022年收入385亿?较上年增长164.52%
- 天天快报!LG化学金惠子:中国医美市场潜力巨大,高端市场尤需持续发力
- 天天报道:中交地产2022年净利润0.34亿元丨年报快讯
- 快讯:苏宁环球披露前期会计差错更正 涉及2021年度末未分配利润数据
- 天天观热点:新能源车险保费大增背后:赔付率超油车,行业如何提升利润?
- 天天新消息丨专访陆家嘴董事长徐而进:集团优质资产注入 三年内预计预收款项近400亿元
- 每日热讯!3月上海二手房成交套数达20个月新高:挂牌量充足,价格稳定
- 环球观察:专访:对中国经济长期向好充满信心——访美敦力全球高级副总裁顾宇韶
- 每日关注!招商蛇口一季度签约销售金额722.66亿元 同比增长超五成
- 当前快讯:严跃进:新力退市、蓝光预警,防范房企债务危机演变为股市危机
- 机构评3月非农:美国就业增长虽降温,但美联储5月加息不可避免?
- 云海金属:青阳项目按计划是今年投产
- 世界要闻:湖北能源:公司信息披露严格按照监管部门相关要求办理,无应披未披事项
- 全球百事通!运动品牌“双雄”安踏、李宁“失速”,成长性陷入瓶颈,高端化困难重重
- 国内游热度走高,全国多地知名景区官宣免票
- 城投控股一季度主要房地产项目新增签约金额4570万元
- 金融街预计2023年与控股股东关联交易不超3.1亿
- 当前短讯!郑州楼市再放大招!公积金最高可贷100万
- 天天百事通!天健集团按比例支付深圳坪山土地价款?代价4.84亿元