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

进阶数据结构——树状数组

前言

看这篇文章前我建议你们先看这个视频还有这个视频,不然你们可能看不懂。
在这里插入图片描述

一、树状数组的核心思想与本质

核心思想:树状数组(Fenwick Tree)是一种用于高效处理前缀和查询和单点更新的数据结构。
本质:通过二进制索引和树形结构,将前缀和的计算复杂度从

O(n) 优化到 O(logn)。

二、树状数组的基本操作

  1. 初始化
    初始化一个大小为 n 的数组,所有元素初始值为 0。

  2. 单点更新
    更新某个位置的值,并维护树状数组的结构。

  3. 前缀和查询
    查询从第一个元素到某个位置的前缀和。

  4. 区间和查询
    查询某个区间的和。

三、树状数组的应用场景

动态前缀和查询:

实时查询数组的前缀和,支持单点更新。

示例:LeetCode 307. 区域和检索 - 数组可修改。

逆序对计数:

使用树状数组统计数组中逆序对的数量。

示例:LeetCode 493. 翻转对。

区间更新与单点查询:

通过差分数组和树状数组实现区间更新和单点查询。

示例:LeetCode 370. 区间加法。

二维树状数组:

处理二维数组的前缀和查询和单点更新。

示例:LeetCode 308. 二维区域和检索 - 可变。

四、树状数组的复杂度分析
时间复杂度
单点更新:
O(logn)。

前缀和查询:
O(logn)。

区间和查询:
O(logn)。

空间复杂度
存储树状数组:
O(n)。

五、树状数组的优化技巧

  1. 差分数组
    通过差分数组实现区间更新和单点查询。

  2. 离散化
    在数据范围较大时,使用离散化减少树状数组的大小。

  3. 多维扩展
    将树状数组扩展到二维或更高维度,处理多维数组的前缀和查询和单点更新。

六、常见误区与调试技巧

  1. 误区一:树状数组适用于所有区间查询问题
    澄清:树状数组适用于前缀和查询和单点更新,对于复杂的区间查询问题可能需要其他数据结构(如线段树)。

  2. 误区二:树状数组的初始化复杂度高
    澄清:树状数组的初始化复杂度为 O(nlogn),但可以通过线性初始化优化到 O(n)。

  3. 调试方法
    打印树状数组:在每次操作后输出树状数组的内容,检查是否正确。

可视化树结构:手动画出树状数组的结构,模拟操作过程。

七、代码模版

单点更新

例题 【模板】树状数组 1

#include<iostream>
#include<vector>
using namespace std;template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowbit(int x);
public:FenwickTree(int n):m_tree(n+1,0){}void update(int idx,T val);T query(int idx);T query(int l, int r);
};template<class T>
int FenwickTree<T>::lowbit(int x) {return x & (-x);
}template<class T>
void FenwickTree<T>::update(int idx, T val) {int n = (int)m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowbit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowbit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}int main() {int n, m;cin >> n >> m;FenwickTree<int> ft(n);for (int i = 1; i <= n; i++) {int x;cin >> x;ft.update(i, x);}while (m--) {int z, x, y;cin >> z >> x >> y;if (z == 1) {ft.update(x, y);}else {int sum = ft.query(x, y);cout << sum << endl;}}return 0;
}

区间更新

例题 【模板】树状数组

#include<iostream>
#include<vector>
using namespace std;template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowBit(int idx);void update(int idx, T val);T query(int idx);T query(int l, int r);
public:FenwickTree(int n):m_tree(n+2,0){}void updateInterval(int l, int r, T val);T queryIndex(int idx);
};template<class T>
int FenwickTree<T>::lowBit(int idx) {return idx & -idx;
}template<class T>
void FenwickTree<T>::update(int idx, T val) {int n = (int)m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowBit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowBit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}template<class T>
void FenwickTree<T>::updateInterval(int l, int r, T val) {update(l, val);update(r + 1, -val);
}template<class T>
T FenwickTree<T>::queryIndex(int idx) {return query(idx);
}int main() {int n, m;cin >> n >> m;FenwickTree<int>ft(n);for (int i = 1; i <= n; i++) {int a;cin >> a;ft.updateInterval(i, i, a);}while (m--) {int opt;cin >> opt;if (opt == 1) {int l, r, x;cin >> l >> r >> x;ft.updateInterval(l, r, x);}else {int k;cin >> k;cout << ft.queryIndex(k) << endl;}}return 0;
}

八、经典例题

排序

#include<iostream>
#include<vector>
using namespace std;template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowBit(int idx);
public:FenwickTree(int n):m_tree(n+1,0){}void update(int idx, T val);T query(int idx);T query(int l, int r);
};template<class T>
int FenwickTree<T>::lowBit(int idx) {return idx & -idx;
}template<class T>
void FenwickTree<T>::update(int idx, T val){int n = m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowBit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowBit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}#define maxn 1000001
int a[maxn];int main() {int n, m;cin >> n;FenwickTree<long long>ft(maxn);for (int i = 0; i < n; i++) {cin >> a[i];}long long sum = 0;for (int i = n - 1; i >= 0; i--) {		//逆序遍历数组看看后面有多少个比当前这个值小的个数,乘于它本身累加起来ft.update(a[i], 1);sum += (long long)ft.query(a[i] - 1) * a[i];	//求1~a[i]-1元素个数}cout << sum << endl;return 0;
}

逆序对的数量

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;template<class T>
class Dicretizer {
private:vector<T>m_data;
public:void addData(T v);void process();int get(T v) const;int size() const;
};template<class T>
void Dicretizer<T>::addData(T v) {m_data.push_back(v);
}template<class T>
void Dicretizer<T>::process() {sort(m_data.begin(), m_data.end());int lastId = 0;for (int i = 1; i < m_data.size(); i++) {T x = m_data[i];if (x != m_data[lastId]) {m_data[++lastId] = x;}}while (lastId < m_data.size() - 1) {m_data.pop_back();}
}template<class T>
int Dicretizer<T>::get(T v) const {int l = -1, r = m_data.size();while (l + 1 < r) {int mid = (l + r) / 2;if (m_data[mid] >= v)r = mid;else l = mid;}if (r == m_data.size() || m_data[r] != v)return -1;return r;
}template<class T>
int Dicretizer<T>::size() const {return m_data.size();
}template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowBit(int idx);
public:FenwickTree(int n):m_tree(n+1,0){}void update(int idx, T val);T query(int idx);T query(int l, int r);
};template<class T>
int FenwickTree<T>::lowBit(int idx) {return idx & -idx;
}template<class T>
void FenwickTree<T>::update(int idx, T val){int n = m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowBit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowBit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}#define maxn 1000001
int a[maxn];int main() {int n;cin >> n;Dicretizer<int>d;FenwickTree<int>ft(n);for (int i = 0; i < n; i++) {cin >> a[i];d.addData(a[i]);}d.process();	for (int i = 0; i < n; i++) {a[i] = d.get(a[i]) + 1;		//树状数组的序号是从1开始,利用离散化给原数组每个值标记它的序号,也就是排序好它们的大小}long long sum = 0;for (int i = n - 1; i >= 0; i--) {ft.update(a[i], 1);sum += ft.query(a[i] - 1);		//查询1~a[i]-1的元素和,他要找的是比它本身小的个数}cout << sum << endl;return 0;
}

三元组个数

这题就是遍历到的原数组的每一个元素用左边比它小的个数乘于右边比它大的个数,但是复杂度还是太高了,所以还得需要离散化数组,用树状数组记录比它小或大的个数

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;template<class T>
class Dicretizer {
private:vector<T>m_data;
public:void addData(T v);void process();int get(T v) const;int size() const;
};template<class T>
void Dicretizer<T>::addData(T v) {m_data.push_back(v);
}template<class T>
void Dicretizer<T>::process() {sort(m_data.begin(), m_data.end());int lastId = 0;for (int i = 1; i < m_data.size(); i++) {T x = m_data[i];if (x != m_data[lastId]) {m_data[++lastId] = x;}}while (lastId < m_data.size() - 1) {m_data.pop_back();}
}template<class T>
int Dicretizer<T>::get(T v) const {int l = -1, r = m_data.size();while (l + 1 < r) {int mid = (l + r) / 2;if (m_data[mid] >= v)r = mid;else l = mid;}if (r == m_data.size() || m_data[r] != v)return -1;return r;
}template<class T>
int Dicretizer<T>::size() const {return m_data.size();
}template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowBit(int idx);
public:FenwickTree(int n):m_tree(n+1,0){}void update(int idx, T val);T query(int idx);T query(int l, int r);
};template<class T>
int FenwickTree<T>::lowBit(int idx) {return idx & -idx;
}template<class T>
void FenwickTree<T>::update(int idx, T val){int n = m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowBit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowBit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}#define mod 998244353
#define maxn 1000001
int a[maxn], lt[maxn];	//lt[i]表示小于a[i]的个数int main() {int n;cin >> n;Dicretizer<int>d;FenwickTree<int>ft(n);for (int i = 0; i < n; i++) {cin >> a[i];d.addData(a[i]);}d.process();	for (int i = 0; i < n; i++) {a[i] = d.get(a[i]) + 1;		//树状数组的序号是从1开始,利用离散化给原数组每个值标记它的序号,也就是排序好它们的大小}for (int i = 0; i < n; i++) {ft.update(a[i], 1);lt[i] = ft.query(a[i] - 1);}ft = FenwickTree<int>(n);long long sum = 0;for (int i = n - 1; i >= 0; i--) {ft.update(a[i], 1);int gt = ft.query(a[i] + 1, n);		//求出比a[i]大的个数sum += (long long)lt[i] * gt % mod;sum %= mod;		//sum这个值可能超出范围所以还要取模}cout << sum << endl;return 0;
}

九、总结与学习建议

  1. 核心总结
    树状数组是一种高效处理前缀和查询和单点更新的数据结构。

通过二进制索引和树形结构,将复杂度优化到 O(logn)。

  1. 学习建议
    分类刷题:按问题类型集中练习(如动态前缀和、逆序对计数、区间更新)。

理解算法原理:掌握树状数组的实现步骤和优化技巧。

手写模拟过程:在纸上画出树状数组的结构,模拟操作过程,加深直观理解。

通过以上分析,树状数组作为一种高效的数据结构,在算法竞赛和实际应用中具有广泛用途。掌握其核心思想和实现技巧,能够有效提升算法效率。
在这里插入图片描述
希望大家可以一键三连,后续我们一起学习,谢谢大家!!!
在这里插入图片描述

相关文章:

进阶数据结构——树状数组

前言 看这篇文章前我建议你们先看这个视频还有这个视频&#xff0c;不然你们可能看不懂。 一、树状数组的核心思想与本质 核心思想&#xff1a;树状数组&#xff08;Fenwick Tree&#xff09;是一种用于高效处理前缀和查询和单点更新的数据结构。 本质&#xff1a;通过二进…...

键盘启用触摸板-tips

在日常使用笔记本电脑时&#xff0c;我们会遇到没带鼠标&#xff0c;触摸板关闭的情况&#xff0c;通常情况下&#xff0c;我们习惯通过鼠标点击或触摸屏操作来启用触摸板&#xff0c;但其实通过键盘也能轻松实现这一功能。以下就是一种通过键盘操作启用触摸板的方法&#xff0…...

信息安全之网络安全

网络安全技术是一类包含内容极其广泛的技术&#xff0c;广义上说任何检测、防御和抵制网络攻击的技术都属于网络安全技术&#xff0c;而且很多网络安全技术都是攻击驱动型的。 网络安全大致包含的内容主要有防火墙&#xff0c;入侵检测&#xff0c;漏洞扫描与网络隔离&#xf…...

成都国际数字影像产业园布局者树莓集团,亮相宜宾翠屏招商签约

在商业版图的不断拓展中&#xff0c;树莓集团始终以敏锐的市场洞察力和果敢的决策力占据先机。近期&#xff0c;作为成都国际数字影像产业园的布局者&#xff0c;树莓集团高调亮相宜宾翠屏招商签约盛会&#xff0c;引发行业内外的广泛关注。 宜宾翠屏招商签约盛会&#xff0c;…...

opencascade 获取edge起始点 会出现终点与实际不同的情况

在使用 OpenCASCADE 获取 TopoDS_Edge 的起始点和终点时&#xff0c;可能会出现终点与实际不一致的情况。这通常是由于以下原因导致的&#xff1a; 几何曲线的方向问题&#xff1a;在某些情况下&#xff0c;几何曲线的方向可能与拓扑边的方向不一致&#xff0c;导致通过几何曲线…...

掌握正则表达式_模式匹配的艺术

当然,以下是《掌握正则表达式:模式匹配的艺术》文章内容,使用 Java 正则表达式,并包含丰富的代码示例: 1. 引言 1.1 正则表达式的定义与历史 正则表达式(Regular Expression,简称 regex 或 regexp)是一种用于描述文本模式的强大工具。它最初由数学家 Stephen Kleene…...

【蓝桥】二维DP--摆花

&#x1f4cc;题目描述 &#x1f4cc;解题思路 &#x1f4cc;完整代码 &#x1f4cc;举例 &#x1f4cc;题目描述 &#x1f4cc;解题思路 动态规划&#xff08;DP&#xff09; 问题&#xff0c;核心是 “前 i 种物品&#xff0c;每种物品最多可以使用x 次&#xff0c;组成总和…...

在AMLOGIC android14 平台上使用adb

1.修改bootloader 编译&#xff1a;添加 --fastboot-write cd bootloader/uboot-repo ./mk s7d_bm201 --vab --avb2 --fastboot-write #./mk s7_bh201 --avb2 --vab --fastboot-write echo "compiled bootloader success!!!" cp build/u-boot.bin.signed ../../dev…...

力扣-二叉树-222 完全二叉树节点的数量

思路1 利用层序遍历所有节点即可 代码1 class Solution { public:int countNodes(TreeNode* root) {if(root nullptr) return 0;queue<TreeNode*> que;que.push(root);int size 0;while(!que.empty()){size que.size();int length que.size();while(length--){Tre…...

V93K测试机

爱德万V9300&#xff08;又称V93K&#xff09;是Advantest公司推出的高端可扩展SoC测试平台&#xff0c;在半导体测试领域具有标杆地位。以下为该设备的详细介绍&#xff1a; ### 一、核心性能与技术优势 1. **高速高精度测试能力** V9300支持高达112 Gbps PAM4信号&…...

【机器学习】监督学习-决策树-CART(Classification and Regression Tree,分类与回归树)详尽版

CART&#xff08;Classification and Regression Trees&#xff09;法 CART&#xff08;分类与回归树&#xff09;是一种决策树算法&#xff0c;由 Breiman 等人在 1984 年提出。它用于构建分类树&#xff08;Classification Tree&#xff09;或回归树&#xff08;Regression …...

Navicat 迁移数据库 传输数据

Navicat提供的数据传输功能&#xff0c;很好用&#xff0c;可以从一个数据库迁移到另外一个数据库。 步骤&#xff1a;菜单栏----工具—传输—选择源连接和数据库----选择目的地连接和数据库...

Jetpack Compose初体验

入门学习 由于工作需要&#xff0c;我们当前要在老代码的基础上使用 Compose 进行新页面的开发&#xff0c;这项工作主要落在我的身上。因此&#xff0c;我需要先了解 Compose。 这里我入门看的是写给初学者的Jetpack Compose教程&#xff0c;Lazy Layout&#xff0c;有兴趣可…...

ceph部署-14版本(nautilus)-使用ceph-ansible部署实验记录

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、环境信息二、部署步骤2.1 基础环境准备2.2 各节点docker环境安装2.3 搭建互信集群2.4 下载ceph-ansible 三、配置部署文件3.1 使用本地docker3.2 配置hosts…...

【C++】C++ 旅馆管理系统(含 源码+报告)【独一无二】

&#x1f449;博__主&#x1f448;&#xff1a;米码收割机 &#x1f449;技__能&#x1f448;&#xff1a;C/Python语言 &#x1f449;专__注&#x1f448;&#xff1a;专注主流机器人、人工智能等相关领域的开发、测试技术。 系列文章目录 目录 系列文章目录一、设计要求二、设…...

快速排序

目录 什么是快速排序&#xff1a; 图解&#xff1a; 递归法&#xff1a; 方法一&#xff08;Hoare法&#xff09;&#xff1a; 代码实现&#xff1a; 思路分析&#xff1a; 方法二&#xff08;挖坑法&#xff09;&#xff1a; 代码实现&#xff1a; 思路分析&#xff1a; 非递…...

国内 ChatGPT Plus/Pro 订阅教程

1. 登录 chat.openai.com 依次点击 Login &#xff0c;输入邮箱和密码 2. 点击升级 Upgrade 登录自己的 OpenAI 帐户后&#xff0c;点击左下角的 Upgrade to Plus&#xff0c;在弹窗中选择 Upgrade plan。 如果升级入口无法点击&#xff0c;那就访问这个网址&#xff0c;htt…...

易仓科技ai面试

请解释PHP中的面向对象编程的基本概念&#xff0c;并举例说明如何在PHP中定义一个类。 回答思路&#xff1a;需理解类、对象、继承和多态等基本概念&#xff0c;并能通过实例代码展示如何定义类及其属性和方法。 . 类&#xff08;Class&#xff09; 类是一个封装了数据和操作…...

LabVIEW用户界面(UI)和用户体验(UX)设计

作为一名 LabVIEW 开发者&#xff0c;满足功能需求、保障使用便捷与灵活只是基础要求。在如今这个用户体验至上的时代&#xff0c;为 LabVIEW 应用程序设计直观且具有美学感的界面&#xff0c;同样是不容忽视的关键任务。一个优秀的界面设计&#xff0c;不仅能提升用户对程序的…...

字玩FontPlayer开发笔记14 Vue3实现多边形工具

目录 字玩FontPlayer开发笔记14 Vue3实现多边形工具笔记整体流程临时变量多边形组件数据结构初始化多边形工具mousedown事件mousemove事件监听mouseup事件渲染控件将多边形转换为平滑的钢笔路径 字玩FontPlayer开发笔记14 Vue3实现多边形工具 字玩FontPlayer是笔者开源的一款字…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...

基于stm32F10x 系列微控制器的智能电子琴(附完整项目源码、详细接线及讲解视频)

注&#xff1a;文章末尾网盘链接中自取成品使用演示视频、项目源码、项目文档 所用硬件&#xff1a;STM32F103C8T6、无源蜂鸣器、44矩阵键盘、flash存储模块、OLED显示屏、RGB三色灯、面包板、杜邦线、usb转ttl串口 stm32f103c8t6 面包板 …...

stm32进入Infinite_Loop原因(因为有系统中断函数未自定义实现)

这是系统中断服务程序的默认处理汇编函数&#xff0c;如果我们没有定义实现某个中断函数&#xff0c;那么当stm32产生了该中断时&#xff0c;就会默认跑这里来了&#xff0c;所以我们打开了什么中断&#xff0c;一定要记得实现对应的系统中断函数&#xff0c;否则会进来一直循环…...