树状数组

这篇具有很好参考价值的文章主要介绍了树状数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

「观前提醒」

「文章仅供学习和参考,如有问题请在评论区提出」


目录
  • 定义
  • 基本概念
  • 基本原理
  • 单点修改
    • 分析
    • 代码实现
  • 区间查询
    • 分析
    • 代码实现
  • 整体代码
  • 练手题目
  • 小结
  • 参考资料


定义


树状数组是一种支持 单点修改区间查询 的数据结构。

普通的树状数组只能用来维护像加法、乘法、异或等,这样满足结合律可差分的信息。

  • 结合律\((x \circ y) \circ z = x \circ(y \circ z)\) ,其中 \(\circ\) 是一个二元运算符。
  • 可差分:具有逆运算的运算,即已知 \(x \circ y\)\(x\) 可以求出 \(y\)

基本概念


对于普通的数组来存储数据,修改一个数的时间复杂度是 \(O(1)\) 的,但是区间查询则是 \(O(N)\) 。而对于前缀和数组来说,虽然它能够在 \(O(1)\) 的时间复杂度内进行区间查询,但是一旦数据有了修改,仍然要再 \(O(N)\) 地重新构造。

所以对于这种单点修改区间查询都有的操作,这两种数据结构都不能很好地完成任务。而树状数组就用了一种折中的法子来应对两种操作都有的情况,利用二进制的原理维护前缀和,从而达到:

  • 时间复杂度
    • 单点修改\(O(logN)\)
    • 区间查询\(O(logN)\)
  • 空间复杂度\(O(N)\)

基本原理


树状数组是根据二进制的原理对数据进行存储,基本存储逻辑如下图所示。

树状数组

\(a[i]\) 代表原数组的存储数据,\(C[i]\) 代表树状数组的存储数据。而我们从图中发现,\(C[i]\) 并不是直接存储的前缀和,而是存储了一段相对应的区间值。具体如下,

\[\begin{align} 首先我们定义: sum[x, y] = &\sum_{i = x}^{y} a[i] \\ C[1] = sum[1, 1] &= a[1] \\ C[2] = sum[1, 2] &= a[2] + C[1] \\ C[3] = sum[3, 3] &= a[3] \\ C[4] = sum[1, 4] &= a[4] + C[3] + C[2] \\ C[5] = sum[5, 5] &= a[5] \\ C[6] = sum[5, 6] &= a[6] + C[5] \\ C[7] = sum[7, 7] &= a[7] \\ C[8] = sum[1, 8] &= a[8] + C[7] + C[6] + C[4] \\ &... \\ C[16] = sum[1, 16] &= a[16] + C[15] + C[14] + C[12] + C[8]\\ &... \end{align} \]

这样的话,我们在查询前缀和的时候就只需要把相对应的区间加和就行了。

例如,当我们要获取 \(i = 15\) 时的前缀和 \(sum[1, 15]\) 时,就只需要把 \(1 \sim 15\) 里的 \(C[j]\) 和就行,即 \(sum[1, 15] = C[15] + C[14] + C[12] + C[8]\)

那么对于 \(C[i]\) 要存储的区间值的逻辑是什么呢?就是为什么 \(C[10] = sum[9, 10]\) ,而不是 \(sum[1, 10]\) 或者存储其他的区间值。而这里就是树状数组对二进制原理的应用,\(C[i]\) 要存储的区间值就和 \(x\) 的二进制表示有关。

根据二进制原理,对于一个正整数 \(x\) ,可以表示为

\[x = 2 ^ {b_{1}} + 2^{b_{2}} + ... + 2^{b_{k}} \]

\(b_{i}\) 代表 \(x\) 的二进制表示中,从低位到高位,第 \(i\)\(1\) 出现的位次(从 \(0\) 开始)。

例如: \(x = 11(1011_{2})\),那么 \(11 = 2^{0} + 2^{1} + 2^{3} = 1 + 2 + 8\)

那么我们发现, \(C[x]\) 要存储的区间值其实就是 \(sum[x - 2^{b_{1}} + 1, x]\) 。这里的 \(2^{b_{1}}\) 代表 \(x\) 的二进制表示中最低位 \(1\) 所对应的值,即

\[C[x] = \sum_{i = x - 2^{b_{1}} + 1}^{x} a[i] \]

例如,\(x = 12(1100_{2})\),最低位 \(1\) 所对应的值为 \(2^{2}\),所以 \(C[12] = sum[12 - 2^{2} + 1, 12] = sum[9, 12]\)


单点修改


分析


从上面我们知道树状数组 \(C[x] = sum[x - 2^{b_{1}} + 1, x]\) ,那我们每次对于 \(a[i]\) 的修改操作都得保证这种逻辑是存在的。

假设现在要给\(a[3]\) 加上 \(V_{0}\) 。然后我们观察图发现, \(C[3], C[4], C[8], C[16] ...\) ,它们的值是从 \(a[3]\) 那里作为一部分加和得来的。那么为了保证数据存储逻辑的成立,就得把它们的值也都加上\(V_{0}\)

树状数组

因为 \(C[x]\) 维护的是一个区间和,如果区间里的某一个值发生改变,那么 \(C[x]\) 也要做出相应的修改。同理,如果 \(C[x]\) 所维护区间被 \(C[y]\) 所包含,那么 \(C[y]\) 也需要做出相应的修改,然后一直往后找谁也需要被修改。那么我们就会发现,这不就是一个不断寻找自己父节点的过程(毕竟树状数组也算是个树结构),直到数组结尾。

那么问题来了,该怎么寻找 \(C[x]\) 的父节点呢?

这里先给出结论,对于 \(C[x]\) ,它的父节点就是 \(C[x + 2^{b_{1}}]\) 。这里的 \(2^{b_{1}}\) 和上面同理,代表 \(x\) 最低位的 \(1\) 所对应的值。那这个要怎么理解呢?

一种思路是,我们可以观察存储的逻辑图来找规律。我们发现 \(C[x]\) 的区间长度就等于 \(C[x]\) 到其父节点的距离,而 \(C[x]\) 的区间长度就为 \(2^{b_{1}}\)

树状数组

另一种思路就是,我们可以通过二进制来看。通过上图我们知道,\(C[8]\) 的子节点有 \(C[4], C[6], C[7]\) 。然后观察它们的二进制表示,

\[\begin{align} 8(1000_{2}) \enspace &= \enspace 4(0100_{2}) \enspace + \enspace 0100_{2} \\ &= \enspace 6(0110_{2}) \enspace + \enspace 0010_{2} \\ &= \enspace 7(0111_{2}) \enspace + \enspace 0001_{2} \\ \end{align} \]

同样我们也能得出结论,\(x\) 的父节点为 \(x + 2^{b_{1}}\) 。至于 \(x\) 最低位 \(1\) 所代表的数值,可以通过 \(lowbit(x)\) 来求。

这样每次通过 x += lowbit(x); 来更新数值,直到数组结尾 \(n\),最多需要执行 \(logn\) 次,所以一次修改操作的时间复杂度就是 \(O(logN)\)


lowbit(x) 解释(会的话可以直接跳过)

功能:可以用来求一个非负整数数 \(x\) 最低位 \(1\) 所代表的数值。

原理:它是利用了负数的补码特性。

我们知道,一个负数 \(-x\) 的二进制表示,是在其对应正数 \(x\) 的二进制表示进行取反加一 得来的。

例如,43 的二进制表示为 
           ...101011	// 前面省略 0
按位取反    ...010100	 // 前面省略 1
	+ 1    ...010101	// 前面省略 1
最后的出来的(...010101) 就是 -43 的二进制表示

\(lowbit(x)\) 是将 \(x\)\(-x\) 进行按位与(&)操作,然后得到 \(x\) 最低位 \(1\) 所代表的数。

\[\begin{align} x &= \enspace ...1001100_{2} \\ -x &= \enspace ...0110100_{2} \\ x \enspace \& -x &= \enspace ...0000100_{2} \\ \end{align} \]

代码实现

void lowbit(x) {
    return x & -x;
}

如果实在不明白,可以先去学一学二进制及位运算相关的知识。


代码实现

const int N = 1e5 + 10;

int tr[N];	// tr[] 存储树状数组数据
int a[N];	// a[] 存储原数组数据
int n;	// 数组的长度

// 返回非负整数 x 在二进制表示下最低位 1 及其后面 0 构成的数值
int lowbit(int x) { return x & -x; }

// 将数列中第 x 个数加上 c
void add(int x, int c) {
    // 不断寻找自己的父亲节点,然后加上增减的值
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += c;
}

// 使用举例
add(2, 3);	// 将数列中下标为 2 的数加上 3
add(5, -7);	// 将数列中下标为 5 的数减去 7

// 这里的每次操作都是对 tr[]进行修改, 而不会对 a[] 产生影响。

区间查询


分析


所谓区间查询,也就是利用前缀和 \(sum[l, r] = sum[1, r] - sum[1, l - 1]\) ,所以本质还是获取前缀和。

前面我们知道了树状数组每个 \(C[i]\) 所存储的是区间值,而想要每次查询操作来获取前缀和,就需要把这些区间值加在一起。那么对于每次操作要选择哪些区间相加呢?

然后拿出我们的万用图进行找规律(一招鲜,吃遍天

树状数组

我们能够发现,对于 \(sum[1, x]\) 值的获取,可以看成一个不断进行回退来获取 \(C[i]\) 的过程。例如,\(sum[1, 15] = C[15] + C[14] + C[12] + C[8]\) 。而每次需要回退的长度就是每个 \(C[i]\) 的区间长度,即每次获取最低位 \(1\) 所对应的数值。模拟过程就是,

\[\begin{align} sum[1, 13] = &C[12] + C[8] + C[0]\enspace (默认 C[0] 为 0)\\ 13 &= 1011_{2} \\ 回退 \enspace 0001_{2} \enspace 12 &= 1010_{2} \\ 回退 \enspace 0010_{2} \enspace \enspace 8 &= 1000_{2} \\ 回退 \enspace 1000_{2} \enspace \enspace 0 &= 0000_{2} \\ \end{align} \]

然后我们就能发现,这其实就是获取 \(x\) 每一位 \(1\) (从低位到高位)所对应的数值。

\[\begin{align} x = & 2^{b_{1}} + 2^{b_{2}} + ... + 2^{b_{k}} \\ sum[1, x] = \enspace & C[x - 2^{b_{1}}] \\ + &C[x - 2^{b_{1}} - 2^{b_{2}}] \\ + & ... \\ + &C[x - 2^{b_{1}} - 2^{b_{2}} - ... -2^{b_{k}}] \\ \end{align} \]

那么这样的话就也需要用到 \(lowbit(x)\) 来每次获取 \(x\) 最低位 \(1\) 所对应的数值,从而找到需要加和的 \(C[i]\) ,来实现查询前缀和的操作。

这样每次通过 x -= lowbit(x); 来更新数值,因为是对 \(x\) 的二进制进行操作,所以最多需要执行 \(logx\) 次,那么一次查询操作的时间复杂度就是 \(O(logN)\)


代码实现

const int N = 1e5 + 10;

int tr[N];	// tr[] 存储树状数组数据
int a[N];	// a[] 存储原数组数据

// 返回非负整数 x 在二进制表示下最低位 1 及其后面 0 构成的数值
int lowbit(int x) { return x & -x; }

// 查询数列前 x 个数的和
int query(int x) {
    int res = 0;
    // 不断进行回退, 直到 tr[0]
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

// 操作举例
int sum1 = query(x);	// 查询 [1, x] 的区间和
int sum2 = query(r) - query(l - 1);	// 查询 [l, r] 的区间和

整体代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int tr[N];	// tr[] 存储树状数组数据
int a[N];	// a[] 存储原数组数据
int n;

// 返回非负整数 x 在二进制表示下最低位 1 及其后面 0 构成的数值
int lowbit(int x) { return x & -x; }

// 将数列中第 x 个数加上 c
void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) 
        tr[i] += c;
}

// 查询数列前 x 个数的和
int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}


int main() {
    cin >> n;
    
    // 获取原数组数据
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    // 建立树状数组
    for (int i = 1; i <= n; i++) 
        add(i, a[i]);	// 在下标为 i 的位置加上 a[i]
    
    add(3, 20);	// 在下标为 3 的位置加上 20
    add(4, -30);// 在下标为 4 的位置减去 30
    add(2, 15 - (query(2) - query(1)));	// 将下标为 2 的位置的值改为 15
    
    int sum1 = query(11);	// 获取数列前 11 个数的和
    int sum2 = query(14) - query(3);	// 获取 [4, 14] 的区间和
    int sum3 = query(15) - query(14);   // 获取下标为 15 的值

    return 0;
}

练手题目


P3374 【模板】树状数组 1 - 洛谷

P3368 【模板】树状数组 2 - 洛谷


小结


树状数组巧妙地运用了二进制的存储逻辑,使得能够在 \(O(logN)\) 内完成单点修改区间查询 。虽然它的应用场景有局限性,有些问题还是需要用到线段树来解决。但是树状数组胜在代码简单,用的时候很好敲(相对于敲一个线段树)。
而且这里只是讲了树状数组最基本的应用,上面的例题也都是模板题。至于树状数组的拓展使用,之后应该会再写的。。。。

树状数组的扩展应用


参考资料


树状数组 - OI Wiki (oi-wiki.org):https://oi-wiki.org/ds/fenwick/文章来源地址https://www.toymoban.com/news/detail-599310.html


到了这里,关于树状数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 深度学习:从入门到精通课后习题解答本答案仅供参考

    第一章: 1、通过本章的学习,你认为深度学习崛起的原因有哪些? 答:(1) 计算能力的发展。深度学习的起源并不晚,但是在发展初期遭遇瓶颈的最主要原因是:当时的计算资源无法支持我们实现深度学习如此庞大复杂的计算。直到我们开始使用GPU进行计算后,深度学习才终

    2024年02月07日
    浏览(52)
  • 【JS逆向一】逆向某站的 加密参数算法--仅供学习参考

    逆向日期:2024.02.06 使用工具:Node.js 文章全程已做去敏处理!!!  【需要做的可联系我】 可使用AES进行解密处理(直接解密即可):在线AES加解密工具 1、打开某某网站(请使用文章开头的AES在线工具解密):T9mpG48zIdYFB40hkjsQS4+N5rr4x4mSPHlx5EoT/+s= 2、点击右上角的登录按钮,账号

    2024年02月22日
    浏览(54)
  • Unity单机手游逆向破解思路(仅供学习参考,禁止用于非法行为)

    一、安卓逆向常用工具 针对安卓单机游戏逆向,尤其是逆向使用Unity引擎开发的安卓游戏,只需了解下面的工具即可。 (1)Android Killer        Android Killer是安卓通用逆向工具,其可以对apk进行反向编译,得到smail代码,用户可以更改smail代码后,对apk重新打包,以实现破解

    2024年01月19日
    浏览(36)
  • 一篇搞定Ubuntu 22.04 下联网问题、 ifconfig、net-tools不能用的问题(亲测可行_仅供参考)

    刚下载的Ubuntu 联不上网、找不到ifconfig (告诉你要安装net-tools)但是输入 sudo apt install net-tools 又发现 E:无法定位软件包 net-tools 鼠标跟着“—”走 step1:打开虚拟网络编辑器 编辑—虚拟网络编辑器 —更改设置 —选择“NAT”模式—移除网络 —添加网络(哪一个都行问题不大

    2023年04月26日
    浏览(43)
  • Office 2019 激活-探索(仅供参考)

    1. 新建txt文件 2. 在新建txt文件中输入 @echooff (cd /d \\\"%~dp0\\\")(NET FILE||(powershell start-process -FilePath \\\'%0\\\' -verb runas)(exit /B)) NUL 21 title Office 2019 Activator r/Piracy echo Converting... mode 40,25 (if exist \\\"%ProgramFiles%Microsoft OfficeOffice16ospp.vbs\\\" cd /d \\\"%ProgramFiles%Microsoft OfficeOffice16\\\")(if exist \\\"%ProgramFiles(x

    2023年04月08日
    浏览(59)
  • LCD1602操作指令(仅供参考)

    1.清屏指令( 0000 0001 ) 1.清除液晶显示器,即将DDRAM的内容全部清除。 2.光标回到液晶屏左上方。 3.地址计数器(AC)的值设置为0。 2.光标归位指令(0000 001x) 1.把光标返回到液晶屏左上方。 2.把地址计数器(AC)的值设置为0。 3.保持DDRAM的内容不变。 3.模式设置指令(0000

    2024年02月05日
    浏览(34)
  • restful接口设计规范[仅供参考]

    应该尽量将API部署在专用域名之下。 如果确定API很简单,不会有进一步扩展,可以考虑放在主域名下。 应该将API的版本号放入URL。 另一种做法是,将版本号放在HTTP头信息中,但不如放入URL方便和直观。Github就采用了这种做法。 因为不同的版本,可以理解成同一种资源的不

    2024年02月15日
    浏览(45)
  • 我的医学预测模型评价步骤(仅供参考)

    个人意见,仅供参考 一切变化都是源于决策曲线分析,据说决策曲线分析已经获得了预测模型界的认可,也已经被写进了预测模型的报告指南–TRIPOD 中。一篇在pubmed上发表的关于如何使用决策曲线分析的指导论文,给出了使用决策曲线分析的几点推荐:1. 确定临床使用场景

    2024年02月02日
    浏览(60)
  • halcon不能连接海康相机解决方法(仅供参考)

    halcon不能连接相机有很多原因,这里作者给出其中一种的解决方法。 首先需要自行先下载海康软件,   1.首先点开Development, 2.根据图片的路径,点开以下文件夹  3.根据自己电脑安装的halcon版本打开对应文件夹     4.我的电脑是win64位的,根据自己的电脑打开对应的文件夹。

    2024年02月12日
    浏览(40)
  • uniapp获取手机号(前端部分,仅供参考~)

    html部分 js部分 api部分

    2024年02月09日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包