详解树状数组（C/C++）

2024-09-01 13:36
文章标签 c++ 数组 详解 树状

本文主要是介绍详解树状数组（C/C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

树状数组（Binary Indexed Tree，简称BIT或Fenwick Tree）是一种用于高效处理数据序列的算法数据结构。它能够支持两个主要操作：单点更新和区间求和，这两个操作的时间复杂度都能达到O(log n)，其中 n 是数据序列的长度。树状数组非常适合处理那些需要频繁更新和查询区间和的问题。

基本原理

树状数组的核心思想是将数据序列映射到一棵二叉树中，这棵树并不是普通的二叉树，而是一棵完全二叉树，并且每个节点的值表示从该节点到叶子节点的区间和。通过这棵二叉树，我们可以快速地计算出任意区间的和。

树状数组由名字可知，它是一个树状结构，在点更新操作时，叶子节点的更新导致父亲节点的更新，从而带动整棵树的更新，它的结构是一棵树，树状的数组，它的值类似于前缀和的思想，每一个lowbit（i）都管着前面所有原数组的值，在进行更新或者计算时可以大大减少操作，从而做到减少时间复杂度的目的。

特点

1. 高效性：树状数组可以在O(log n)的时间复杂度完成点更新和区间求和，普通点更新和区间求和都需要O(n)，大大提升了效率。

2. 空间优化：相比于线段树，树状数组的空间复杂度更低，只需要一个大小为 n+1 的数组，并且树状数组的实现比线段树简单非常多。

3.树状数组的下标必须从1开始，不能从0开始。

核心操作

1. 单点更新：将单个点的值修改为num。
2. 区间求和：将数组第 l 个元素到第 r 个元素进行求和。

算法实现

下面将以C语言为例进行算法实现，lowbit函数会求出二进制数字的最低位代表哪个数字，例如10110，最低位为1的是2。

单点更新： 

add函数是对第x点增加k，此时我们就要更新其所有父亲节点，也就是每一步的lowbit(i)，使其所有管着它的父亲节点都增加k。

区间求和：

query函数是区间求和，求[1,x]范围内的和，如果求[n,m]范围内可以采用前缀和的思想实现，即query(m)-query(n-1)。 

#include<stdio.h>
int a[100005];
int c[100005];
int n,m;
int sum;
int lowbit(int x){//c[i]的区间长度，就是管着几个a[i]return x&(-x);
}
void add(int x,int k){//c[x]父子树更新加上k,a[x]加上k,点更新for(int i=x;i<=n;i+=lowbit(i)){c[i]+=k;}
}
int query(int x){//求区间和1--xint s=0;for(int i=x;i>0;i-=lowbit(i)){s+=c[i];}return s;
}
int main(){int i,j,x,y;scanf("%d%d",&n,&m);scanf("%d%d",&x,&y);for(i=1;i<=n;i++){//树状数组的下表必须从1开始scanf("%d",&a[i]);}for(i=1;i<=n;i++){add(i,a[i]);}add(m,m);//对第m个数改变mprintf("%d",query(y)-query(x-1));//求x--y区间的和return 0;
}

视频辅助讲解可以看一下这个动画讲解，非常形象-->点击直达<-- 

树状数组应用

树状数组在算法竞赛和实际应用中非常常见，主要有以下操作例如：

1. 求逆序对数量：

逆序对为前面的数比后面的数大，例如：【3， 1】这就是一对逆序对，【4，2，1，3】此序列有3对逆序对分别为【4，2】、【4，1】、【4，3】、【2，1】。

那么我们如何通过树状数组求逆序对的数量呢。首先我们初始化一个都为0的树状数组，把原数组进行离散化，保存下标pos到结构体之中，把原数组中的数据按照降序的顺序排序。此时离散化的下标就打乱了顺序。从头到尾遍历每一个位置，求它前一个位置的区间和就是此数与前面的数能够构成逆序对的数量，每遍历完一个，点更新一次，这样就对应了每遍历一次就进行一次区间求和、单点更新。

图解算法：

我们以【4，2，1，3】为例进行每一步模拟。

 树状数组求逆序对的视频讲解可以看一下董晓老师的讲解：C83 树状数组 P1908 逆序对_哔哩哔哩_bilibili

代码实现：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e5+5;
struct node{//val值pos位置int val,pos;
}a[N];
int c[N];
int n;
ll ans;
int lowbit(int x){//c[i]的区间长度，就是管着几个a[i]return x&(-x);
}
bool cmp(node A,node B){if(A.val==B.val){return A.pos>B.pos;}return A.val>B.val;
}
void add(int x,int k){//c[x]父子树更新加上k,a[x]加上k,点更新for(int i=x;i<=n;i+=lowbit(i)){c[i]+=k;}
}
int query(int x){//求区间和1--xint s=0;for(int i=x;i>0;i-=lowbit(i)){s+=c[i];}return s;
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i].val;a[i].pos=i;}sort(a+1,a+n+1,cmp);//降序排序for(int i=1;i<=n;i++){//遍历每个位置ans+=query(a[i].pos-1);//求它前一个位置的和---区间求和add(a[i].pos,1);//单点修改}cout<<ans<<endl;return 0;
}

 2. 区间修改，单点查询：

区间修改，单点查询与前面树状数组核心操作恰好相反，前面的树状数组都是前缀和的思想，那么将前缀和反过来就是差分，可以通过差分来实现区间修改与单点查询。

差分数组是这样定义的c[i]=a[i]-a[i-1](1<i<=n)，特殊情况在端点处c[1]=a[1]，c[n]=-a[n-1]，实现区间修改时例如在[l,r]区间+d操作，转换为差分数组c[l]+d，c[r+1]-d。当需要单点查询时，我们可以把差分数组利用前缀和的思想给还原回去，a[i]=c[i]+a[i-1]等价于1—i对差分数组进行求和。

代码实现：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e5+5;
int a[N],c[N];
int n;
ll ans;
int lowbit(int x){return x&(-x);
}
void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i)){c[i]+=k;}
}
int query(int x){//求区间和1--xint s=0;for(int i=x;i>0;i-=lowbit(i)){s+=c[i];}return s;
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];add(i,a[i]-a[i-1]);}//区间更新[l,r]上+kint l,r,k;cin>>l>>r>>k;add(l,k);add(r+1,-k);for(int i=1;i<=n;i++){cout<<query(i)<<" ";}cout<<endl;//查询第x点的值int x;cin>>x;cout<<query(x)<<endl;return 0;
}

3.TOP K问题（区间第K大问题）：

这类问题我们可以利用树状数组的思想，可以在O(nlogn)的时间内找到一个数组中第K大的元素。

主要步骤：

  1. 构建树状数组：首先，创建一个大小为n的树状数组，并将数组的初始值设为0。然后，将原始数组中的每个元素依次插入树状数组中，相当于进行了n次更新操作。

  2. 预处理树状数组：在构建树状数组的过程中，对于每个插入的元素，需要更新树状数组中对应位置的值。具体操作是将该位置上的值增加1。

  3. 查询第K大的元素：从大到小遍历原始数组中的元素，并从树状数组中查询对应位置的值。假设当前遍历的元素是a[i]，则查询树状数组中小于等于a[i]的元素数量。如果这个数量大于等于K，说明a[i]是第K大的元素；否则，将K减去这个数量，继续遍历下一个元素。

代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;const int N=2e5+5;
int n,k;
int c[N];int lowbit(int x){return x&(-x);
}
void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i)){c[i]+=k;}
}
int query(int x){int s=0;for(int i=x;i>0;i-=lowbit(i)){s+=c[i];}return s;
}
// 查询第K大的元素
int find_top_k(vector<int>& nums, int k) {// 离散化处理vector<int> sortedNums(nums);sort(sortedNums.begin(), sortedNums.end());for (int i = 0; i < n; i++) {nums[i] = lower_bound(sortedNums.begin(), sortedNums.end(), nums[i]) - sortedNums.begin() + 1;}// 更新树状数组for (int i = 0; i < n; i++) {add(nums[i], 1);}// 二分查找int left = 1, right = n;while (left < right) {int mid = (left + right) / 2;int count = query(mid);if (count >= k) {right = mid;} else {left = mid + 1;}}return sortedNums[left-1];
}int main() {cin>>n;vector<int> nums(n);for(int i=0;i<n;i++){cin>>nums[i];}cin>>k;cout << find_top_k(nums, k) << endl;return 0;
}

算法例题

洛谷 P1908 逆序对

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai​>aj​ 且i<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

输入格式

第一行，一个数 n，表示序列中有 n个数。

第二行 n 个数，表示给定的序列。序列中每个数字不超过 10^9。

输出格式

输出序列中逆序对的数目。

输入 

6
5 4 2 6 3 1

输出 

11
说明/提示

对于 25% 的数据，n≤2500

对于 50% 的数据，n≤4×10^4。

对于所有数据，n≤5×10^5

解题思路：

是树状数组求逆序对数量的模板题，直接复制上面的代码。

AC代码：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e5+5;
struct node{int val,pos;
}a[N];
int c[N];
int n;
ll ans;
int lowbit(int x){//c[i]的区间长度，就是管着几个a[i]return x&(-x);
}
bool cmp(node A,node B){if(A.val==B.val){return A.pos>B.pos;}return A.val>B.val;
}
void add(int x,int k){//c[x]父子树更新加上k,a[x]加上k,点更新for(int i=x;i<=n;i+=lowbit(i)){c[i]+=k;}
}
int query(int x){//求区间和1--xint s=0;for(int i=x;i>0;i-=lowbit(i)){s+=c[i];}return s;
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i].val;a[i].pos=i;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){ans+=query(a[i].pos-1);add(a[i].pos,1);}cout<<ans<<endl;return 0;
}

AcWing 244. 谜一样的牛

有 n 头奶牛，已知它们的身高为 1∼n 且各不相同，但不知道每头奶牛的具体身高。

现在这 n 头奶牛站成一列，已知第 i 头牛前面有 Ai 头牛比它低，求每头奶牛的身高。

输入格式

第 1 行：输入整数 n。

第 2..n 行：每行输入一个整数 Ai，第 i 行表示第 i 头牛前面有 Ai 头牛比它低。
（注意：因为第 1 头牛前面没有牛，所以并没有将它列出）

输出格式

输出包含 n 行，每行输出一个整数表示牛的身高。

第 i 行输出第 i 头牛的身高。

数据范围

1≤n≤10^5

输入样例：
5
1
2
1
0
输出样例：
2
4
5
3
1
解题思路：

这道题博主真的没有想到会用树状数组求解，本题解题方法为树状数组+二分，还是比较考验思维的，这道题的树状数组考察是前面所说的TOP K问题。题目看似很简单，但不知如何下手，这样的问题处理一般是先从边界处理，要么先处理最左边的，要么先处理最右边的。这道题我们从后往前处理，因为题目条件给出了第 i 头牛前面有 Ai 头牛比它低这个条件，这样可以二分出答案，不用考虑已经推出来的数，如果从前往后的话，还要考虑之前已经推出来的数。

由于每头牛的高度各不相同且在[1,n]之内，因此，对于倒数第二头牛而言，它应该在除去最后一头牛的身高，且在区间[1,n]中，选取比a[n−1]+1小的数且最接近的一个。其他的牛以此类推。假如建立一个全部元素为1的身高数列，某个位置的数为1代表这个高度还不知道是哪头牛的，那么就用树状数组维护该数列的前缀和，若某个位置的前缀和等于a[i+1]此时的下标就是要找的数。选择这个数后，将相应位置的1置0，可以二分这个位置。

AC代码：
#include<iostream>
using namespace std;
const int N=2e5+5;
int a[N],c[N],ans[N];//a是原数组c是树状数组ans是结果数组
int n;int lowbit(int x){return x&(-x);
}void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i)){c[i]+=k;}
}
int query(int x){int s=0;for(int i=x;i>0;i-=lowbit(i)){s+=c[i];}return s;
}
int main(){cin>>n;add(1,1);//点更新for(int i=2;i<=n;i++){cin>>a[i];add(i,1);}for(int i=n;i>=1;i--){//倒着先从最后一个往前推int l=1,r=n;while(l<r){//二分答案，需要找的数int mid=l+r>>1;if(query(mid)<a[i]+1){l=mid+1;}else{r=mid;}}ans[i]=l;//找到答案赋值add(l,-1);//置0，点更新}for(int i=1;i<=n;i++){cout<<ans[i]<<endl;}return 0;
}

AcWing 1265. 数星星

天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。

本题采用数学上的平面直角坐标系，即 x 轴向右为正方向，y 轴向上为正方向。

如果一个星星的左下方（包含正左和正下）有 k 颗星星，就说这颗星星是 k 级的。

例如，上图中星星 5 是 3 级的（1,2,4在它左下），星星 2,4 是 1 级的。

例图中有 1 个 0 级，2 个 1 级，1 个 2 级，1 个 3 级的星星。

给定星星的位置，输出各级星星的数目。

换句话说，给定 N 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

输入格式

第一行一个整数 N，表示星星的数目；

接下来 N行给出每颗星星的坐标，坐标用两个整数 x,y 表示；

不会有星星重叠。星星按 y 坐标增序给出，y 坐标相同的按 x 坐标增序给出。

解题思路、AC代码：

由于文章长度限制，这里不在详解，可以移步我的这一篇博客，专门讲解的这一道题。

AcWing 1265. 数星星（每日一题）_天空中有一些星星,这些星星都在不同的位置,每个星星有个坐标。 本题采用数学上的-CSDN博客

由此篇可见树状数组还是非常重要的，算法的效率也是非常高的，在算法竞赛中比较重要，希望对大家有所帮助，文章有错误的地方，恳请各位大佬指出。执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。 

这篇关于详解树状数组（C/C++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1127085。

相关文章

Linux下如何使用C++获取硬件信息

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息：读取"/proc/cpuinfo"文件获取磁盘信息：读取"/proc/diskstats"文
阅读更多...
Java数组初始化的五种方式

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化：简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化：灵活但需手动管理代
阅读更多...
Java使用SLF4J记录不同级别日志的示例详解

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J
阅读更多...
Java使用ANTLR4对Lua脚本语法校验详解

Java使用ANTLR4对Lua脚本语法校验详解

《Java使用ANTLR4对Lua脚本语法校验详解》ANTLR是一个强大的解析器生成器,用于读取、处理、执行或翻译结构化文本或二进制文件,下面就跟随小编一起看看Java如何使用ANTLR4对Lua脚本... 目录什么是ANTLR？第一个例子ANTLR4 的工作流程Lua脚本语法校验准备一个Lua Gramm
阅读更多...
一文详解如何在Python中从字符串中提取部分内容

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》：本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST（抽象语法树）、字符串操作... 目录前言解决方案方法一：使用正则表达式方法二：使用 Pyparsing方法三：使用 AST方法四：使用字
阅读更多...
C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
Python列表去重的4种核心方法与实战指南详解

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1：集合(set)去重法（最快速）方法2：顺序遍历法（保持顺序）方法3：副本删除法（原地修改）方法4：
阅读更多...
python logging模块详解及其日志定时清理方式

python logging模块详解及其日志定时清理方式

《pythonlogging模块详解及其日志定时清理方式》：本文主要介绍pythonlogging模块详解及其日志定时清理方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录python logging模块及日志定时清理1.创建logger对象2.logging.basicCo
阅读更多...
前端CSS Grid 布局示例详解

前端CSS Grid 布局示例详解

《前端CSSGrid布局示例详解》CSSGrid是一种二维布局系统，可以同时控制行和列，相比Flex（一维布局），更适合用在整体页面布局或复杂模块结构中,：本文主要介绍前端CSSGri... 目录css Grid 布局详解（通俗易懂版）一、概述二、基础概念三、创建 Grid 容器四、定义网格行和列五、设置行
阅读更多...
Node.js 数据库 CRUD 项目示例详解(完美解决方案)

Node.js 数据库 CRUD 项目示例详解(完美解决方案)

《Node.js数据库CRUD项目示例详解(完美解决方案)》：本文主要介绍Node.js数据库CRUD项目示例详解(完美解决方案),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考... 目录项目结构1. 初始化项目2. 配置数据库连接 (config/db.js)3. 创建模型 (models/
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2