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

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

什么是线段树

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

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

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