深刻理解树状数组--树状数组构造定义与动态维护区间和的合理性证明

在这里插入图片描述

文章目录

  • 一.树状数组概览
  • 二.树状数组构造定义
    • lowbit运算
    • 树状数组的结点值的定义
    • 树状数组结点层次的定义
    • 树状数组父子结点关系定义
  • 三.关于树状数组结构的重要证明
    • 引理1
    • 引理2
    • 树状数组模板题

一.树状数组概览

  • 树状数组的下标从1开始标识,其物理结构是线性表,逻辑结构是一颗多叉树
    在这里插入图片描述
  • 对于一个原数组,树状数组可以动态维护原数组的区间和
  • 下文中[]表示闭区间(包含端点),()表示开区间(不包含端点)

二.树状数组构造定义

lowbit运算

  • 得到一个整数二进制最低位的1的运算
int lowbit(int n){return n & (-n);
}
  • 根据计算机补码原理不难证明:
    在这里插入图片描述

树状数组的结点值的定义

  • 设原数组为arr,树状数组为Tree,Tree[n]表示原数组arr下标区间[n-lowbit(n)+1,n]中所有数的和
    在这里插入图片描述

  • 根据树状数组的结点值的定义,很容易可以得到一个求原数组前缀和的递归表达式:
    在这里插入图片描述

  • 现有树状数组Tree,可以给出求原数组arr区间[1,n]前缀和的函数:

int Get_Sum(int * Tree,int n){if(n == 0)return 0;return Get_Sum(Tree,n - lowbit(n)) + Tree[n];
}
  • 不难分析,该递归函数的时间复杂度为logN级别

树状数组结点层次的定义

  • 树状数组Tree[n]结点的层次为n二进制表示末位连续0的个数
  • 根据该定义可知,树状数组所有奇数位结点层次全部为0
    在这里插入图片描述
  • 根据该定义可知,设树状数组中结点x的层数为k,则结点x+lowbit(x)的层数一定大于k(根据lowbit运算的定义很容易可以证明)

树状数组父子结点关系定义

  • 树状数组Tree[n]结点的父节点定义为:Tree[n+lowbit(n)]
  • 根据上述定义,可以直观地感受一下树状数组的逻辑结构:
    在这里插入图片描述
    在这里插入图片描述

三.关于树状数组结构的重要证明

引理1

  • 引理1:树状数组第x个结点父结点所代表的原数组和区间[x+lowbit(x)-lowbit(x+lowbit(x))+1,x+lowbit(x)]包含x
    • 由于lowbit(x + lowbit(x)) > lowbit(x),所以x+lowbit(x)-lowbit(x+lowbit(x))+1 <= x,引理1成立

引理2

  • 引理2:树状数组第x个结点到其父结点之间的所有节点(不包括x结点和其父结点)所代表的原数组的和区间不包含x
    • 证明:在这里插入图片描述
    • 最严格的证明应写成数学表达式,但考虑到直观性,这里略过了(其实并不难)
  • 根据引理1和引理2,当原数组某个数arr[i]改变Δx时,树状数组只需从结点Tree[i]开始,沿着树中的路径向上层将每一个结点的值改变Δx就可以维持树状数组的数据结构完整性,实现了区间和的动态更新,时间复杂度为logN
    在这里插入图片描述
  • 原数组第n个元素改变change,树状数组Tree的更新函数:
//size表示树状数组的长度
void UpDate(int * Tree ,int size,int n , int change){for(int i = n  ; i <= size ; i+=lowbit(i)){Tree[i] += change;}
}

树状数组模板题

树状数组模板题1
树状数组模板提2

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/252177.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

c++入门学习④——对象的初始化和清理

目录 对象的初始化和清理&#xff1a; why? 如何进行初始化和清理呢&#xff1f; 使用构造函数和析构函数​编辑 构造函数语法: 析构函数语法: 构造函数的分类&#xff1a; 两种分类方式&#xff1a; 三种调用方法&#xff1a; 括号法&#xff08;默认构造函数调用&…

Meta开源大模型LLaMA2的部署使用

LLaMA2的部署使用 LLaMA2申请下载下载模型启动运行Llama2模型文本补全任务实现聊天任务LLaMA2编程Web UI操作 LLaMA2 申请下载 访问meta ai申请模型下载&#xff0c;注意有地区限制&#xff0c;建议选其他国家 申请后会收到邮件&#xff0c;内含一个下载URL地址&#xff0c;…

Redis -- set集合

挑战自己&#xff0c;每天进步一点点&#xff0c;成就将属于不停止脚步的你。 目录 Redis集合&#xff1f; 集合基本命令 sadd smembers sismember scard spop srandmember smove srem 集合间操作 sinter sinterstore sunion sdiff sdiifstore Redis集合&#…

Webpack源码浅析

webpack启动方式 webpack有两种启动方式&#xff1a; 通过webpack-cli脚手架来启动&#xff0c;即可以在Terminal终端直接运行&#xff1b; webpack ./debug/index.js --config ./debug/webpack.config.js通过require(webpack)引入包的方式执行&#xff1b;其实第一种方式最终…

vue3前端开发,element-plus前端框架探秘:scope对象

vue3前端开发&#xff0c;element-plus前端框架探秘:scope对象&#xff01;我们经常需要对当前行的数据进行操作&#xff0c;比如增加&#xff0c;删除&#xff0c;编辑等&#xff0c;为此我们需要传递当前行所对应的唯一主键,通常情况下&#xff0c;当前行对应的业务主键是id属…

CTFshow web(php特性 105-108)

web105 <?php /* # -*- coding: utf-8 -*- # Author: Firebasky # Date: 2020-09-16 11:25:09 # Last Modified by: h1xa # Last Modified time: 2020-09-28 22:34:07 */ highlight_file(__FILE__); include(flag.php); error_reporting(0); $error你还想要flag嘛&…

WPF控件-ItemsControl

介绍 ItemsControl是用于展示一组项的控件。我们常见的列表&#xff08;ListBox&#xff09;、数据表格&#xff08;DataGrid&#xff09;等都是继承自ItemsControl。可用于自定义样式展示各种批量的数据集合。 常见使用示例&#xff1a; <ItemsControl ItemsSource"…

Docker进阶篇-Docker网络

一、描述 1、docker不启动&#xff0c;默认网络情况 查看网卡情况使用&#xff0c;ifconfig或者ip addr ens33&#xff1a;本机网卡 lo&#xff1a;本机回环网络网卡 virbr0:在CentoS 7的安装过程中如果有选择相关虚拟化的的服务安装系统后&#xff0c;启动网卡时会发现 …

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之QRCode组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之QRCode组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、QRCode组件 用于显示单个二维码的组件。 子组件 无。 接口 QRCode(value: st…

C#中dll引用常见错误

当你在使用C#开发程序时&#xff0c;经常会遇到需要引用外部的dll文件来扩展程序的功能或者使用一些第三方库。然而&#xff0c;在引用这些dll文件的过程中&#xff0c;有时候会遇到一些问题&#xff0c;比如上面提到的错误信息&#xff1a;“未能加载文件或程序集“System.Run…

从零开始 TensorRT(4)命令行工具篇:trtexec 基本功能

前言 学习资料&#xff1a; TensorRT 源码示例 B站视频&#xff1a;TensorRT 教程 | 基于 8.6.1 版本 视频配套代码 cookbook 参考源码&#xff1a;cookbook → 07-Tool → trtexec 官方文档&#xff1a;trtexec 在 TensorRT 的安装目录 xxx/TensorRT-8.6.1.6/bin 下有命令行…

基于微信小程序的校园水电费管理小程序的研究与实现

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

SpringBoot项目打包成jar包供第三方使用实践

文章目录 1.使用者手动配置 basePackages1.1 第三方jar项目1.2 使用者项目1.2.1 使用者配置1.2.2 项目测试 2.使用者通过注解的方式引入2.1 第三方jar项目2.2 使用者项目2.2.1 使用者配置2.2.2 项目测试 3.SpringBoot Starter 方式3.1 第三方jar项目3.2 使用者项目3.2.1 使用者…

linux、windows 安装 vue-cli

Vue CLI 是一个基于 Vue.js 进行快速开发的完整系统&#xff0c;提供&#xff1a; 通过 vue/cli 实现的交互式的项目脚手架。 通过 vue/cli vue/cli-service-global 实现的零配置原型开发。 一个运行时依赖 (vue/cli-service) 可升级&#xff1b; 基于 webpack 构建&#…

【Linux操作系统】:Linux开发工具编辑器vim

目录 Linux 软件包管理器 yum 什么是软件包 注意事项 查看软件包 如何安装软件 如何卸载软件 Linux 开发工具 Linux编辑器-vim使用 vim的基本概念 vim的基本操作 vim正常模式命令集 插入模式 插入模式切换为命令模式 移动光标 删除文字 复制 替换 撤销 跳至指…

【Redis】字符串原理--简单动态字符串SDS

一.SDS定义 free 属性值为0&#xff0c;标识SDS没有分配任何未使用空间。len 属性值为5&#xff0c;标识SDS保存了一个5字节长度的字符串。buf 属性是一个char类型数组&#xff0c;数组的前5个字节保存了&#xff0c;R e d i s 五个字符&#xff0c;最后一个保存空字符串 \0…

Cassandra 命令大全

文章目录 1. 连接与基本操作2. 数据库管理3. 表&#xff08;Column Family&#xff09;操作4. 集群管理5. 权限管理6. 其他高级功能7. 条件查询与聚合操作8. 索引管理9. 用户权限和角色管理10. 安全性相关设置11. 一致性级别控制12. 用户定义类型 (UDTs)13. 用户定义函数 (UDFs…

【C生万物】C语言数据类型、变量和运算符

&#x1f4da;博客主页&#xff1a;爱敲代码的小杨. ✨专栏&#xff1a;《Java SE语法》 | 《数据结构与算法》 | 《C生万物》 ❤️感谢大家点赞&#x1f44d;&#x1f3fb;收藏⭐评论✍&#x1f3fb;&#xff0c;您的三连就是我持续更新的动力❤️ &#x1f64f;小杨水平有…

亚信安慧AntDB推动技术创新与满足用户需求

随着互联网技术的迅猛发展&#xff0c;大数据时代的到来&#xff0c;数据库的需求不断增长。在这样的背景下&#xff0c;国产分布式数据库正逐渐崭露头角&#xff0c;AntDB作为其中的重要代表&#xff0c;也积极参与到了这场竞争中。作为国内的技术创新者&#xff0c;AntDB不仅…

Solidworks 与 MATLAB 联合仿真

本文主要讲解了“MATLAB与SolidWorks的联合仿真怎么实现”&#xff0c;文中的讲解内容简单清晰&#xff0c;易于学习与理解&#xff0c;下面请大家跟着小编的思路慢慢深入&#xff0c;一起来研究和学习“MATLAB与SolidWorks的联合仿真怎么实现”吧&#xff01; 下载插件。 1、…