最新要闻
- 今日快看!排队5小时、日营业额过万!春节前美甲生意火了
- 比新车还香!极氪推出官方二手车:三电终身质保
- 【独家焦点】或将对标《原神》!《王者荣耀·世界》即将发布新实机演示
- 每日短讯:吃完饭车没了 男子怀疑被偷报警:结果忘拉手刹车溜进沟
- 我国第二款国产ECMO获批上市!航天火箭技术转化:完全自主知识产权
- 微头条丨定了!2023高考全国统考时间公布:6月7日开考
- 世界看热讯:曾两次感染新冠!辉瑞CEO:正研发可保护一年的新冠疫苗
- 环球焦点!SpaceX星际飞船超级重型助推器本周测试:33部猛禽发动机同时点火
- 焦点热议:年轻人的第一台影像旗舰!卢伟冰:Redmi Note 12 Pro系列绝对可以
- 天天观速讯丨东北大哥8小时狂炫40斤砂糖橘 网友提醒:当心变黄
- 全球报道:《魔兽世界》国服即将停运!最后一周超7千帐号开挂被封
- 世界看热讯:近千亿国产半导体公司卓胜微净利润暴降超50%:大家确实不爱换手机!你换没
- 全球速读:呆萌!66只考拉七代同堂齐送新春祝福
- 不是安卓!鸿蒙系统成大学教材 “鸿蒙之父”王成录参与 培养开发者
- 焦点热议:美国科技史上最大规模裁员开启:亚马逊、微软“毕业”均超万人
- 全球快播:25年历史的笔记本内存将被淘汰 新标准单条可达128GB 频率更快
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
当前滚动:树状数组笔记整理
树状数组介绍
树状数组,顾名思义,就是树状的一维数组。
(相关资料图)
二叉树同样也可以用一维数组存储。我们以二叉树进行类比。
如图所示,图中节点的序号就是存在数组中的下标。
记父节点序号为 \(p\),子节点序号为 \(s\)。
则有:
\(p\) \(=\) \(s\) \(/\) \(2\) (向下取整)。
左子节点 \(s_{left}\) \(=\) \(p\) \(* 2\) 。
右子节点 \(s_{right}\) \(=\) \(p\) \(*2+1\) 。
综上可知,二叉树能用一维数组存,是由于其父子节点间存在一定关系,以至于不需要用额外的变量来表示信息。
那类比到树状数组中,可以发现:
\(c\)数组即为树状数组。\(c_i\) 表示区间\(a\)\([i-lowbit(i),i]\) 的和。
ps:点我了解lowbit运算是什么
同样记父节点下标为 \(p\) ,子节点下标为 \(s\)。
则有:
\(p\) \(=\) \(s\) \(+\) \(lowbit(s)\)。
由这条公式亦可反推出:
\(s\) \(=\) \(p\) \(-\) \(2^i\)(\(0 \le i < p_{last}\))
这里的 \(p_{last}\) 指的是 \(p\) 二进制表示下最后一位 \(1\) 所在的位数。
例如:\(6\) 的二进制数表示为 \(110\),则它的 \(p_{last}\) 为 \(1\)。(这里的位数从右往左从\(0\)开始记)。
因为公式 \(1\) 由 \(s\) 加上自身 \(lowbit(s)\) 得到 \(p\) 其过程一定会产生进位。且 \(lowbit(s)\) 一定小于 \(lowbit(p)\) ,所以可以倒推得到子节点。
由于以上关系,树状数组不仅可以用一维数组存。而且还衍生出了一系列用途。
树状数组功能
单点增加
Q:给序列中的一个数 \(a[x]\) 加上 \(y\) 。此时如何维护树状数组?
A:将所有包含 \(a[x]\) 的节点加上 \(y\) 即可,也就是 \(c[x]\) 和它所有的祖先节点。
ps:初始化时亦可运用此操作。
点击查看代码
void add(int x,int y){for (; x <= N;x += x&-x) c[x] += y;return ;}
动态维护前缀和
之所以说动态维护,因为用树状数组维护前缀和只需要 \(\log N\) 的时间复杂度。更为优秀。
Q:求 \(a\) 数组 \(a_i \sim a_x\) 的和。
A:将数 \(x\) 分成若干个区间。
区间共同特点:若区间结尾为 \(R\),则区间长度就等于 \(lowbit(R)\),即 \(R\) 二进制分解下最小的整数次幂。
举例:当 \(x\) = \(7\) 时
如图所示。
区间划分方式与树状数组相同。前面又提到“\(c\)数组即为树状数组。\(c_i\) 表示区间\(a\)\([i-lowbit(i),i]\) 的和。”
因此只需要将这几个区间所对应的 \(c_i\) 相加。即可得到前缀和。
点击查看代码
int ask(int x){int ans = 0;for (; x ; x -= x & -x) ans += c[x];return ans;}
例题【具体应用】
主要利用树状数组可以快速求前缀和的优势,以数据范围为下标,快速统计区间内的个数(或所需要的信息),适用于数据范围适中(一般为 \(0 \le x \le 10^6\))且需要多次求前缀和的题目。
【例题1】 三元上升子序列
【题目分析】
对于一个数 \(x\) ,计算其作为 \(j\) 时,位置在它前面比它小的数 \(x_{min}\)、位置在它后面比它大的数 \(x_{max}\),运用乘法原理的知识可知,将\(x_{min} \times x_{max}\),即可得到 \(x\) 作为 \(j\) 时的方案数 ,枚举所有 \(x\) ,即可得到总方案数。
【树状数组作用】
统计 \(x_{min}\) 和 \(x_{max}\) 时,即可将数 \(x\) 的范围作为树状数组的下标。
此时两种操作所代表的意思分别为:
\(add(x,1)\) 表示数值为 \(x\) 的数的个数 \(+1\)。
\(sum(y)\) 表示在已经扫描过的区间内,数值为从 \(1 \sim y\) 的所有数的个数。
顺序扫描序列,对于数 \(x\) ,统计两个信息。
\(r_{i,0}\) 表示位置在数 \(x\) 前面,且比它小的数。
\(r_{i,1}\) 表示位置在数 \(x\) 前面,且比它大的数。
位置在数 \(x\) 后面,且比数 \(x\) 大的数就等于:
\(所有数 - 所有位置在 x 前面比 x 小的数 - r{i,1}\)。
【code】
点击查看代码
#include#include#include#define ll long longusing namespace std;ll tree[100005],n,num;ll r[40005][2],a[100005];void add(ll x,ll y){for(;x<=100005;x+=(x&-x)) tree[x]+=y;}ll sum(ll x){ll ans=0;for(;x;x-=(x&-x)) ans+=tree[x];return ans;}int main(){scanf("%lld",&n);for(int i=1;i<=n;i++){ll x;scanf("%lld",&x);a[i]=x;num=max(num,x);add(x,1);r[i][0]=sum(x-1);r[i][1]=sum(num)-sum(x);}ll ans=0;for(int i=1;i<=n;i++)ans+=r[i][0]*(sum(num)-sum(a[i])-r[i][1]);cout<
【summary】
此题算是初步认识了以数值范围为下标的树状数组的用法。下一大点求逆序对的思想与此相同。
【例题2】 [USACO04OPEN] MooFest G 加强版
【题目分析】
将奶牛按照音量从小到大进行排序,保证当前奶牛的音量一定最大,然后分类讨论所有比当前奶牛音量小的奶牛与当前奶牛的距离(坐标比当前奶牛大的和坐标比当前奶牛小的)。两者相加,乘上当前奶牛音量,枚举每个奶牛,即可得到答案。
【树状数组作用】
定义两个树状数组,都是以距离的范围作为下标, \(c\) 数组用于统计对应距离的个数,\(t\) 数组用于表示对应距离 \(\times\) 对应 距离个数的总数,通过二者,即可快速计算距离差。
【code】
计算过程的解释已在代码中注释出来。
点击查看代码
#include#include#include#include#define ll long longusing namespace std;ll n,t[50005],c[50005];struct A{ll v,x;}a[50005];bool cmp(A xx,A yy){if(xx.v==yy.v) return xx.x
【summary】
这一题的重点给到题目中树状数组 \(t\)。主要收获为:以数值范围为下标的树状数组,能够处理的信息不仅限于个数。
【例题3】P1972 [SDOI2009] HH的项链
【题意分析】
本题核心:如何判断一个区间内的贝壳是否重复?
当右端点 \(r\) 固定时,不论 \(l\) 取何值,对于任意一组重复的贝壳,都可以只统计最右端的贝壳。
原因:设一组重复贝壳中最右端的贝壳所在的位置为 \(pos_r\),那么当 \(pos_r < l\) 时,其他贝壳也不可能算进统计中,当 $pos_r \ge l $时,无论其他贝壳是否被包括,对于区间的贡献都只有 \(1\),因此,只计算最右端的贝壳即可。
因此,只需要将所有询问区间按 \(r\) 从小到大排序,计算答案即可。
【树状数组作用】
以位置为下标,每遇到一个新的数 \(num(num \le r)\),判断它是否重复,如果重复,那么将上一个相同的数的贡献值 \(-1\),将当前数的贡献值 \(+1\)。
对于一段区间 \([l,r]\),答案为 \(sum(r)-sum(l-1)\)。
【code】
点击查看代码
#include#include#include#includeusing namespace std;int n,m,ask_r,prev,pos;int vis[1000005],a[1000005],t[1000005],ans[1000005];struct A{int l,r,num;}ask[1000005];bool cmp(A x,A y){return x.r
【\(summary\)】
此题不再以数据范围为下标,而是以位置为下标。对于树状数组的应用更加灵活。在想到以最右端的贝壳为有价值的贡献时,对应到树状数组的操作就可以是上一个重复的数的贡献值 \(-1\),当前数的贡献值 \(+1\)。然后用前缀和统计区间内的个数。算进一步的开阔思维。
求逆序对
本质上也是通过树状数组单点增加和区间求和的操作进行计算。作为一个专题单独列出来。
桶排+树状数组:
1.桶排部分:
对于一个序列 \(a\) , 我们建立一个 \(cnt\) 数组,\(cnt[x]\) 表示 \(x\) 在序列 \(a\) 中出现过的次数。当 \(a_i=val\) 时,\(cnt[val]++\)。
2.树状数组部分:
倒序扫描序列 \(a\),对于新加入的数 \(a_i\),查询 \(cnt[1~a_i-1]\) 的前缀和,并将返回的前缀和加入答案。前缀和部分就可以用树状数组来维护。
操作简单粗暴,但相当好用。
点击查看代码
for ( int i = n; i; i --) {ans += ask (a[i] - 1);add (a[i] , 1 );}
【例题】
接下来通过两道题进一步了解一下逆序对的考法。(不做一下真没想到还能这样考。)
【例题1】P2448 无尽的生命
【题意简述】
看到题目显而易见是求逆序对个数。
【思路分析】
看到数据范围 \(x_i,y_i \le 2^{31}-1\),\(k \le 10^5\)。数据值域大但是个数少,且与数据之间的大小关系有关,因此考虑离散化。
离散化简单介绍
离散化实际就是一种映射,当数据值域过大而个数有限时,可以尝试离散化。
具体过程以此题为例。假设给出这么一组数据
2123456789 123456987654321 123456
首先将所有出现过的数收集起来,存进 \(a\) 数组,并进行排序,然后再去重保存进 \(pos\) 数组当中。
接下来就可以建立映射关系。将数值大的数在 \(num\) 数组中用数值小的数代替,但各个数之间的大小关系不变,接下来交换操作先用二分答案在 \(pos\) 数组中检索,然后通过映射在 \(num\) 数组中进行交换。
最终被交换过的数之间的逆序对在 \(num\) 数组中求即可。
被交换的数与未被交换的数之间的逆序对
考虑每个被交换的数对答案的贡献。
设 \(x 对于 \(x\) 来说, \(x \sim y\) 之间所有未被交换的数都比 \(x\) 大,形成逆序对。 对于 \(y\) 来说,\(x \sim y\) 之间所有未被交换的数都比 \(y\) 小,形成逆序对。 逆序对个数都为\(x \sim y\) 之间所有未被交换的数。 温馨提示:以下主要为代码实现讲解,本质思想同上。 对于交换过后的 \(num\) 数组,\(num_i\) 表示的是位置 \(pos_i\) 上当前所在的数在 \(num\) 数组中对应的数。记数 \(x\) 为位置 \(pos_i\) 上当前所在的数。 \(pos_{num_i}\) 表示数 \(x\) 现在所在的位置。 \(pos_i\) 表示数 \(x\) 原来在的位置。 \(\left\vert pos_i-pos_{num_i}-1\right\vert\) 表示两个位置间所有的数。 \(\left\vert num_i-i-1\right\vert\) 表示两个位置间所有被交换过的数。 因此所有未被交换的数就为 \(\left\vert pos_i-pos_{num_i}-1\right\vert - \left\vert num_i-i-1\right\vert\)。 【code】 【summary】 重点在于与未交换的数之间的求解。题目中序列的长度可以长到一个数组都存不下,但却可以用公式求呢。 【题目描述】 该题的重点在于如何从题面描述转到求 \(逆序对\)。抓到重点: 交换 \(a\) 中相邻两个字符,求最少的交换次数。 \(a,b\) 中只含大写字母,且数据保证 \(a\) 可以变成 \(b\)。 对 \(b\) 串中的字符进行顺序编号(假设此时 \(b\) 中并没有重复的字母),并对应到 \(a\) 串中。 例如: 对 \(BCA\) 进行顺序编号,对应到 \(ABC\) 就是 \(312\)。 当序列 \(a\) 中存在数 \(a , b\),满足 $pos_a < pos_b $ , \(a > b\)。也就是形成逆序对。 而对于我们的目标,将 \(a\) 串变成 \(b\) 串,需满足任意数 \(a , b\),都有 \(pos_a < pos_b\) , \(a < b\)。 显然我们需要通过一定操作,令逆序对都消失,以达到目标。 由于题目中的交换为交换相邻的数,因此只要 \(a\) 与 \(b\) 不交换,它们之间的相对位置就不会变,也就不能达成目标。 综上所述,最少的交换次数就是逆序对的个数。 当字母重复时,我们要如何让编号对应到 \(a\) 呢? 显然逆序对个数越少越好,因此对于相同的字母,按出现的顺序进行顺序编号。代码中用单向链表实现。 【code】 【模板】树状数组2 相信经过上面的头脑风暴,再来看这题已经相当简单了。 此时主要运用到差分的思想,差分是前缀和的逆运算。 当要在区间 \([x,y]\) 加上 \(k\) 时,我们进行以下操作: \(add(x,k) , add(y+1,-k)\) 此时对于区间求前缀和对于 \(x \sim y\),它的前缀和都为 \(k\),而到 \(y+1\) ,又变成 \(0\)。此时的前缀和正好是区间增加的数,且不会对其它数产生影响。 因此,当查询第 \(x\) 个数时,只需要输出: \(a_x(第 x 个数原本的数值) + sum(x)(变化的值)\)。 即可。点击查看代码
#include
【例题2】P3531 [POI2012]LIT-Letters
3ABCBCA
点击查看代码
#include
区间增加,单点查询
思路剖析
code
点击查看代码
#include
当前滚动:树状数组笔记整理
今日快看!排队5小时、日营业额过万!春节前美甲生意火了
比新车还香!极氪推出官方二手车:三电终身质保
【独家焦点】或将对标《原神》!《王者荣耀·世界》即将发布新实机演示
环球微速讯:学习笔记——@RequestMapping注解位置、注解属性;@RequestMapping支持Ant风格的路径
每日短讯:吃完饭车没了 男子怀疑被偷报警:结果忘拉手刹车溜进沟
我国第二款国产ECMO获批上市!航天火箭技术转化:完全自主知识产权
微头条丨定了!2023高考全国统考时间公布:6月7日开考
世界看热讯:曾两次感染新冠!辉瑞CEO:正研发可保护一年的新冠疫苗
环球焦点!SpaceX星际飞船超级重型助推器本周测试:33部猛禽发动机同时点火
天天观速讯丨【网关开发】5.Openresty 自定义负载均衡与流量转发
观点:100w人在线的 弹幕 系统,是怎么架构的?
焦点热议:年轻人的第一台影像旗舰!卢伟冰:Redmi Note 12 Pro系列绝对可以
天天观速讯丨东北大哥8小时狂炫40斤砂糖橘 网友提醒:当心变黄
全球报道:《魔兽世界》国服即将停运!最后一周超7千帐号开挂被封
世界看热讯:近千亿国产半导体公司卓胜微净利润暴降超50%:大家确实不爱换手机!你换没
全球速读:呆萌!66只考拉七代同堂齐送新春祝福
全球播报:非对称加解密算法SM2
世界简讯:从合并石子学区间DP
环球快播:Golang的基本数据类型-基本使用
不是安卓!鸿蒙系统成大学教材 “鸿蒙之父”王成录参与 培养开发者
焦点热议:美国科技史上最大规模裁员开启:亚马逊、微软“毕业”均超万人
全球快播:25年历史的笔记本内存将被淘汰 新标准单条可达128GB 频率更快
环球最新:24年前经典重现!《轩辕剑叁:云和山的彼端》将推出Switch版本
世界微动态丨三亚已成全国最堵城市:国人扎堆去海南 能堵到你哭泣
焦点精选!零下30度 东北司机穿10斤棉裤冒雪下乡送年货:网友为劳动者正能量点赞
焦点播报:大年初一上映!《流浪地球2》要做中国科幻片天花板 特效拉满
学习笔记——SpringMVC简介;SpringMVC处理请求原理简图;SpringMVC搭建框架
全球今日报丨曾致苹果华人工程师身亡!FSD造假实锤:特斯拉技术大牛证实
短讯!强推Win11:微软即将停售Win10数字许可
观天下!Win系统下实现任意exe静态免杀
全球速看:iPhone 14 Pro Max屏幕抽风出现死亡横线:iOS 16.3终于修复了
当前资讯!质量堪忧 退换货激增!AMD旗舰显卡RX7900 XTX游戏实测近3.5GHz 你买吗?
当前视点!还有5天关服 魔兽世界怀旧服免费玩 网易高管:出问题就找暴雪
低配版《黑神话:悟空》即将发售!新实机预告公布
“搭桥”运工具 波士顿动力机器人展示新技能:网友却不认账
佛诞是哪个国家的节日?佛诞日是农历的哪一天?
如来佛拈花一笑是什么意思?如来佛拈花一笑的故事
五常指的是哪五常?五常是什么时候建立的?
卫生衣是什么东西?卫生衣是什么季节穿的?
学习笔记——Spring声明式事务管理属性(隔离级别、事务超时、事务只读、事务回滚);Spring5新特性、新注解&整合log4j2;Spring5整合Juni
AIRIOT答疑第6期|如何使用二次开发引擎?
村的由来是什么?中国省市县区等级划分
思科路由器怎么进入设置界面?思科路由器配置命令大全
宝岛眼镜是哪里的品牌?宝岛眼镜怎么样?
开心消消乐什么时候上线的?开心消消乐怎么求助好友过关?
电脑重装系统后没有声音是怎么回事?电脑重装系统后没有声音怎么办?
b站在线人数在哪里看?b站在线人数怎么关闭?
国产芯的iPhone 14 Pro!乐视手机S1 Pro现货发售:仅899元
【当前热闻】嚣张!飞度女应急车道超车未果打砸后车被刑拘 受害车主回应
观速讯丨专为游戏优化!AYANEO OS掌机操作系统官宣2023年上线
国产科幻巨制!《流浪地球2》终极预告发布:大年初一上映
焦点要闻:红灯藏在成片红灯笼里引司机吐槽:差点6分没了
【天天播资讯】店主卖自制香肠遭男子10倍索赔 被法院驳回:网友大赞判决
世界视点!55天徒步跨越1600公里!沙特一观众获国际足联最佳球迷奖提名
【世界新视野】坐等分钱!全球205位富豪呼吁征收财富税:现在就向我们征税
全球首款独显掌机!AYANEO官宣NEXT 2将搭载锐龙7000系处理器
东芝高管放言:SSD硬盘永远无法取代机械硬盘
全球新资讯:Array 数组
读编程与类型系统笔记11_高级类型及其他
游戏对PC性能需求走向失控:16G内存已成最低要求
【世界时快讯】8900元!TP-Link最新Wi-Fi7路由器BE900上架 网速达24Gbps
观焦点:售价曝光!RTX 4060 Ti一塌糊涂 NV各种秀刀法:你会买?
新资讯:中金公司10大预测错9个:称电动车高景气 结果宁德时代年度最惨
世界速看:穷疯了?13岁儿女起诉父亲还压岁钱1.68万 官方回应压岁钱是个人私有财产
天天快报!“丑”出圈!蓝兔子邮票身价暴增 溢价幅度接近300%
过年租车7天起 日租价上涨近7倍:还定不到现车
【世界独家】西藏林芝一隧道出口雪崩 8人遇难:失联者家属称丈夫计划回家过年
全球要闻:近8年最大规模!微软正式宣布将裁员1万人
百事通!《阿凡达2》全球票房破19.28亿美元:成全球影史第六
观速讯丨CSS3选择器总结(表格)
年味十足!苹果发布iPhone兔年限定壁纸:苹果Logo变兔头
热门:“三体 脱水”登顶热搜 于和伟游戏刚上线游戏就下线
焦点速讯:“巨型屎山”QQ终于要史诗级重写!但是腾讯被骂惨了
口碑爆棚!冒险游戏改编剧《最后生还者》豆瓣开分9.2分
全球热推荐:AMD被大大看好:抢走Intel 30%市场!
【天天新视野】SpringBoot Wiki项目部署记录
环球微速讯:学习笔记——Spring声明式事务管理;Spring中支持事务管理;使用声明式事务管理;Spring声明式事务管理属性
世界热门:C. Equal Frequencies
全球播报:雷军:小米13用了昂贵的高硅负极电池才把容量做到4500mAh
世界简讯:Qt项目-翻金币游戏
lambda表达式基础
java-数组相关的算法(尚硅谷)
Pytorch-geometric: Creating Message Passing Networks 构建消息传递网络教程
把魔兽停服当庆典营销 网易《逆水寒》被曝涉嫌抄袭暴雪IP
当前热讯:《黑神话:悟空》定档:想玩记得升级电脑
快播:2022年预制菜销量大涨!之前有专家还说“我从来不吃”
7层WAF的一些记录
天天新动态:Numpy基本使用方法
[数据结构]单向链表插入排序(C语言)
世界报道:高铁站大厅没插座 客服:为了消防安全
滚动:你遇到过没?货车安装超亮后射灯:夜晚跟车根本看不清
时讯:首发2亿像素HP2!三星Galaxy S23 Ultra万元机皇来了
观察:口碑爆棚!剧版《三体》市占率16.51%排行第一
当前要闻:BC4-牛牛学说话之-浮点数
【独家焦点】关于可迭代对象、迭代器对象、生成器对象
环球快消息!AcWing 1077. 皇宫看守
年终会员大促:B站/芒果TV/腾讯视频/优酷/百度网盘3.6折起
三电机真恐怖!特斯拉Model S Plaid瞬间撕裂马力机张力带
焦点热讯:内置LED屏见过没?Naspec推出高端HDMI 2.1数据线