基于完全二叉树实现线段树-- [爆竹声中一岁除,线段树下苦踌躇]

2024-02-10 19:04

本文主要是介绍基于完全二叉树实现线段树-- [爆竹声中一岁除,线段树下苦踌躇],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

文章目录

  • 一.完全二叉树
    • 完全二叉树的父子结点引索关系
  • 二.线段树
  • 三.基于完全二叉树实现线段树
    • 关于线段树的结点数量问题的证明
    • 递归建树
    • 递归查询区间和
    • 递归单点修改
    • 线段树模板题

一.完全二叉树

  • 完全二叉树的物理结构是线性表,逻辑结构是二叉树
    在这里插入图片描述

完全二叉树的父子结点引索关系

  • 通过子结点下标引索父结点下标 : 父结点下标 = 子节点下标/2;
  • 通过父结点下标引索左孩子下标 : 左孩子下标 = 父结点下标 * 2;
  • 通过父结点下标引索右孩子下标 : 右孩子下标 = (父结点下标 * 2) + 1;
    在这里插入图片描述

二.线段树

  • 线段树是一种基于分治思想实现的数据结构,用途非常广泛,常用于快速引索动态更新数组的区间和,以及解决众多类型的区间问题
  • 现有一个原数组,线段树结点表示一个结构体,结构体中存储原数组某一段区间的端点下标区间和
struct TreeNode{int left;   //原数组区间左端点下标int right;  //原数组区间右端点下标int Sum;    //区间和
}
  • 线段树根节点存储整个原数组的区间和,然后以区间二分的方式构建左子结点和右子结点:
    在这里插入图片描述
  • 以此类推,形成递归,直到将原数组区间划分为一个个单元素区间为止:
    在这里插入图片描述
  • 建树过程时间复杂度为O(N),引索更新的复杂度都是logN,比如要引索原数组[1,4]的区间和:
    在这里插入图片描述

三.基于完全二叉树实现线段树

在这里插入图片描述

关于线段树的结点数量问题的证明

  • 证明:若根节点的区间长度为N,线段树的总结点数量不会超过4*N
    在这里插入图片描述
  • 使用线段数时,数据范围为N,则定义一个4*N大小的完全二叉树数组防止算法中出现数组越界问题

递归建树

  • int BuildTree(TreeNode * Tree,int index,int left,int right)
    • 调用BuildTree(Tree,1,left,right)从下标1(根节点)开始递归建立线段树,[left,right]表示原数组的区间
    • 返回值表示原数组[left,right]的区间和
void Bulid(TreeNode* Tree,int index , int left , int right){//结点赋值Tree[index] = {left,right,0};if(right == left)return;//二分区间int mid = ((right - left) >> 1) + left;//构建左子树Bulid(Tree,index << 1,left, mid);//构建右子树Bulid(Tree,(index << 1)|1, mid + 1 , right);
}
  • 递归建树的时间复杂度为O(N)

递归查询区间和

  • int Get_Sum(TreeNode* Tree,int index , int left , int right)表示查询原数组[left,right]的区间和
//查询区间和
int Get_Sum(TreeNode* Tree,int index , int left , int right){//当前区间被目标区间包含则返回区间部分和if(Tree[index].left >= left && Tree[index].right <= right){return Tree[index].Sum;}//二分查询左右子树int mid = (Tree[index].left + Tree[index].right) >> 1;int res = 0;if(mid >= left) res = Get_Sum(Tree,index << 1,left,right);if(mid < right) res += Get_Sum(Tree,index << 1 | 1 , left , right);return res;
}
  • 关于复杂度的分析:
    在这里插入图片描述

递归单点修改

  • void modify(TreeNode* Tree,int index,int target,int change),原数组下标为target的元素加上change,调用时index1(根节点下标)开始递归
//原数组下标为target的元素加上change
void modify(TreeNode* Tree,int index,int target,int change){Tree[index].Sum += change;if(Tree[index].left  == Tree[index].right)return;//二分被修改区间int mid = (Tree[index].left + Tree[index].right) >> 1;if(target <= mid) modify(Tree,index << 1,target,change);  //递归修改左子树else modify(Tree,index << 1 | 1 , target,change);         //递归修改右子树
}

线段树模板题

线段树模板题1
线段树模板题2

在这里插入图片描述

这篇关于基于完全二叉树实现线段树-- [爆竹声中一岁除,线段树下苦踌躇]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、