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

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

相关文章

Python位移操作和位运算的实现示例

《Python位移操作和位运算的实现示例》本文主要介绍了Python位移操作和位运算的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 位移操作1.1 左移操作 (<<)1.2 右移操作 (>>)注意事项:2. 位运算2.1

如何在 Spring Boot 中实现 FreeMarker 模板

《如何在SpringBoot中实现FreeMarker模板》FreeMarker是一种功能强大、轻量级的模板引擎,用于在Java应用中生成动态文本输出(如HTML、XML、邮件内容等),本文... 目录什么是 FreeMarker 模板?在 Spring Boot 中实现 FreeMarker 模板1. 环

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

SpringMVC 通过ajax 前后端数据交互的实现方法

《SpringMVC通过ajax前后端数据交互的实现方法》:本文主要介绍SpringMVC通过ajax前后端数据交互的实现方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价... 在前端的开发过程中,经常在html页面通过AJAX进行前后端数据的交互,SpringMVC的controll

Spring Security自定义身份认证的实现方法

《SpringSecurity自定义身份认证的实现方法》:本文主要介绍SpringSecurity自定义身份认证的实现方法,下面对SpringSecurity的这三种自定义身份认证进行详细讲解,... 目录1.内存身份认证(1)创建配置类(2)验证内存身份认证2.JDBC身份认证(1)数据准备 (2)配置依

利用python实现对excel文件进行加密

《利用python实现对excel文件进行加密》由于文件内容的私密性,需要对Excel文件进行加密,保护文件以免给第三方看到,本文将以Python语言为例,和大家讲讲如何对Excel文件进行加密,感兴... 目录前言方法一:使用pywin32库(仅限Windows)方法二:使用msoffcrypto-too

C#使用StackExchange.Redis实现分布式锁的两种方式介绍

《C#使用StackExchange.Redis实现分布式锁的两种方式介绍》分布式锁在集群的架构中发挥着重要的作用,:本文主要介绍C#使用StackExchange.Redis实现分布式锁的... 目录自定义分布式锁获取锁释放锁自动续期StackExchange.Redis分布式锁获取锁释放锁自动续期分布式

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删

SpringBoot整合mybatisPlus实现批量插入并获取ID详解

《SpringBoot整合mybatisPlus实现批量插入并获取ID详解》这篇文章主要为大家详细介绍了SpringBoot如何整合mybatisPlus实现批量插入并获取ID,文中的示例代码讲解详细... 目录【1】saveBATch(一万条数据总耗时:2478ms)【2】集合方式foreach(一万条数

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1