数据结构/线段树详解与实现

数据结构/线段树详解与实现

此篇文章用于记录《玩转数据结构》课程的学习笔记

什么是线段树

线段树也被称为区间树,英文名为Segment Tree或者Interval tree,是一种高级的数据结构。这种数据结构更多出现在竞赛中,在常见的本科数据结构教材里没有介绍这种数据结构。但是,在面试中却有可能碰到和线段树相关的问题。那么为什么会产生线段树这种数据结构,线段树到底是为了解决什么样的一种问题呢?

其实这里的线段可以理解为区间,线段树就是为了解决区间问题的。

有一个很经典的线段树问题是:区间染色。

阅读更多