线段树简单实现
实现 简单 线段
2023-09-27 14:25:54 时间
首先,线段树是一棵满二叉树。(每个节点要么有两个孩子,要么是深度相同的叶子节点)
每个节点维护某个区间,根维护所有的。
如图,区间是二分父的区间。
当有n个元素,初始化需要o(n)时间,对区间操作需要o(logn)时间。
下面给出维护区间最小值的思路和代码
功能:
一样的,依旧是查询和改值。
查询[s,t]之间最小的数
修改某个值
从下往上,每个节点的值为左右区间较小的那一个即可。
这算是简单动态规划思想,做到了o(n),因为每个节点就访问一遍,而叶子节点一共n个,所以访问2n次即可。
如果利用深搜初始化,会到o(nlogn)。
https://blog.csdn.net/hebtu666/article/details/81777273
有介绍
那我们继续说,如何查询。
不要以为它是二分区间就只能查二分的那些区间,它能查任意区间。
比如上图,求1-7的最小值,查询1-4,5-6,7-7即可。
下面说过程:
递归实现:
如果要查询的区间和本节点区间没有重合,返回一个特别大的数即可,不要影响其他结果。
如果要查询的区间完全包含了本节点区间,返回自身的值
都不满足,对左右儿子做递归,返回较小的值。
如何更新?
更新ai,就要更新所有包含ai的区间。
可以从下往上不断更新,把节点的值更新为左右孩子较小的即可。
代码实现和相关注释:
注:没有具体的初始化,dp思路写过了,实在不想写了
初始全为INT_MAX
const int MAX_N=1<<7;
int n;
int tree[2*MAX_N-1];
//初始化
void gg(int nn)
{
n=1;
while(n<nn)n*=2;//把元素个数变为2的n次方
for(int i=0;i<2*n-1;i++)tree[i]=INTMAX;//所有值初始化为INTMAX
}
//查询区间最小值
int get(int a,int b,int k,int l,int r)//l和r是区间,k是节点下标,求[a,b)最小值
{
if(a>=r || b<=l)return INTMAX;//情况1
if(a<=l || b<=b)return tree[k];//情况2
int ll=get(a,b,k*2+1,l,(l+r)/2);//以前写过,左孩子公式
int rr=get(a,b,k*2+2,(l+r)/2,r);//右孩子
return min(ll,rr);
}
//更新
void update(int k,int a)//第k个值更新为a
{
//本身
k+=n-1;//加上前面一堆节点数
tree[k]=a;
//开始向上
while(k>0)
{
tree[k]=min(tree[2*k+1],tree[2*k+2]);
k=(k-1)/2//父的公式,也写过
}
}
相关文章
- Python 操作 Elasticsearch 实现 增 删 改 查
- node.js 实现一个简单的登录拦截器
- 用Tensorflow实现多层神经网络
- ssh密钥创建分发(端口号非22)&脚本实现自动创建分发密钥
- Android 简单用户中心布局实现
- python 实现简单的端口扫描器
- SpringBoot实现电子文件签字+合同系统!
- TopK的一个简单实现
- C# Remoting 简单实现
- 超简单集成HMS Scan Kit扫码SDK,轻松实现扫码购
- 使用storyboard实现页面跳转,简单的数据传递
- Django实现adminx后台识别用户身份的内容编辑与显示
- 线程的3种实现方式--内核级线程, 用户级线程和混合型线程
- 微信小程序云开发实现分页功能(简单易懂)
- BP神经网络与Python实现
- Android学习之界面切换的两种效果实现(直接跳转,滑动切换)
- Python 基础 之 词云(词的频率统计大小成图)的简单实现(包括图片词云,词云颜色,词的过滤)
- spring boot 2 + shiro 实现简单的身份验证例子
- 超简单的用C语言实现定时关闭计算机
- C#实现对象序列化为XML
- 设计模式-发布-订阅方式实现异步并发