首页 > 其他分享 >树状数组——原理详解

树状数组——原理详解

时间：2024-10-20 09:32:19浏览次数：1  
标签：树状 int lowbit tree 详解 数组 节点

前言

这两天在网上学树状数组，但是发现网上关于树状数组的解释大都对初学者不太友善，原理讲解部分并不是很容易理解，所以写了一篇树状数组，顺便帮自己巩固一下。
在这里插入图片描述

一、什么是树状数组

1.概念：

简单来说，这是一种数据结构。顾名思义，它通过树的结构来对数组进行高效操作，一般用于求数组前缀和以及区间和，并且可以在线维护数组，时间复杂度为\(O(logN)\)。

2.优点：

与ST表相比，树状数组有在线修改的功能；与线段树相比，树状数组的代码更简单。
当然，树状数组的局限性更大，此处不过多展开。

3.本质：

利用了二进制特性。

二、树状数组原理详解

先来看一张图：（可继续往下读，无须看懂）
在这里插入图片描述图片来源于bilibili：〔manim | 算法 | 数据结构〕 完全理解并深入应用树状数组 | 支持多种动态维护区间操作

1.Lowbit

（1）定义

\(lowbit(x)\) 表示 \(x\) 在二进制下从右往左第一个 \(1\) 所代表的权值
例如：
\(lowbit(5_{10})=lowbit(101_2)=1_2=1_{10}\)
\(lowbit(12_{10})=lowbit(1100_2)=100_2=4_{10}\)

在十进制之下，\(lowbit(x)\) 表示的就是 \(x\) 以 \(2\) 为底指数最大的因数。当然，此处十进制意义不大。为了理解树状数组，我们只需要关注数字在二进制下的 \(lowbit()\) 即可，不需要关注十进制，也不需要关注二进制从右往左第一个 \(1\) 的左边是什么。

（2）Lowbit计算公式

公式如下：

\[lowbit(x)=x \&(-x) \]

① 机器码：原码、补码、反码

此处利用了计算机存储数字的特性。以 \(int\) 为例，一个 \(int\) 是 \(4\) 个字节，\(32\) 个比特。这 \(32\) 位中，最高位符号位，\(0\) 表示正数，\(1\) 表示负数。正数的存储即为其二进制（原码），负数的存储是其补码。
原码： 二进制表示
反码： 原码除符号位，其余各位取反
补码： 反码 \(+1\)

例如：
\(5\) 存储为 \(00000000\) \(00000000\) \(00000000\) \(00000101\)
\(-12\) 存储为 \(11111111\) \(11111111\) \(11111111\) \(11110100\)（补码）
（\(12\) 原码 \(00000000\) \(00000000\) \(00000000\) 00001100
反码 \(11111111\) \(11111111\) \(11111111\) \(11110011\)）

这样存储的意义是方便计算机利用符号位直接对机器数进行简单加法，从而完成减法运算，例如计算 \(5-12\) ，通过将二者机器数相加可以得到 \(11111111\) \(11111111\) \(11111111\) \(11111001\)， 即为 \(-7\) 的机器数。

② Lowbit 运算

以 \(12\) 为例：
\(12\) 与 \(-12\) 后八位编码分别为 $$00001100$$$$11110100$$
那么进行 \(\&\) 运算后就得到 \(000000100\)，即为 \(Lowbit(12)\)。

原理解释：
假设一个数 \(x\) 的编码是这样：\(\dots100\dots0\) ，加上负号 \(-x\) 即对原码取反再 \(+1\) ，取反变成 \(\dots011\dots1\)，\(+1\) 变成 \(\dots100\dots0\)，那么可以发现我们要求的 \(lowbit(x)\) 在 \(x\) 和 \(-x\) 中是一样的。
而更高位的数字由于取反，每一位都不同，那么 \(x\&(-x)\) 则可以得到后面的 \(lowbit(x)\) 部分。也就是说，任何一个 \(lowbit()\) ，取反再 \(+1\) 后一定为其本身。利用这个二进制特性，我们可以很方便地求得 \(lowbit()\)。

2.树状数组

（1）定义

（此处只是作者给出的定义，便于理解；网络上搜到的定义大多是描述性的，并没有明确的意思）

① 首先我们有一个数组 \(a[x]\) 用于存放原数列

② 树状数组是一个 \(int\) 型数组 \(tree[x]\)

③ 定义 \(tree[x]\) 表示以 \(a[x]\) 结尾，长度为 \(lowbit(x)\) 的一串数的和，即 \(tree[x]=\displaystyle\sum_{i=x-lowbit(x)+1}^{x}{a[i]}\)

（2）性质

我们将数组 \(a[x]\) 当做这棵树的叶节点，那么这棵树有以下性质：

性质① \(tree[x]\) 有 \(lowbit(x)\) 个子节点，其中一个为叶节点 \(a[x]\)

性质② \(tree[x]\) 的子节点为 \(tree[x-2^i] （i=0,1,2\dots(\log_2lowbit(x))-1）\) 和 \(a[x]\)

即 \(tree[x]=\displaystyle\sum_{i=0}^{(\log_2lowbit(x))-1}{tree[x-2^i]}+a[x]\)

性质③ \(tree[x]\) 的父节点为 \(tree[x+lowbit(x)]\)

结合下图理解三条性质：在这里插入图片描述图片来源于bilibili：〔manim | 算法 | 数据结构〕 完全理解并深入应用树状数组 | 支持多种动态维护区间操作

（3）原理

首先最重要的是定义 \(tree[x]\) 表示以 \(a[x]\) 结尾，长度为 \(lowbit(x)\) 的一串数的和，即 \(tree[x]=\displaystyle\sum_{i=x-lowbit(x)+1}^{x}{a[i]}\)，以及树的递推关系 \(tree[x]=\displaystyle\sum_{i=0}^{(\log_2lowbit(x))-1}{tree[x-2^i]}+a[x]\)

下面以 \(tree[8]\) 为例：

① 长度规律理解

\(lowbit(8)=1000_2\)，即 \(tree[8]\) 表示长度为 \(1000_2\) 的一串数的和。
可以发现，二进制下，\(1000=0111+0001=(0100+0010+0001)+0001\)
其中 \(0111=0100+0010+0001\) 代表 \(tree[4]+tree[6]+tree[7]\)，长度分别为 \(4\)、\(2\)、\(1\)；\(0001\) 代表 \(a[8]\)，长度为 \(1\)
其长度之和 \(4+2+1+1=8=lowbit(8)\)（再次强调，仅需关注一个数的 \(lowbit()\) 即可）

二进制可以直观地看出其中的规律，而用我们熟悉的十进制来描述就是：\(2^n=\displaystyle\sum_{i=0}^{n-1}{2^i}+1\) （利用等比数列求和公式即可得到）。至此我们已经可以理解长度的规律。

② 子节点规律理解

那么如何得到这些子节点的编号呢？公式如下：\(son(x)=x-lowbit(2^i)=x-2^i(i=0,1,2\dots,(log_2lowbit(x))-1)\)
我们要求 \(tree[x]\) 的所有子节点 \(tree[i]\) 表示的长度 \(lowbit(i)\) 之和再 \(+1\) 等于 \(lowbit(x)\)。而对于任意一个 \(x\)，有 \(lowbit(x-2^i)=lowbit(2^i)=2^i(i=0,1,2\dots,(log_2lowbit(x))-1)\)（这样求得的子节点就符合要求了）。论证也很简单：考虑 \(x=\dots100\dots0,lowbit(x)=100\dots0\)，则有 \(x-lowbit(2^i)=(x-1)-lowbit(2^i)+1=\dots011\dots1-2^i+1=\dots011\dots1011\dots1+1=\dots011\dots1100\dots0\)，那么上面那个式子就可以得到直观的理解了。

我们已经从父节点推出子节点，那么显然，子节点 \(tree[x]\) 唯一的父节点即为 \(tree[x+lowbit(x)]\) 。

至此，我们已经完全理解了节点的定义以及节点间的递推关系，那么以数组为基础的树也就建好了。这就是树状数组。

三、树状数组应用

（注意，树状数组开原数组的一倍空间即可，由定义易证。）

1.单点修改，区间查询

（1）题目：【模板】树状数组 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  • 将某一个数加上 \(x\)

  • 求出某区间每一个数的和

输入格式

第一行包含两个正整数 \(n,m\)，分别表示该数列数字的个数和操作的总个数。

第二行包含 \(n\) 个用空格分隔的整数，其中第 \(i\) 个数字表示数列第 \(i\) 项的初始值。

接下来 \(m\) 行每行包含 \(3\) 个整数，表示一个操作，具体如下：

  • 1 x k 含义：将第 \(x\) 个数加上 \(k\)

  • 2 x y 含义：输出区间 \([x,y]\) 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 \(2\) 的结果。

（2）建树：

虽然上文提及我们需要用数组 \(a[x]\) 存储原数列，但实际上我们并不会真正调用 \(a[x]\)，因此我们输入时只要将第 \(i\) 个数存储在 \(tree[i]\) 即可，并以此为基础自底向上完成建树过程。
代码如下：

int lowbit(int x)
{
	return x&(-x);
}
void build()
{
	for(int i=1;i<=n;i++)
	{
		int lb=lowbit(i);
		for(int j=1;j<lb;j<<=1)
		tree[i]+=tree[i-j];
	}
}

（3）单点修改：

自底向上逐个修改即可。
代码如下：

void add(int x,int k)
{
	for(int i=x;i<=n;i+=lowbit(i))
	tree[i]+=k;
}

（4）区间查询：

采用前缀和相减求区间和，只需依照定义循环求出 \(sum\) 即可。
代码如下：

int ask(int l,int r)
{
	int sum1=0,sum2=0;
	for(int i=r;i>=1;i-=lowbit(i)) sum1+=tree[i];
	for(int i=l-1;i>=1;i-=lowbit(i)) sum2+=tree[i];
	return sum1-sum2;
}

（5）完整代码：

#include<bits/stdc++.h>
using namespace std;
const int maxx=5*1e5+5;
int a[maxx],tree[maxx];
int n,m,cnt;int ans[maxx];
int lowbit(int x)
{
	return x&(-x);
}
void build()
{
	for(int i=1;i<=n;i++)
	{
		int lb=lowbit(i);
		for(int j=1;j<lb;j<<=1)
		tree[i]+=tree[i-j];
	}
}
void add(int x,int k)
{
	for(int i=x;i<=n;i+=lowbit(i))
	tree[i]+=k;
}
int ask(int l,int r)
{
	int sum1=0,sum2=0;
	for(int i=r;i>=1;i-=lowbit(i)) sum1+=tree[i];
	for(int i=l-1;i>=1;i-=lowbit(i)) sum2+=tree[i];
	return sum1-sum2;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>tree[i];
	
	build();
	
	int t,x,y;
	for(int i=1;i<=m;i++)
	{
		cin>>t>>x>>y;
		if(t==1) add(x,y);
		else ans[++cnt]=ask(x,y);
	}
	
	for(int i=1;i<=cnt;i++)
	cout<<ans[i]<<endl;
	
	return 0;
}

2.区间修改，单点查询

（1）题目：【模板】树状数组 2

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上 \(x\)；

  2. 求出某一个数的值。

输入格式

第一行包含两个整数 \(N\)、\(M\)，分别表示该数列数字的个数和操作的总个数。

第二行包含 \(N\) 个用空格分隔的整数，其中第 \(i\) 个数字表示数列第 $i $ 项的初始值。

接下来 \(M\) 行每行包含 \(2\) 或 \(4\)个整数，表示一个操作，具体如下：

操作 \(1\)： 格式：1 x y k 含义：将区间 \([x,y]\) 内每个数加上 \(k\)；

操作 \(2\)： 格式：2 x 含义：输出第 \(x\) 个数的值。

输出格式

输出包含若干行整数，即为所有操作 \(2\) 的结果。

（2）差分数组及其性质

此题与上一题区别在于修改和查询的范围不同。区间修改可以理解为修改区间内每个单点，单点查询可以理解为查询长度为 \(1\) 的区间，那么用上一题的模板也可以解决。但这样完全是小题大做，并且算法显然会超时。因此，此题我们需要使用差分数组，并利用树状数组维护它。

什么是差分数组？

其核心在于作差：
现已知一个数列 \(a[x](a[0]=0)\)，定义 \(b[x]=a[x]-a[x-1](x\ge1)\)，\(b[x]\) 即差分数组，有以下性质：

性质① \(a[x]=\displaystyle\sum_{i=1}^{x}{b[i]}\) （简单的累加，证略）

性质② 当对一个区间进行加法修改时，对应的差分数组只有头尾改变。

如：对 \([l,r]\) 内每个数 \(a[l\dots r]+k\)，那么对应的差分数组操作则是： \(b[l]+k,b[r+1]-k\)

那么，接下来我们可以利用性质①进行单点查询，利用性质②进行区间修改。也就是利用差分数组将区间修改转化为单点修改，将单点查询转化为区间（和）查询。

（3）输入简化

虽然我们需要使用差分数组，但是我们不必求每一个数和其前一个数的差。我们只需记录每一次区间操作带来的差分数组的改变即可。其核心原理是：加法满足交换律。

证明：
如果未简化，那么操作如下：（暂时不考虑使用树状数组优化）

① 输入 \(a[x]\)，并求得 \(b[x]\)，\(b[x]=a[x]-a[x-1]\)

② 对区间 \([l,r]\) 进行加法操作 \(a[l\dots r]+=k\)，并修改：\(b[l]=b[l]+k，b[r+1]=b[r+1]-k\)

③ 查询 \(a[x]\)，\(a[x]=\displaystyle\sum_{i=1}^{x}{b[i]}\)

我们会发现，\(a[x]=\displaystyle\sum_{i=1}^{x}{b[i]}=\displaystyle\sum_{i=1}^{x}{(a[x]-a[x-1]+k_i)}=a[x]+\displaystyle\sum_{i=1}^{x}{k_i}\)，\(k_i\) 指对 \(b[i]\) 进行的操作。因此我们只需要记录 \(k_i\) 即可，这样可以简化代码。再以树状数组 \(tree[x]\) 辅助维护即可。

（4）完整代码

#include<bits/stdc++.h>
using namespace std;
const int maxx=5*1e5+5;
int arr[maxx],tree[maxx];
int ans[maxx],cnt;
int n,m;
int lowbit(int x)
{
	return x&(-x);
}
void add(int l,int r,int k)
{
	for(int i=l;i<=n;i+=lowbit(i))
	tree[i]+=k;
	for(int i=r+1;i<=n;i+=lowbit(i))
	tree[i]-=k;
}
int ask(int x)
{
	int tmp=0;
	for(int i=x;i>=1;i=i-lowbit(i))
	tmp+=tree[i];
	return arr[x]+tmp;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>arr[i];
	
	int t,x,y,k;
	for(int i=1;i<=m;i++)
	{
		cin>>t;
		if(t==1)
		{
			cin>>x>>y>>k;
			add(x,y,k);
		}
		else
		{
			cin>>x;
			ans[++cnt]=ask(x);
		}
	}
	
	for(int i=1;i<=cnt;i++)
	cout<<ans[i]<<endl;
	
	return 0;
}

后记

说真的，Fenwick真的太天才了，理解树状数组之后，我佩服的五体投地。实在是太巧妙了%%%%%%

标签：树状,int,lowbit,tree,详解,数组,节点
From： https://www.cnblogs.com/Gcint-from-2024/p/18486943

相关文章

  • Java之反射机制详解
    一、基本概念Java反射（Reflection）是一种允许程序在运行时动态地检查和操作类、接口、字段、方法等内部信息的机制。通过反射，程序可以在不知道对象类型的情况下创建对象、调用方法和访问字段，甚至访问私有成员。反射机制为Java程序提供了极大的灵活性和扩展性，是Java语言中一个......
  • 二维数组1019
    publicclassPlaceDemo{publicstaticvoidmain(String[]args){//班级学生座位（二维数组）place();pace();}publicstaticvoidplace(){//静态初始化数组-----数据类型[][]数组名=new数据类型[]{元素1，元素2，元素3，··......
  • 数组练习1018
    假设班级有8名学生，录入8名学生的java成绩，成绩类型是小数，并输出平均分，最高分，最低分publicclassClassDemo2{publicstaticvoidmain(String[]args){//假设班级有8名学生，录入8名学生的java成绩，成绩类型是小数，并输出平均分，最高分，最低分studentSc......
  • 数组与字符串
    数组一维数组构造的数据类型之一，由若干数据类型相同的元素组成。其中数组名是地址常量不可修改，所以不能赋值操作，sizeof(数组名)求总内存空间。特点：数组不赋初始值，随机生成static修饰，默认位0部分赋值，其余默认为0//验证以上#include<iostream>usingnamespacestd;i......
  • 代码随想录算法训练营day20| 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树
    学习资料：https://programmercarl.com/0669.修剪二叉搜索树.html#算法公开课学习记录：669.修剪二叉搜索树（直接在原函数上操作，要根据情况用root的左右子树递归，因为子树中有满足条件的；前序：根左右）点击查看代码#Definitionforabinarytreenode.#classTreeNode:#def_......
  • Deepsort算法详解
    多目标跟踪的主要步骤：获取原视频帧利用目标检测器对视频帧中的目标进行检测将检测到的目标的框中的特征提取出来，该特征包括表观特征（方便特征对比避免IDswitch）和运动特征（运动特征方便卡尔曼滤波对其进行预测）表观特征与运动特征：表观特征：描述目标的外观信息，通常包括颜色、纹......
  • 2024/10/19日 日志--》关于MySQL中 JDBC的API 详解的整理简述
    今天进一步学习了JDBC中的API，已经可以初步连接数据库了，接下来继续进行学习。点击查看代码--JDBCAPI详解--DirverManager--DriverManager(驱动管理类)作用:1.注册驱动2.获取数据库连接--1.注册驱动--Class.forName("com.mysql.jdbc.Driver");--·需要注意的是:My......
  • USB协议详解第13讲（USB传输-控制传输及事务组成）
    1.前言前面讲过USB一个传输由多个事务组成，一个事务由多个包实体组成。传输又分为控制传输、同步传输、批量传输、中断传输四种，今天我们主要讲解控制传输三个阶段及事务组成。控制传输是一种特殊的传输方式，且传输过程相对复杂一些，但十分重要。当USB设备初次连接主机时，用控制传输......
  • USB协议详解第14讲（USB传输-同步传输及事务组成）
    1.前言前面讲过USB一个传输由多个事务组成，一个事务由多个包实体组成。传输又分为控制传输、同步传输、批量传输、中断传输四种，上一节我们讲了控制传输细节及事务组成，今天我们主要讲解同步传输及事务组成。同步传输用在数据量大、对实时性要求高的场合，例如音频设备、视频设备等，这......
  • 「图::连通」详解并查集并实现对应的功能 / 手撕数据结构（C++）
    目录概述成员变量创建销毁根节点访问路径压缩启发式合并复杂度Code概述并查集，故名思议，能合并、能查询的集合,在图的连通性问题和许多算法优化上着广泛的使用。这是一个什么数据结构呢？一般来讲，并查集是由一系列集合组成的集合群。其中，每个集合都有一个根节点，它的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99