线段树c++

前言

在谈论到种种算法知识与数据结构的时候，线段树无疑总是与“简单”和“平常”联系起来的。而这些特征意味着，线段树作为一种常用的数据结构，有常用性，基础性和易用性等诸多特点。因此，今天我来讲一讲关于线段树的话题。

定义

首先，线段树是一棵“树”，而且是一棵完全二叉树。同时，“线段”两字反映出线段树的另一个特点：每个节点表示的是一个“线段”，或者说是一个区间。事实上，一棵线段树的根节点表示的是“整体”的区间，而它的左右子树也是一棵线段树，分别表示的是这个区间的左半边和右半边。

在此我们可以举一个例子来说明线段树通常的构造方法，以RMQ问题为例：

有N个数排成一排，每次询问某一段中的最小数。

构造的时候，让根节点表示区间[0,N-1]，即所有N个数所组成的一个区间，然后，把区间分成两半，分别由左右子树表示。不难证明，这样的线段树的节点数只有2N-1个，是O(N)级别的，如图：