数据结构 玩转数据结构 9-1 什么是线段树

标签：米染 线段 玩转 logn 墙体 数据结构

0　　　　课程地址

https://coding.imooc.com/lesson/207.html#mid=13843

 

1　　　　重点关注

1.1　　　　线段树解决的问题

墙体染色

区间查询

某区间天空天体数量

 

1.2　　　　使用线段树和使用数组对比时间复杂度

实现方式 数组　　线段树

更新　　O(n)　　O(logn)　　

查询　　O(n)　　O(logn)

 

1.3　　　　线段树解析

每个节点存储的区间信息

 

 

 

2　　　　课程内容

2.1　　　　墙体染色解析：

• 场景：

一面墙长n米,3-8米染红色，5-7米染绿色（第二次会覆盖第一次的颜色），...m次操作后，我们在2-8米能看到多少种颜色

 

 

2.2　　　　扩展其他的堆

二项堆

斐波那契堆

 

 

3　　　　Coding

 

标签：米染,线段,玩转,logn,墙体,数据结构
From： https://www.cnblogs.com/1446358788-qq/p/17051896.html