快乐地打牢基础(4)——树状数组

2023-12-30 06:38

本文主要是介绍快乐地打牢基础(4)——树状数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在解题的过程中,我们想维护一个数组的前缀和s[i] = A[1] + A[2] +…+A[i]。我们改变任意一个A[i],那么S[i]之后都会发生变化,朴素写法调整前缀和S最坏的情况需要O(n)的时间。所以引入树状数组,它的修改和求和都是O(logn)的,效率非常高。

一、基本思想


根据任意正整数关于2的不重复次幂的唯一分解性质,若一个正整数x的二进制表示为10101,其中等于1 的位置是0,2,4,那么正整数x可以被“二进制分解”成2 ^ 4 + 2 ^ 2 + 2^0。区间[1,x]可以被分成O(logx)个小区间。
长度为2 ^ 4的小区间[1,2 ^ 4]。
长度为2 ^ 2的小区间[2 ^ 4+1,2 ^ 4+2 ^ 2]。
长度为2 ^ 0的小区间[2 ^ 4+2 ^ 2 + 2,2 ^ 4+2 ^ 2 + 2 ^ 0]。

对于给定序列A,我们建立一个数组从,其中c[x]保存序列A的区间[x-lowbit(x)+1,x]中所有的和。
形成下图的树形结构:
在这里插入图片描述
从图中可以得到C[]和A[]关系:C[i]=A[i-2^ k+1]+A[i-2^k+2]+…A[i]; (k为i的二进制中末尾0的数量)
该结构满足一下的性质:

  • 1.每个内部结点C[x]保存以它为根的子树中所有叶结点的和。
  • 2.每个内部结点C[x]的子节点个数等于lowbit(x)的位数。
  • 3.除树根外,每个内部节点C[x]的父结点是C[x + lowbit(x)].
  • 4.树的深度为O(logN)。

二、算法操作


由于之前已经整理过树状数组原理的博客:https://blog.csdn.net/sinat_40872274/article/details/97895705
所以直接给出重要操作。
例如i=8时,k=3;

1.求lowbit(x)

lowbit(x)表示取出x的最低位1 换言之 lowbit(x)=2^k ( k为k为x的二进制中末尾0的数量)。
lowbit(x) = x&(-x)是怎么来的呢?具体分析一下

设x > 0,x的第k位上是最低位的1,后边还有若干个0。
先把x取反,此时第k位变成0,第0~到k-1位都是1。
再令x = x +1,此时因为进位,第k位变成1,第0~k-1位都是0.在上面的取反加1的 操作后,x的第k+1位到最高位因为取反,所以是与原来相反的,这样一来x&( ~ x+1)运算过后就只有第k位上是1了。而补码 ~x = -x-1 ,因此lowbit(x) = x&(-x)。
代码:


int lowbit(int x){return x&-x;
}
2.对某个元素进行加法操作

树状数组支持单点增加,意思是给序列中的某个数A[x]加上y,同时正确维护序列的前缀和,根据上面给出的树形结构和它的性质,只有结点C[x]及其所有祖先你结点保存的“区间和”包含结点A[x],而任意一个结点的祖先至多只有logN个,所以逐一对包含A[x]的C[]值进行更新就可以了,这样可以在O(logN)时间内执行单点增加操作。
那么我们的现在就是要解决如和找到A[x]的祖先结点。这就要回顾这个树形结构的第三点性质了。
在这里插入图片描述

  • 3.除树根外,每个内部节点C[x]的父结点是C[x + lowbit(x)]。

代码:

void update(int x,int y){for(;x<= N; x += lowbit(x)) c[x] += y;return ans;
}
3.查询前缀和

树状数组支持查询前缀和,即序列A第1~x个数的和。按照我们刚才提出的方法,应该求出x的二进制表示中每个等于1的位,把[1,x]分成O(logN)个小区间,而每个小区间的和都已经存在数组C[]中了,所以直接求代表每个小区间的C[]的和就行了。

int sum(int x){int ans = 0;for(; x; x -= lowbit(x)) ans += c[x];return ans;//可以发现求前缀和与加法操作 是两个逆序的过程
}
4.统计A[x]…A[y]的值

前缀和思想:sum(y) - sum(x-1)

5.多维树状数组

将一维的树状数组变成m维的,那么时间复杂度就是O((logN)^m),在m不大的时候,还是可以接受的。扩充的方法就是将原来的修改和查询函数中的一个循环,改成m个循环m维数组c中的操作。下面以n*m的二维数组a,树状数组c为例,给出单点增加和求和操作的代码。

//单点增加
void update(int x,int y ,int z){//将(x,y)的值加上zint i = x;while(i <= n){int j = y;while(j <= m

这篇关于快乐地打牢基础(4)——树状数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/552017

相关文章

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

安装centos8设置基础软件仓库时出错的解决方案

《安装centos8设置基础软件仓库时出错的解决方案》:本文主要介绍安装centos8设置基础软件仓库时出错的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录安装Centos8设置基础软件仓库时出错版本 8版本 8.2.200android4版本 javas

Linux基础命令@grep、wc、管道符的使用详解

《Linux基础命令@grep、wc、管道符的使用详解》:本文主要介绍Linux基础命令@grep、wc、管道符的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录grep概念语法作用演示一演示二演示三,带选项 -nwc概念语法作用wc,不带选项-c,统计字节数-

python操作redis基础

《python操作redis基础》Redis(RemoteDictionaryServer)是一个开源的、基于内存的键值对(Key-Value)存储系统,它通常用作数据库、缓存和消息代理,这篇文章... 目录1. Redis 简介2. 前提条件3. 安装 python Redis 客户端库4. 连接到 Re

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

SpringBoot基础框架详解

《SpringBoot基础框架详解》SpringBoot开发目的是为了简化Spring应用的创建、运行、调试和部署等,使用SpringBoot可以不用或者只需要很少的Spring配置就可以让企业项目快... 目录SpringBoot基础 – 框架介绍1.SpringBoot介绍1.1 概述1.2 核心功能2

Spring Boot集成SLF4j从基础到高级实践(最新推荐)

《SpringBoot集成SLF4j从基础到高级实践(最新推荐)》SLF4j(SimpleLoggingFacadeforJava)是一个日志门面(Facade),不是具体的日志实现,这篇文章主要介... 目录一、日志框架概述与SLF4j简介1.1 为什么需要日志框架1.2 主流日志框架对比1.3 SLF4