当前位置：首页 > news >正文

【算法进阶详解第一节】树状数组

news 来源：原创 2025/9/22 0:46:41

【算法进阶详解第一节】树状数组

前言
树状数组基础
- 树状数组原理
- 树状数组能够解决的问题
树状数组提高
- 树状数组区间加，区间和操作
- 二维树状数组
树状数组应用
- 树状数组区间数颜色
- 树状数组二维偏序

前言

树状数组在算法竞赛中十分常见，其能解决二维数点，区间数颜色等问题，还具有较小的常数，是一个十分优秀的数据结构。如果文章有问题欢迎在评论区指出。

树状数组基础

树状数组原理

我们用前缀和问题引入树状数组。
给定一个长为 $n$ 数组，之后有 $q$ 次操作，操作分修改和查询两种，修改数组中一个位置，查询前缀和。
如果维护整个数组，每一次修改是 $O (1)$ 的，但是查询要便利整个前缀，复杂度 $O (n)$ ， $1 s$ 难以通过；如果维护前缀和，每一次查询是 $O (1)$ 的，但是修改会影响到包含它的前缀的值，复杂度 $O (n)$ ， $1 s$ 内仍旧难以通过；而树状数组可以在 $O(\log(n))$ 的时间内解决修改和查询两种做法，复杂度十分优秀，相当于平均了修改和查询的复杂度。

	维护数组	维护前缀和	维护树状数组
修改	$O (1)$	$O (n)$	$O(\log(n))$
查询	$O (n)$	$O (1)$	$O(\log(n))$

树状数组中每一个元素 $c_i$ 存储的是 $i - l o w bi t (i) + 1$ ~ $i$ 的权值和，其中 $l o w bi t (x)$ 表示 $x$ 从低位开始的第一个 $1$ 的权值（即 $2^{最低位算 0 位时的位数}$ ），形象表示如下图（来自网上一张图片）：

在这里插入图片描述

其中树状数组中每个元素的值就是其所属区间覆盖的原数组的元素和。

对于修改第 $i$ 位操作，修改任意一个位置上的值，变化的是包含其的所有区间，通过找规律可以发现就是 $i$ 从查询位置编号开始，每次加上 $l o w bi t (i)$ 。
对于查询前 $i$ 位操作，查询那些区间能覆盖查询操作，通过找规律可以发现就是 $i$ 从查询位置编号开始，每次减去 $l o w bi t (i)$ 。

树状数组的核心代码如下：

int lowbit(int x)
{return x & -x;
}void add(int x, int c)
{for (int i = x; i <= n; i += lowbit(i)) tr[i] += c; // n 为数组长度，tr为树状数组。
}int sum(int x)
{int res = 0;for (int i = x; i; i -= lowbit(i)) res += tr[i];return res;
}

树状数组能够解决的问题

树状数组可以解决区间和问题，查询两个前缀和相减即可；树状数组还可以进行单点与原来取 $min$ ，查询前缀最小值，但是由于两个前缀最小值不能得到区间最小值，所以树状数组这样做不能得到区间最小值。

树状数组提高

树状数组区间加，区间和操作

题目链接

要求实现两种操作：

将一个区间中所有数加上一个数。
查询一个区间中所有数的和。

这个题直接把区间修改暴力拆成单点修改显然会超时。我们可以将原序列 $a$ 变成差分序列 $b$ ，这样区间 $[l, r]$ 加上 $x$ 就变成了将差分序列的第 $l$ 项加上 $x$ ，将第 $r + 1$ 项减去 $x$ ，单点查询就变成了前缀查询。若此时把区间查询暴力拆成单点查询，仍旧难以通过。
我们把前缀和式子进行变换：
$\sum_{i = 1}^{x} a_i$
$=\sum_{i = 1}^{x} \sum_{j = 1}^{i} b_j$
$=\sum_{i = 1}^{x} (x - i + 1)b_i$
$1)\sum_{i = 1}^{x} b_i - \sum_{i = 1}^{x} ib_i$
于是我们维护两个树状数组，分别储存 $b_i$ 和 $ib_i$ 的前缀和，即可查询原序列的前缀和。两个前缀和相减就是题目中要求查询的区间和了。

二维树状数组

二维树状数组就是把一维树状数组扩展到二维中，能够进行单点修改和二维前缀和查询，具体做法就是把每个一维树状数组的元素再存一个新的一维树状数组。修改时枚举需要修改的树状数组，每个树状数组单独修改；查询时枚举需要查询的树状数组，每个树状数组单独查询即可。设查询和修改的二维平面大小为 $\times m$ ，则二维树状数组时间复杂度为 $O (l o g (n) l o g (m))$ 。

二维树状数组的核心代码如下：

int lowbit(int x)
{return x & -x;
}void add(int x, int y, int c)
{for (int i = x; i <= n; i += lowbit(i))for (int j = y; j <= m; j += lowbit(j))tr[i][j] += c;
}int sum(int x, int y)
{int res = 0;for (int i = x; i; i -= lowbit(i))for (int j = y; j; j -= lowbit(j))res += tr[i][j];return res;
}

树状数组应用

树状数组区间数颜色

原题链接

给定一个长度为 $n$ 的数组，每次查询一个区间 $[l, r]$ 中不同值的个数。

直接在线做比较困难，考虑离线，按右端点排序，从前往后按右端点扫描线。在树状数组中，我们在最后一次出现的颜色对应的下标存 $1$ ，否则存 $0$ ，扫描线时加入一个颜色时，如果之前没有出现过这个颜色就直接把当前位置加 $1$ ，否则把前面最后一次出现当前颜色的下标减 $1$ ，再把当前下标加上 $1$ ，查询时直接查询区间和即可。

树状数组二维偏序

树状数组可以解决二维偏序问题。

所谓的二维偏序，就是给定两个 $1$ ~ $n$ 的数组 $a$ 和 $b$ ，对于每个 $\le i \le n$ ，计算满足如下条件的 $\le j \le n)$ ：

$a_i \le a_j$
$b_i \le b_j$

具体解决方法，可以先把所有下标以 $a_i$ 为第一关建字， $b_i$ 为第二关键字排序，然后从前往后扫描每个下标，当扫描到 $a_i$ 时可能的 $j$ 只能出现在 $i$ 之前（满足第一个限制），且 $i$ 后面不会在有 $j$ （后面只有两种情况， $a_i > a_j$ 和 $a_i = a_j$ ，第一种肯定不满足，第二种因为第二关键字是 $b_i$ ，所以后面只可能 $b_i \ge b_j$ ， $b_i > b_j$ 肯定不行， $b_i = b_j$ 特判即可）。

然后由于 $i$ 之前 $a_i$ 的限制一定满足，所以只需处理 $i$ 之前的下标 $b_i$ 的限制即可。我们发现就是求 $\sum_{k = 1}^{b_i - 1} i 之前 = k 的数的个数$ 。我们把这个式子理解成前缀和，维护一个数组，每扫过一个数就把 $b_i$ 为下标的位置 $+ 1$ ，查询前缀和，可以用树状数组处理。时间复杂度 $O(n\log(n) + n\log(\max b_i))$ ，如果 $max b_i$ 太大，可以先把 $b_i$ 离散化再求解，复杂度 $O(n\log(n))$ 。

【算法进阶详解第一节】树状数组

【算法进阶详解第一节】树状数组前言树状数组基础树状数组原理树状数组能够解决的问题树状数组提高树状数组区间加，区间和操作二维树状数组树状数组应用树状数组区间数颜色树状数组二维偏序前言树状数组在算法竞赛中十分常见，其能解决二维数点&am…...

编程日记 2025/9/22 0:46:41

青少年编程与数学 02-009 Django 5 Web 编程 16课题、权限管理

青少年编程与数学 02-009 Django 5 Web 编程 16课题、权限管理一、授权授权的主要特点和作用授权的类型应用场景二、权限系统使用Django内置的权限系统使用组管理权限使用第三方库在视图中应用权限三、权限管理示例步骤 1: 创建Django项目和应用步骤 2: 定义模型和权限步骤 …...

编程日记 2025/9/22 0:45:39

第四十四篇--Tesla P40+Janus-Pro-7B部署与测试

环境系统：CentOS-7 CPU: 14C28T 显卡：Tesla P40 24G 驱动: 515 CUDA: 11.7 cuDNN: 8.9.2.26创建环境 conda create --name trans python3.10torch 2.6.0 transformers 4.48.3克隆项目 git clone https:/…...

编程日记 2025/9/22 0:44:12

低成本、高效率且成熟的电商实时数据采集方案：梦想成真？

在电子商务领域，数据是驱动业务决策的核心资源。实时数据采集对于电商企业而言，意味着能够即时洞察市场动态、消费者行为以及运营效果，从而快速调整策略，提升竞争力。然而，如何在保证数据质量的同时，实现低…...

编程日记 2025/9/19 8:26:42

微信小程序之mobx-miniprogram状态管理

目前已经学习了6种小程序页面、组件间的数据通信方案,分别是: 1. 数据绑定: properties 2.获取组件实例: this.selectComponent() 3.事件绑定: this.triggerEvent() 4. 获取应用实例：getApp() 5. 页面间通信: EventChannel 6.事件总线:pubsub-js 在中小型项目…...

编程日记 2025/9/22 0:45:39

uniapp可视化-活动报名表单系统-代码生成器

活动报名表单系统小程序旨在为各类活动组织者提供一个便捷、高效的线上报名管理平台，同时为参与者提供简单易用的报名途径。主要功能活动发布：活动组织者可以发布活动的详细信息，包括活动名称、时间、地点、活动内容等。用户可以在小程序中…...

编程日记 2025/9/18 0:39:09

1.从零开始学会Vue--{{基础指令}}

全新专栏带你快速掌握Vue2Vue3 1.插值表达式{{}} 插值表达式是一种Vue的模板语法我们可以用插值表达式渲染出Vue提供的数据 1.作用：利用表达式进行插值，渲染到页面中表达式：是可以被求值的代码，JS引擎会将其计算出一个结果 …...

编程日记 2025/9/15 17:20:48

深入解析操作系统控制台：阿里云Alibaba Cloud Linux（Alinux）的运维利器

作为一位个人开发者兼产品经理，我的工作日常紧密围绕着云资源的运维和管理。在这个过程中，操作系统扮演了至关重要的角色，而操作系统控制台则成为了我们进行系统管理的得力助手。本文将详细介绍阿里云的Alibaba Cloud Linux操作系统控制台的功…...

编程日记 2025/9/22 0:46:40

CSS Grid 网格布局，以及 Flexbox 弹性盒布局模型，它们的适用场景是什么？

CSS Grid网格布局和Flexbox弹性盒布局模型都是现代CSS布局的重要工具，它们各自具有独特的优势和适用场景。作为前端开发工程师，理解这些布局模型的差异和适用场景对于编写高效、可维护的代码至关重要。 CSS Grid网格布局适用场景： 复杂…...

编程日记 2025/9/20 22:23:02

2025.2.16机器学习笔记：TimeGan文献阅读

2025.2.9周报一、文献阅读题目信息摘要Abstract创新点网络架构一、嵌入函数二、恢复函数三、序列生成器四、序列判别器损失函数实验结论后续展望一、文献阅读题目信息题目： Time-series Generative Adversarial Networks会议： Neural Information…...

编程日记 2025/9/21 12:50:49

高通推出骁龙游戏超级分辨率™：充分释放移动游戏性能，带来更持久的续航

Snapdragon Elite Gaming 一直致力于为每位用户打造卓越游戏体验。骁龙支持众多端游级特性，包括144FPS游戏体验、True 10-bit HDR支持的最高视觉质量的超流畅图形，让玩家可以畅享超10亿色的游戏体验。骁龙将许多移动端首创特性引入备受玩家喜爱的游戏中&…...

编程日记 2025/9/21 14:49:27

golangAPI调用deepseek

目录 1.deepseek官方API调用文档1.访问格式2.curl组装 2.go代码1. config 配置2.模型相关3.错误处理4.deepseekAPI接口实现5. 调用使用 3.响应实例 1.deepseek官方API调用文档 1.访问格式现在我们来解析这个curl 2.curl组装 // 这是请求头要加的参数-H "Content-Type:…...

编程日记 2025/9/21 8:14:27

SOC芯片前端设计对芯片电源完整性的影响

在进行芯片的电源完整性时，因为PI受影响的因素较多，出现问题debug也比较难，所以在进行芯片设计时，需要端到端从前到后进行考虑设计，本篇文章将从芯片前端设计的角度来看看哪些因素会影响到PI的设计。芯片前端设计的主…...

编程日记 2025/9/20 23:19:21

【区块链】零知识证明基础概念详解

🌈个人主页: 鑫宝Code 🔥热门专栏: 闲话杂谈｜ 炫酷HTML | JavaScript基础 💫个人格言: "如无必要，勿增实体" 文章目录零知识证明基础概念详解引言1. 零知识证明的定义与特性1.1 基本定义1.2 三个核心…...

编程日记 2025/9/19 16:46:50

面基Spring Boot项目中实用注解一

在Spring Boot项目中，实用注解根据功能可以分为多个类别。以下是常见的注解分类、示例说明及对比分析： 1. 核心配置注解 SpringBootApplication 作用：标记主启动类，组合了Configuration、EnableAutoConfiguration和ComponentScan…...

编程日记 2025/9/19 5:35:56

最新智能优化算法：中华穿山甲优化（ Chinese Pangolin Optimizer ，CPO）算法求解23个经典函数测试集，MATLAB代码

中华穿山甲优化（ Chinese Pangolin Optimizer ，CPO）算法由GUO Zhiqing 等人提出，该算法的灵感来自中华穿山甲独特的狩猎行为，包括引诱和捕食行为。算法流程如下： 1. 开始设置算法参数和最大迭代次数&a…...

编程日记 2025/9/16 10:12:45

shell脚本备份MySQL数据库和库下表

目录注意： 一.脚本内容二.执行效果三.创建定时任务注意： 以下为对MySQL5.7.42版本数据库备份shell脚本参考运行备份的机器请确认mysqldump版本>5.7，否则备份参数--set-gtid-purgedOFF无效，考虑到一般数据库节点和备份…...

编程日记 2025/9/20 19:12:34

Unity Shader Graph 2D - Procedural程序化图形之渐变的正弦波形

前言正弦波形也是一种常用、常见的程序化图形，合理的使用正弦波形会创作出一些有趣、美观和丰富的效果，本文将使用Unity Shader Graph来实现一个正弦波形效果，帮助理解和实践Unity Shader Graph以及正弦函数。创建一个名为SineWave的Shader…...

编程日记 2025/9/18 17:26:57

【算法与数据结构】并查集详解+题目

目录一，什么是并查集二，并查集的结构三，并查集的代码实现 1，并查集的大致结构和初始化 2，find操作 3，Union操作 4，优化小结： 四，并查集的应用场景省份…...

编程日记 2025/9/19 3:35:52

国家队出手！DeepSeek上线国家超算互联网平台！

目前，国家超算互联网平台已推出 DeepSeek – R1 模型的 1.5B、7B、8B、14B 版本，后续还会在近期更新 32B、70B 等版本。 DeepSeek太火爆了！在这个春节档，直接成了全民热议的话题。 DeepSeek也毫无悬念地干到了全球增速最快的AI应用。这几天，国内的云计算厂家都在支持Dee…...

编程日记 2025/9/20 17:37:27

H5接入支付宝手机网站支付并实现

小程序文档 - 支付宝文档中心 1.登录支付宝开放平台创建网页/移动应用 2.填写创建应用信息 3.配置开发设置 4.网页/移动应用：需要手动上线。提交审核后，预计 1 个工作日的审核时间。详细步骤可点击查看上线应用。应用上线后，还需要完成…...

编程日记 2025/9/21 1:26:59

Win10环境借助DockerDesktop部署大数据时序数据库Apache Druid

Win10环境借助DockerDesktop部署最新版大数据时序数据库Apache Druid32.0.0 前言大数据分析中，有一种常见的场景，那就是时序数据，简言之，数据一旦产生绝对不会修改，随着时间流逝，每个时间点都会有个新的…...

编程日记 2025/9/18 9:17:10

（三）Axure制作转动的唱片

效果图属性： 图标库：iconfont-阿里巴巴矢量图标库方形图片转为圆角图片，裁剪，然后加圆角， 唱片和底图是两个图片，点击播放，唱片在旋转。主要是播放按钮和停止按钮，两个动态面板…...

编程日记 2025/9/18 0:40:40

[JVM篇]分代垃圾回收

分代垃圾回收分代收集法是目前大部分 JVM 所采用的方法，其核心思想是根据对象存活的不同生命周期将内存划分为不同的域，一般情况下将 GC 堆划分为老生代(Tenured/Old Generation)和新生代(Young Generation)。老生代的特点是每次垃圾回收时只有少量对象…...

编程日记 2025/9/21 7:29:51

SpringBoot多数据源实践：基于场景的构建、实现和事务一体化研究

1. 多数据源应用场景剖析 1.1 业务驱动的多数据源需求数据量与业务复杂度引发的分库分表：在现代企业级应用中，随着业务的不断拓展和用户量的持续增长，数据量呈爆炸式增长。例如，在大型电商平台中，用户数据、订单数据…...

编程日记 2025/9/21 20:14:25

鸿蒙应用开发者基础

目录判断题单选题多选题判断题 1、在http模块中，多个请求可以使用同一个httpRequest对象，httpRequest对象可以复用。（错误） 2、订阅dataReceiverProgress响应事件是用来接收HTTP流式响应数据。（错误&#xff0…...

编程日记 2025/9/16 9:47:59

Java面试第二山！《计算机网络》！

在 Java 面试里，计算机网络知识是高频考点，今天就来盘点那些最容易被问到的计算机网络面试题，帮你轻松应对面试，也方便和朋友们一起探讨学习。一、HTTP 和 HTTPS 的区别 1. 面试题呈现 HTTP 和 HTTPS 有什么区别？在…...

编程日记 2025/9/20 22:37:16

2025最新Java面试题大全（整理版）2000+ 面试题附答案详解

很多 Java 工程师的技术不错，但是一面试就头疼，10 次面试 9 次都是被刷，过的那次还是去了家不知名的小公司。问题就在于：面试有技巧，而你不会把自己的能力表达给面试官。应届生：你该如何准备简历&#…...

编程日记 2025/9/18 16:49:22

低空经济：开启未来空中生活的全新蓝海

引言随着科技的进步，我们不再仅仅依赖地面交通和传统物流。你是否曾幻想过，未来的某一天，快递、外卖可以像魔法一样直接从空中送到你手中？或者，你能乘坐小型飞行器，快速穿梭于城市之间，告别拥堵…...

编程日记 2025/9/21 11:24:52

【机器学习】线性回归与一元线性回归

【机器学习系列】 KNN算法 KNN算法原理简介及要点特征归一化的重要性及方式线性回归算法线性回归与一元线性回归线性回归模型的损失函数多元线性回归多项式线性回归线性回归与一元线性回归 V1.1线性回归问题线性方程的最优解一元线性回归一元线性回归的方程一元线性回归…...

编程日记 2025/9/21 2:28:14

MongoDB 7 分片副本集升级方案详解（上）

#作者：任少近文章目录前言：Mongodb版本升级升级步骤环境1.1环境准备1.2standalone升级1.3分片、副本集升级前言：Mongodb版本升级在开始升级之前，请参阅 MongoDB下个版本中的兼容性变更文档，以确保您的应用程序和…...

编程日记 2025/9/16 10:26:46

Fiori APP配置中的Semantic object 小bug

在配置自开发程序的Fiori Tile时，需要填入Semantic Object。正常来说，是需要通过事务代码/N/UI2/SEMOBJ来提前新建的。但是在S4 2022中，似乎存在一个bug，即无需新建也能输入自定义的Semantic Object。如下，当我们任…...

编程日记 2025/9/16 10:21:46

坑多多之AC8257 i2c1 rtc-pcf8563

pcf85163 ordering information Ordering information Package Description Version Marking code PCF85163T/1 SO8 ① SOT96-1 PF85163 PCF85163TS/1 TSSOP8 ② SOT505-1 85163 ①plastic small outline package; 8 leads;body width 3.9 mm ②plastic thin…...

编程日记 2025/9/16 10:27:44

制作一个项目用于研究elementUI的源码

需求：修改el-tooltip的颜色，发现传递参数等方法都不太好用，也可以使用打断点的方式，但也有点麻烦，因此打算直接修改源码，把组件逻辑给修改了第一步下载源码源码地址 GitHub - ElemeFE/element: A Vue.j…...

编程日记 2025/9/19 2:01:43

Docker高级篇

1.Mysql主从复制Docker版本 mysql主从复制原理 binlog 1.新建主服务器容器实例 docker run -d -p 3307:3306 --privilegedtrue \ -v /opt/mysql8.4.3/log:/var/log/mysql \ -v /opt/mysql8.4.3/conf:/etc/mysql/conf.d \ -v /opt/mysql8.4.3/data:/var/lib/mysql \ -e MYSQL…...

编程日记 2025/9/21 9:24:07

OSI 参考模型和 TCP/IP 参考模型

数据通信是很复杂的，很难在一个协议中完成所有功能。因此在制定协议时经常采用的思路是将复杂的数据通信功能由若干协议分别完成，然后将这些协议按照一定的方式组织起来。最典型的是采用分层的方式来组织协议，每一层都有一套清晰明确的功能和…...

编程日记 2025/9/16 10:30:16

rocketmq-netty通信设计-request和response

1、NettyRemotingServer启动分析 org.apache.rocketmq.remoting.netty.NettyRemotingServer#start public void start() {this.defaultEventExecutorGroup new DefaultEventExecutorGroup(nettyServerConfig.getServerWorkerThreads(),new ThreadFactory() {private AtomicI…...

编程日记 2025/9/20 19:21:12

【算法进阶详解 第一节】树状数组

前言

树状数组基础

树状数组原理

树状数组能够解决的问题

树状数组提高

树状数组区间加，区间和操作

二维树状数组

树状数组应用

树状数组区间数颜色

树状数组二维偏序

相关文章：

【算法进阶详解第一节】树状数组