详解树状数组(C/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--x
  int 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个数改变m
  printf("%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--x
  int 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--x
  int 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]上+k
  int 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--x
  int 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博客

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


目录
打赏
0
0
0
0
1
分享
相关文章
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
【C++篇】深度解析类与对象(中)
在上一篇博客中,我们学习了C++类与对象的基础内容。这一次,我们将深入探讨C++类的关键特性,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载、以及取地址运算符的重载。这些内容是理解面向对象编程的关键,也帮助我们更好地掌握C++内存管理的细节和编码的高级技巧。
【C++篇】深度解析类与对象(上)
在C++中,类和对象是面向对象编程的基础组成部分。通过类,程序员可以对现实世界的实体进行模拟和抽象。类的基本概念包括成员变量、成员函数、访问控制等。本篇博客将介绍C++类与对象的基础知识,为后续学习打下良好的基础。
|
1月前
|
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
70 19
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
52 13
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
55 5
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
42 5
【C++面向对象——类的多态性与虚函数】计算图像面积(头歌实践教学平台习题)【合集】
本任务要求设计一个矩形类、圆形类和图形基类,计算并输出相应图形面积。相关知识点包括纯虚函数和抽象类的使用。 **目录:** - 任务描述 - 相关知识 - 纯虚函数 - 特点 - 使用场景 - 作用 - 注意事项 - 相关概念对比 - 抽象类的使用 - 定义与概念 - 使用场景 - 编程要求 - 测试说明 - 通关代码 - 测试结果 **任务概述:** 1. **图形基类(Shape)**:包含纯虚函数 `void PrintArea()`。 2. **矩形类(Rectangle)**:继承 Shape 类,重写 `Print
49 4