「数据结构详解·十五」树状数组

  • 「数据结构详解·一」树的初步
  • 「数据结构详解·二」二叉树的初步
  • 「数据结构详解·三」栈
  • 「数据结构详解·四」队列
  • 「数据结构详解·五」链表
  • 「数据结构详解·六」哈希表
  • 「数据结构详解·七」并查集的初步
  • 「数据结构详解·八」带权并查集 & 扩展域并查集
  • 「数据结构详解·九」图的初步
  • 「数据结构详解·十」双端队列 & 单调队列的初步
  • 「数据结构详解·十一」单调栈
  • 「数据结构详解·十二」有向无环图 & 拓扑排序
  • 「数据结构详解·十三」优先队列 & 二叉堆的初步
  • 「数据结构详解·十四」对顶堆
  • 「数据结构详解·十五」树状数组

0. 前置知识:lowbit 运算

我们定义 lowbit ( x ) \text{lowbit}(x) lowbit(x) x x x 在二进制下最低的 1 1 1 所代表的数。
lowbit ( 101 0 2 ) = 1 0 2 = 2 10 , lowbit ( 1110 1 2 ) = 1 2 = 1 10 \text{lowbit}(1010_2)=10_2=2_{10},\text{lowbit}(11101_2)=1_2=1_{10} lowbit(10102)=102=210,lowbit(111012)=12=110

我们要如何计算这个东西呢?
一种通常的计算方法是 lowbit ( x ) = x & ( ( ∼ x ) + 1 ) = x & − x \text{lowbit}(x)=x\&((\sim x)+1)=x\&-x lowbit(x)=x&((x)+1)=x&x,手模一下可以得到正确性。

现在你学会了计算 lowbit,下面就可以学习树状数组了!

1. 树状数组的概念

树状数组(Binary Indexed Tree, BIT, Fenwick Tree),也称作二叉索引树,是一种维护序列信息的数据结构。所维护的序列信息和运算需要满足一定的要求:

  • 可差分性:即如果知道了 a ∘ b a\circ b ab a a a,可以推得 b b b
  • 结合律:即维护的信息所做的运算 ∘ \circ 满足 ( a ∘ b ) ∘ c = a ∘ ( b ∘ c ) (a\circ b)\circ c=a\circ(b\circ c) (ab)c=a(bc)

在树状数组中,记 bit i \text{bit}_i biti区间 [ i- lowbit( i )+1, i ] \textbf{[\textit{i-}lowbit(\textit i)+1,\textit i]} [i-lowbit(i)+1,i] 的信息和
那么,对于一个序列 a a a 的前缀信息,都被划分成了 log \textbf{log} log
如图所示,底部的点是 a i a_i ai,上方的点是 bit i \text{bit}_i biti

下面以例题具体解释树状数组的实现。

2. 例题详解

2-1. Luogu P3374 【模板】树状数组 1 / Loj 130 树状数组 1 :单点修改,区间查询

思考一下我们修改位置 x x x 的数会影响的到的 bit i \text{bit}_i biti
结合上图的观察,可以发现,如果我们从下往上修改,当修改的是 x x x,则下一次修改的就是 x + lowbit ( x ) x+\text{lowbit}(x) x+lowbit(x)(具体证明留给读者思考)。

而查询 ∑ i = l r a i \sum\limits_{i=l}^ra_i i=lrai 可以拆成 ∑ i = 1 r a i − ∑ i = 1 l − 1 a i \sum\limits_{i=1}^ra_i-\sum\limits_{i=1}^{l-1}a_i i=1raii=1l1ai
显然查询前缀和我们只要不断减去当前的 lowbit \text{lowbit} lowbit 即可。

修改和查询的时间复杂度都是 O ( n log ⁡ n ) O(n\log n) O(nlogn)
具体实现:

#include<bits/stdc++.h>
using namespace std;struct fwk{int n,bit[500005];void init(int i){n=i;memset(bit,0,sizeof(bit));}void add(int i,int c){for(;i<=n;i+=i&-i) bit[i]+=c;}int qry(int i){int res=0;for(;i;i-=i&-i) res+=bit[i];return res;}
}bit;int main()
{//freopen(".in","r",stdin);//freopen(".out","w",stdout);int n,m;cin>>n>>m;bit.init(n);for(int i=1;i<=n;i++){int x;cin>>x;bit.add(i,x);}while(m--){int op,x,y;cin>>op>>x>>y;if(op==1) bit.add(x,y);else cout<<bit.qry(y)-bit.qry(x-1)<<endl;}return 0;
}

2-2. Luogu P3368 【模板】树状数组 2 / Loj 131 树状数组 2 :区间修改,单点查询

我们 BIT 只能单点修改啊?怎么办!
其实,只要将序列 a a a 差分成为 b b b 后( b i = a i − a i − 1 b_i=a_i-a_{i-1} bi=aiai1),就变成了单点修改 b l ← b l + x , b r + 1 ← b r + 1 − x b_{l}\gets b_l+x,b_{r+1}\gets b_{r+1}-x blbl+x,br+1br+1x,区间查询 ∑ i = 1 x b i \sum\limits_{i=1}^xb_i i=1xbi 了。
代码和上一题几乎是一样的,所以不再展示了。

2-3. Luogu P3372 【模板】线段树 1 / Loj 132 树状数组 3 :区间修改,区间查询

这就不是很好做了。
首先区间查询就是 ∑ i = 1 r a i − ∑ i = 1 l − 1 a i \sum\limits_{i=1}^ra_i-\sum\limits_{i=1}^{l-1}a_i i=1raii=1l1ai,也就是说我们只要考虑如何求一个前缀和 ∑ i = 1 x a i \sum\limits_{i=1}^xa_i i=1xai
同上一题一样,将 a a a 差分得到 b b b,有这样的推导:
∑ i = 1 x a i = ∑ i = 1 x ∑ j = 1 i b j = b 1 + b 1 + b 2 + b 1 + b 2 + b 3 + ⋯ + b 1 + b 2 + b 3 + ⋯ + b x = ∑ i = 1 x ( x − i + 1 ) b i = ( x + 1 ) ∑ i = 1 x b i − ∑ i = 1 x i ⋅ b i \begin{aligned} &\sum\limits_{i=1}^xa_i\\ =&\sum\limits_{i=1}^x\sum\limits_{j=1}^ib_j\\ =&b_1+\\ &b_1+b_2+\\ &b_1+b_2+b_3+\\ &\cdots+\\ &b_1+b_2+b_3+\cdots+b_x\\ =&\sum\limits_{i=1}^x(x-i+1)b_i\\ =&(x+1)\sum\limits_{i=1}^xb_i-\sum\limits_{i=1}^xi\cdot b_i \end{aligned} ====i=1xaii=1xj=1ibjb1+b1+b2+b1+b2+b3++b1+b2+b3++bxi=1x(xi+1)bi(x+1)i=1xbii=1xibi
发现前后两个和式都是可以用 BIT 维护的!
于是就做完了。代码留给读者实现。

3. 值域树状数组

也称权值树状数组,就是将值的出现情况展现在 BIT 上,类似于哈希表。

以 Luogu P1908 逆序对 为例。
题目要求 i < j i<j i<j a i > a j a_i>a_j ai>aj 的二元组 ( i , j ) (i,j) (i,j) 个数。
考虑一个显然的事情:开一个桶,存放每种数的出现次数 c i c_i ci。那么当加入 a j a_j aj 时,能与 j j j 配对形成 ( i , j ) (i,j) (i,j) i i i 的个数就是 ∑ k = 1 i − 1 c k \sum\limits_{k=1}^{i-1}c_k k=1i1ck
而这个东西恰恰是可以使用 BIT 维护的!
代码也很简单,留给读者实现。

4. 二维树状数组

也称 BIT 套 BIT,也就是把 BIT 放到平面上。

以 Loj 133 二维树状数组 1:单点修改,区间查询 为例。
单点修改是同理的,只要在循环外再套一层就可以。

void add(int x,int y,int d)
{for(int i=x;i<=n;i+=i&-i){for(int j=y;j<=m;j+=j&-j){bit[i][j]+=d;}}
}

区间查询同理。但是注意查询的是 ∑ i = 1 x ∑ j = 1 y a i , j \sum\limits_{i=1}^x\sum\limits_{j=1}^ya_{i,j} i=1xj=1yai,j 的信息,即二维前缀和,减一减即可。

int qry(int x,int y)
{int res=0;for(int i=x;i;i-=i&-i){for(int j=y;j;j-=j&-j){res+=bit[i][j];}}return res;
}
int qry(int a,int b,int c,int d){return qry(c,d)-qry(c,b-1)-qry(a-1,d)+qry(c-1,d-1);}

而 Loj 134 二维树状数组 2:区间修改,单点查询 做二维差分即可。

但是,Luogu P4514 上帝造题的七分钟 / Loj 135 二维树状数组 3:区间修改,区间查询 就不是这样的了。

和一维的同理,令 b i , j = a i , j − a i − 1 , j − a i , j − 1 + a i − 1 , j − 1 b_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1} bi,j=ai,jai1,jai,j1+ai1,j1 后推一个式子:
∑ i = 1 x ∑ j = 1 y a i , j = ∑ i = 1 x ∑ j = 1 y ∑ p = 1 i ∑ q = 1 j b p , q = ∑ i = 1 x ∑ j = 1 y ( x − i + 1 ) ( y − j + 1 ) b i , j = ∑ i = 1 x ∑ j = 1 y ( ( x + 1 ) ( y + 1 ) − ( x + 1 ) j − ( y + 1 ) i + i ⋅ j ) b i , j = ( x + 1 ) ( y + 1 ) ∑ i = 1 x ∑ j = 1 y b i , j − ( x + 1 ) ∑ i = 1 x ∑ j = 1 y j ⋅ b i , j − ( y + 1 ) ∑ i = 1 x ∑ j = 1 y i ⋅ b i , j + ∑ i = 1 x ∑ j = 1 y i ⋅ j ⋅ b i , j \def\s{\sum\limits} \begin{aligned} &\s_{i=1}^x\s_{j=1}^ya_{i,j}\\ =&\s_{i=1}^x\s_{j=1}^y\s_{p=1}^i\s_{q=1}^jb_{p,q}\\ =&\s_{i=1}^x\s_{j=1}^y(x-i+1)(y-j+1)b_{i,j}\\ =&\s_{i=1}^x\s_{j=1}^y((x+1)(y+1)-(x+1)j-(y+1)i+i\cdot j)b_{i,j}\\ =&(x+1)(y+1)\s_{i=1}^x\s_{j=1}^yb_{i,j}-(x+1)\s_{i=1}^x\s_{j=1}^yj\cdot b_{i,j}-(y+1)\s_{i=1}^x\s_{j=1}^yi\cdot b_{i,j}+\s_{i=1}^x\s_{j=1}^yi\cdot j\cdot b_{i,j} \end{aligned} ====i=1xj=1yai,ji=1xj=1yp=1iq=1jbp,qi=1xj=1y(xi+1)(yj+1)bi,ji=1xj=1y((x+1)(y+1)(x+1)j(y+1)i+ij)bi,j(x+1)(y+1)i=1xj=1ybi,j(x+1)i=1xj=1yjbi,j(y+1)i=1xj=1yibi,j+i=1xj=1yijbi,j
于是开 4 4 4 个 BIT 分别维护 b i , j , i ⋅ b i , j , j ⋅ b i , j , i ⋅ j ⋅ b i , j b_{i,j},i\cdot b_{i,j},j\cdot b_{i,j},i\cdot j\cdot b_{i,j} bi,j,ibi,j,jbi,j,ijbi,j 即可。

5.巩固练习

事实上,BIT 还有很多应用,如维护不可差分的信息等。但这些通常是用其他数据结构平替的,故不在此继续做阐述。感兴趣的读者可以自行了解。

  • 上述未给出代码的例题
  • Luogu P2068 统计和
  • Luogu P2357 守墓人
  • Luogu P1774 最接近神的人
  • Luogu P1637 三元上升子序列

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

复合机器人为生产提供精准的建议和决策支持

在现代化生产的浪潮中&#xff0c;智能复合机器人以其卓越的性能和高度智能化特点&#xff0c;正成为保障生产安全与可靠性的重要力量。 智能复合机器人具备精确的感知、判断和决策能力&#xff0c;能够在复杂的生产环境中自主导航、精确操作&#xff0c;避免了人为因素可能导致…

实现按键按下(低电平)检测到下降沿

按照流程进行编程 步骤1&#xff1a; 初始化函数 包括时基工作参数配置 输入通道配置 更新中断使能 使能捕获、捕获中断及计数器 HAL_TIM_IC_Init(&ic_handle) //时基参数配置 HAL_TIM_IC_ConfigChannel(&ic_handle,&ic_config,TIM_CHANNEL_2) //输…

软件开发中的三层结构

一、三层结构概述 在软件开发中&#xff0c;三层结构&#xff08;Three - Tier Architecture&#xff09;是一种常见的软件架构模式。它将软件系统分为三个主要的层次&#xff0c;即表示层&#xff08;Presentation Layer&#xff09;、业务逻辑层&#xff08;Business Logic L…

【MQ】大白话告诉你什么是MQ,没有比这还详细还易懂的文章了吧,以RabbitMQ为例,从小白到大神

目录 分布式系统通信方式 MQ选型与应用场景 应用场景&#xff08;优势&#xff09; RabbitMQ工作模型 RabbitMQ简介 RabbitMQ 工作模型&#xff08;流程&#xff09;​编辑 Docker安装配置RabbitMQ RabbitMQ管理控制台 RabbitMQ 简单模式构建生产者 RabbitMQ 简单模式…

RTMP推流平台EasyDSS在无人机推流直播安防监控中的创新应用

无人机与低空经济的关系密切&#xff0c;并且正在快速发展。2024年中国低空经济行业市场规模达到5800亿元&#xff0c;其中低空制造产业占整个低空经济产业的88%。预计未来五年复合增速将达到16.03%。 随着科技的飞速发展&#xff0c;公共安防关乎每一个市民的生命财产安全。在…

PCIE概述

PCIE概述 文章目录 PCIE概述前言一、应用场景二、PCIE理论2.1 硬件2.2 拓扑结构&#xff1a;处理器和设备之间的关系2.3 速率2.4 层次接口2.5 四种请求类型2.5.1 bar空间2.5.2 memory2.5.3 IO2.5.4 configuration2.5.5 message 前言 参考链接&#xff1a; pcie总线知识点解析 …

SpringBoot SPI

参考 https://blog.csdn.net/Peelarmy/article/details/106872570 https://javaguide.cn/java/basis/spi.html#%E4%BD%95%E8%B0%93-spi SPI SPI(service provider interface)是JDK提供的服务发现机制。以JDBC为例&#xff0c;JDK提供JDBC接口&#xff0c;在包java.sql.*。MY…

超详细!Jmeter性能测试

前言 性能测试是一个全栈工程师/架构师必会的技能之一&#xff0c;只有学会性能测试&#xff0c;才能根据得到的测试报告进行分析&#xff0c;找到系统性能的瓶颈所在&#xff0c;而这也是优化架构设计中重要的依据。 测试流程&#xff1a; 需求分析→环境搭建→测试计划→脚…

快速本地化部署 OnlyOffice服务 ( Linux+Docker)

文章目录 一、OnlyOffice介绍&#x1f4d6;二、集成OnlyOffice&#x1f9e9;2.1 环境准备&#x1f5a5;️2.2 搜索镜像2.3 拉取镜像2.4 查看镜像2.5 创建容器2.6 进入容器配置2.7 重启服务2.8 添加字体字号2.9 测试OnlyOffice服务 三、在线预览office文档四、Cpolar内网穿透 一…

加密--03--MD5-- JAVA运用(hutool工具包)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 hutool1.简介2.pom.xml3.Hutool-crypto概述4.MD5 加密 案例11.hutool依赖2.用户表3.加密方法4.业务代码 hutool https://www.hutool.cn/docs/#/ 1.简介 2.pom.xml …

CSS 实现带tooltip的slider

现代 CSS 强大的令人难以置信 这次我们来用 CSS 实现一个全功能的滑动输入器&#xff0c;也就是各大组件库都有的slider&#xff0c;效果如下 还可以改变一下样式&#xff0c;像这样 特别是在拖动时&#xff0c;tooltip还能跟随拖动的方向和速度呈现不同的倾斜角度&#xff0c…

关于SAP Router连接不稳定的改良

这个也是网上看来的&#xff0c;之前在用的时候也在想是不是建立一个长连接&#xff0c;就不至于断线。今天正好看到。 关于SAP Router连接不稳定的改良 我们在使用SAPRouter时经常会碰到断线&#xff0c;其发生原因有很多&#xff0c;如&#xff1a;网络不稳定、操作间隔时间…

docker 搭建自动唤醒UpSnap工具

1、拉取阿里UpSnap镜像 docker pull crpi-k5k93ldwfc7o75ip.cn-hangzhou.personal.cr.aliyuncs.com/upsnap/upsnap:4 2、创建docker-compose.yml文件&#xff0c;进行配置&#xff1a; version: "3" services:upsnap:container_name: upsnapimage: crpi-k5k93ldwf…

Python课设-谁为影狂-豆瓣数据【数据获取与预处理课设】

&#x1f3c6; 作者简介&#xff1a;席万里 ⚡ 个人网站&#xff1a;https://dahua.bloggo.chat/ ✍️ 一名后端开发小趴菜&#xff0c;同时略懂Vue与React前端技术&#xff0c;也了解一点微信小程序开发。 &#x1f37b; 对计算机充满兴趣&#xff0c;愿意并且希望学习更多的技…

STM32 进阶SPI案例1:软件模拟SPI读写FLASH

需求描述 基于寄存器操作&#xff0c;使用软件模拟SPI协议&#xff0c;完成读写FLASH。 硬件电路设计 寄存器代码书写 main.c #include "usart1.h" #include "string.h" #include <stdio.h> #include "m24c02.h" #include "soft_…

Qt WORD/PDF(一)使用 QtPdfium库实现 PDF 预览

文章目录 一、简介二、下载 QtPdfium三、加载 QtPdfium 动态库四、Demo 使用 关于QT Widget 其它文章请点击这里: QT Widget 姊妹篇: Qt WORD/PDF&#xff08;一&#xff09;使用 QtPdfium库实现 PDF 操作 Qt WORD/PDF&#xff08;二&#xff09;使用 QtPdfium库实现…

【SpringCloud】OpenFeign配置时间Decode

文章目录 1.自定义反序列化器2.配置类与自定义 ObjectMapper客户端 需求&#xff1a;OpenFeign配置自定义decode&#xff0c;解析http请求返回的时间字符串 1.自定义反序列化器 Date 自定义反序列化器 import com.fasterxml.jackson.core.JsonParser; import com.fasterxml.j…

java程序设计2(二)

自动装箱和自动拆箱&#xff1a;基本数据类型和包装类型之间可以直接相互转换的包装类通常可以区分有效数据和无效数据&#xff0c;例如&#xff1a;0和nullString类 获取字符串的方式 【企业面试】 String str1 "hello"; 这种获取字符串的方式&#xff0c;在串池…

百度地图JavaScript API核心功能指引

百度地图JavaScript API是一套由JavaScript语言编写的应用程序接口&#xff0c;它能够帮助您在网站中构建功能丰富、交互性强的地图应用&#xff0c;包含了构建地图基本功能的各种接口&#xff0c;提供了诸如本地搜索、路线规划等数据服务。百度地图JavaScript API支持HTTP和HT…

让 Win10 上网本 Debug 模式 QUDPSocket 信号槽 收发不丢包的方法总结

在前两篇文章里&#xff0c;我们探讨了不少UDP丢包的解决方案。经过几年的摸索测试&#xff0c;其实方法非常简单, 无需修改代码。 1. Windows 下设置UDP缓存 这个方法可以一劳永逸解决UDP的收发丢包问题&#xff0c;只要添加注册表项目并重启即可。即使用Qt的信号与槽&#…