【树状数组】树状数组入门(简单的原理讲解)

标签: 算法总结

看到一个很好的讲树状数组的博客,就直接借鉴过来了 ^_^

注明,转载自 https://www.cnblogs.com/findview/archive/2019/08/01/11281628.html

树状数组入门(简单的原理讲解)

树状数组可以解决什么样的问题:

这里通过一个简单的题目展开介绍,先输入一个长度为n的数组,然后我们有如下两种操作:

  1. 输入一个数m,输出数组中下标1~m的前缀和
  2. 对某个指定下标的数进行值的修改

多次执行上述两种操作


寻常方法
对于一个的数组,如果需要求1~m的前缀和我们可以将其从下标1开始对m个数进行求和,对于n次操作,时间复杂度是O(n^2),对于值的修改,我们可以直接通过下标找到要修改的数,n次操作时间复杂度为O(n),在数组n开得比较大的时候,求前缀和的效率显得低了

  • 那么有人提出了一种优化的方式:
    初始我们用一个数组A的保存每个位置的初始值,然后用一个辅助数组B存放的是下标为i的时候A数组的前i个的和(前缀和),那么当我们需要查询m个数的前缀和的时候只要直接使用下标对B数组进行查询即可,n次查询,时间复杂度为O(n),而此时,对于单点更新值的维护消耗,由原来的O(n)变成了O(n^2),因为每一次与更新单点值都会对后面的已经计算好的B数组前缀和的值造成影响,需要不断更新B数组的值,n次更新维护的消耗自然就变成了O(n^2),更新的效率变得低下

树状数组
那么是否有一种方法可以让查询和更新的时间复杂度都小一些呢,至少可以令人接受,这里将介绍树状数组如何处理前缀和查询和单点更新的问题,对于n次操作,时间复杂度都为O(nlogn)

  • 借用百度百科上的图片
    图1.jpg
    图2.jpg

如图,对于一个长度为n的数组,A数组存放的是数组的初始值,引入一个辅助数组C(我们通过C数组建立树状数组)

C1 = A1
C2 = C1 + A2 = A1 + A2
C3 = A3
C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4
C5 = A5
C6 = C5 + A6 = A5 + A6
C7 = A7
C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

我们称C[i]的值为下标为i的数所管辖的数的和,C[8]存放的就是被编号8所管辖的那些数的和(有8个),而下标为i的数所管辖的元素的个数则为2^k个(k为i的二进制的末尾0的个数)举两个例子查询下标m8和m5所管辖的数的和

  • 8 = 1000,末尾3个0,故k == 3,所管辖的个数为2^3 == 8,C8是8个数的和
  • 5 = 0101,末尾没有0,故k == 0,所管辖的个数为2^0 == 1,C5是一个数的和(它本身A5)

而对于输入的数m,我们要求编号为m的数的前缀和A1~Am(这里假设树状数组已经建立,即C1~C8的值已经求出,别着急,在本文的最下方会做出建立树状数组的过程讲解,因为现在是在求前缀和,就假设C数组已经可用了吧)举两个例子m7和m6(sum(i)表示求编号为i的前缀和)

  • m==7 sum(7) = C7 + C6 + C4
    那么我们是怎么得到编号7是由哪几个C[i]求和得到呢(C4, C6, C7怎么得到的),这里有介绍一种巧妙的方法:
    对于查询的m,将它转换成二进制后,不断对末尾的1的位置进行-1的操作,直到全部为0停止
    7的二进制为0111(C7得到),那么先对0111的末尾1的位置-1,得到0110 == 6(C6得到),再对0110末尾1位置-1,得到0100 == 4(C4得到),最后对0100末尾1位置-1后得到0000(结束信号),计算停止,至此C7,C6,C4全部得到,求和后就是m == 7时它的前缀和
  • m==6 sum(6) = C6 + C4
    m == 6时也是一样,先转成2进制等于0110,经过两次变换后为0100(C4)和0000(结束信号),那么求和后同样也得到了预计的结果

这里要介绍一个高效的方法,lowbit(int m),这是一个函数,它的作用是求出m的二进制表示的末尾1的位置,对于要查询m的前缀和,m = m - lowbit(m)代表不断对二进制末尾1进行-1操作,不断执行直到m == 0结束,就能得到前缀和由哪几个Cm构成,十分巧妙,lowbit也是树状数组的核心

int lowbit(int m){
    return m&(-m);
}

关于m&(-m)很多童鞋可能感到困惑,那么就不得不提及一下负数在计算机内存中的存储形式,负数在计算机中是以补码的形式存储的,如13的二进制表示为1101,那么-13的二进制而将13二进制按位取反,然后末尾+1,即0010 + 0001 = 0011,那么1101 & 0011== 0001,很显然得到m == 13二进制末尾1的位置是2的0次方位,将13 - 0001 == 12,再对12执行lowbit操作,1100 & 0100 == 0100,也很轻易得到了m == 12时二进制末尾1的位置是2的2次方位,将12 - 0100 == 8,再对8执行lowbit操作,0100 & 1100 == 0100,得到m == 8时二进制位是2的2次方位,8 - 0100 == 0(结束操作),通过循环得到的13,12,8,则sum(13) == C13 + C12 + C8

求前缀和的代码

int ans = 0;
int getSum(int m){
    while(m > 0){
        ans += C[m];
        m -= lowbit(m);
    }
}

对于n次前缀和的查询,时间复杂度为O(nlogn)
接下来讲解单点更新值
对于输入编号为x的值,要求为它的值附加一个value值,我们把图再一次拿下来
图3.jpg

假设x2,value5,那么我们先找到A[2]的位置,通过观察我们得知,如果修改了A[2]的值,那么管辖A[2]的C[2],C[4],C[8]的前缀和都要加上value(所有的祖先节点),那么和查询类似,我们如何得到C2的所有祖先节点呢(因为C2和A2的下标相同所以更新时查询从C[x]开始),依旧是上述的巧妙的方法,但是我们把它倒过来
对于要更新x位置的值,我们把x转换成二进制,不断对二进制最后一个1的位置+1,直到达到数组下标的最大值n结束

  • 对于给出的例子x2,假设数组下标上限n8,x转换成二进制后等于0010(C2),对末尾1的位置进行+1,得到0100(C4),对末尾的1的位置进行+1,得到1000(C8),循环结束,对C2,C4,C8的前缀和都要加上value,当然不能忘记对A[2]的值+value,单点更新值过程结束

给出代码

void update(int x, int value){
    A[x] += value;    //不能忘了对A数组进行维护,尽善尽美嘛
    while(x <= n){
        C[x] += value;
        x += lowbit(x);
    }
}

对于n次更新操作,时间复杂度同样为O(nlogn)

这里有一个注意事项,我们对于求前缀和与单点更新时,树状数组C是拿来直接使用的,那么问题来了,树什么时候建立好的,我怎么不知道??

事实上,对于一个输入的数组A,我们一次读取的过程,就可以想成是一个不断更新值的过程(把A1~An从0更新成我们输入的A[i]),所以一边读入A[i],一边将C[i]涉及到的祖先节点值更新,完成输入后树状数组C也就建立成功了

  • 完整代码如下:
#include<stdio.h>
#include<string.h>

int a[10005];
int c[10005];
int n;

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

int getSum(int x){
	int ans = 0;
	while(x > 0){
		ans += c[x];
		x -= lowbit(x);
	}
	return ans;
}

void update(int x, int value){
	a[x] += value;
	while(x <= n){
		c[x] += value;
		x += lowbit(x);
	}
}

int main(){
	while(scanf("%d", &n)!=EOF){	//用于测试n == 8 
		memset(a, 0, sizeof(a));
		memset(c, 0, sizeof(c));
		for(int i = 1; i <= n; i++){
			scanf("%d", &a[i]);		//a[i]的值根据具体题目自己安排测试可以1,2,3,4,5,6,7,8 
			update(i, a[i]);		//输入的过程就是更新的过程 
		}
		int ans = getSum(n-1);		//用于测试输出n-1的前缀和 输出28 
		printf("%d\n", ans);
	}	
	return 0;
} 
版权声明:本文为m0_38055352原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_38055352/article/details/105726733

智能推荐

VS2015错误—严重性代码说明项目文件行 禁止显示状态错误 C4996 fopen(‘fscanf‘、strcmp):This function or variable may be unsafe.

在运行时碰到下列错误: 看错误输出,需要将fopen改为fopen_s; 1.最普通的解决方法,就是使用fopen_s替代, fopen_s()函数的用法:fopen_s(_Outptr_result_maybenull_ FILE ** _File, _In_z_ const char * _Filename, _In_z_ const char * _Mode); fopen()函数的用法:f...

Vuejs——前端学习日记(二)

Vuejs——前端学习日记(二) Vue列表显示 新的指令和属性 后续 通过之前对Vuejs进行简单项目的学习,让我对Vuejs有了初步的认识,接下来是进一步的了解。 Vue列表显示 与之前看到的声明的简单变量message,name相比,数据列表是一个更加复杂的数据,所以在显示方面也会有所不同。在HTML代码中,我们会用v-for指令来显示列表。 如果用之前那样的方法来显...

设计模式之适配器模式

一、适配器模式的背景 在现实生活中,经常出现两个对象因接口不兼容而不能在一起工作的实例,这时需要第三者进行适配。例如,讲中文的人同讲英文的人对话时需要一个翻译,用直流电的笔记本电脑接交流电源时需要一个电源适配器,用计算机访问照相机的 SD 内存卡时需要一个读卡器等。 在软件设计中也可能出现:需要开发的具有某种业务功能的组件在现有的组件库中已经存在,但它们与当前系统的接口规范不兼容,如果重新开发这些...

Spring 4.x遇到的连接数据库拒绝访问

使用了Spring JdbcTemplate连接数据库, 提示 ‘Access denied for user ‘lil’@’192.168.3.104’ (using password: YES)’ , 问题记录与解决 使用了两种方法连接数据库 使用Java读取properties配置文件读取数据库配置(没有使用spring...

Day80.html的基本内容 -HTML和CSS

Html和CSS Javase → C/S模式 → Client / Server Javaweb→B/S模式 → Browser / Server 1. 前端BS软件结构 2. 前端的开发流程 3. 网页的组成部分 页面组成: 内容(结构)、表现、行为。 4. HTML简介 5… 创建HTML文件 创建一个web工程(静态的web工程) 在工...

猜你喜欢

排序算法

(1)冒泡排序 (2)快速排序参考博客(快排原理) 参考博客(形象化过程) 快排原理: 在要排的数(比如数组A)中选择一个中心值key(比如A[0]),通过一趟排序将数组A分成两部分,其中以key为中心,key右边都比key大,key左边的都key小,然后对这两部分分别重复这个过程,直到整个有序。 整个快排的过程就简化为了一趟排序的过程,然后递归调用就行了。 一趟排序的方法: 1,定义i=0,j=...

如何在Windows中获取Mac地址?

Mac Address is a network address used to layer 2 network traffic. The communication is done between network nodes with the mac address. It is important part of computer networking. In this tutorial, w...

使用stm32cubemx快速生成fatfs例程

使用stm32cubemx快速生成fatfs例程 前言 1. cubemx生成过程 1.1 sdio相关配置 1.2 系统时钟树配置 1.3 fatfs配置 1.4 修改工程的栈空间 2. 修改工程代码 2.1 fatfs sd卡读写文件的流程 2.2 具体代码的实现 3.实验现象 前言 本文将介绍如何使用stm32cubemx快速生成一个stm32 sdio 接口的fatfs例程,并实现对sd卡...

史上最简单maven配置与使用

什么是maven maven是用来帮助开发者管理项目所依赖的jar包的一款工具,创建maven工程使得开发不必再自己下载jar包,放入项目文件作为依赖,开发者只需在pom.xml文件里加入依赖的坐标即刻 什么是坐标 关于scope 配置 1、官网下载 2、环境配置 此电脑->属性->高级系统设置->环境变量 新建系统变量,变量名maven_home,变量值maven安装目录 系统...

U-Boot基本用法

U-Boot基本用法 mmc命令 帮助信息 打印板子信息 打印环境变量 设置、保存环境变量 U-Boot 倒计时 bootcmd 自定义环境变量 删除环境变量 mmc命令 帮助信息 查看全部命令:输入?,或help 查看某一个命令帮助信息:? + [命令] 打印板子信息 bdinfo 打印环境变量 printenv 设置、保存环境变量 设置:setenv 保存:saveenv U-Boot 倒计时...