1、简述
线段树，也叫区段树，是一个完全二叉树，它在每个连接点储存一条直线（即“子二维数组”），因此常见于处理数列维护保养难题，它基础能确保每一个实际操作的复杂性为O(lgN)。
2、线段树操作过程
线段树的操作过程关键包含结构线段树，区段查看和区段改动。
（1） 线段树结构
最先详细介绍结构线段树的方式：让根节点表明区段[0,N-1]，即全部N数量所构成的一个区段，随后，把区段分为两截，各自由上下子树表明。不会太难证实，那样的线段树的连接点数仅有2N-一个，是O(N)等级的，如图所示：
显而易见，结构线段树是一个递归的全过程，伪代码以下：
//结构求得区段极小值的线段树
function 结构以v为根的子树
if v所表明的区段内只有一个原素
v区段的极小值就是这个原素, 结构全过程完毕
end if
把v隶属的区段一分为二，用w和x2个连接点表明。
标识v的左孩子是w，右孩子是x
各自结构以w和以x为根的子树（递归）
v区段的极小值 <- min(w区段的极小值,x区段的极小值)
end function
线段树除开最终一层外，前边每一层的节点全是满的，因而线段树的深层
h =ceil(log(2n -1))=O(log n)。
（2） 区段查看
区段查看指客户键入一个区段，获得该区段的相关信息内容，如区段中最高值，极小值，第N大的值等。
例如前边一个图上所显示的树，假如了解区段是[0,2]，或是了解的区段是[3,3]，不会太难立即寻找相匹配的连接点回应这一难题。但并非是全部的提出问题都那么非常容易回应，例如[0,3]，就沒有哪一个连接点纪录了这一区段的极小值。自然，解决方案也不会太难寻找：把[0,2]和[3,3]2个区段（他们在整数金额实际意义上是相接的2个区段）的极小值“合拼”起來，也就是求这两个极小值的极小值，就能求出[0,3]范畴的极小值。同样，针对别的了解的区段，也都能够寻找数个相接的区段，合拼后能够获得了解的区段。
区段查看的伪代码以下：
// node 为线段树的节点种类，在其中Left 和Right 各自表明区段上下节点
// Lch 和Rch 各自表明偏向上下小孩的表针
void Query(node *p, int a, int b) // 当今调查节点为p，查看区段为(a,b]
{
if (a <= p->Left && p->Right <= b)
// 假如当今节点的区段包括在查看区段内
{
...... // 升级結果
return;
}
Push_Down(p); // 直到下边的改动实际操作再表述这句话
int mid = (p->Left p->Right) / 2; // 测算上下子节点的隔开点
if (a < mid) Query(p->Lch, a, b); // 和左小孩有相交，调查左子节点
if (b > mid) Query(p->Rch, a, b); // 和右小孩有相交，调查右子节点
}
由此可见，那样的全过程一定挑选出了尽量避免的区段，他们相接后恰好包含了全部[l,r]，沒有反复都没有忽略。另外，充分考虑线段树上各层的连接点数最多会被选择两个，一共选择的连接点数也是O(log n)的，因而查看的算法复杂度也是O(log n)。
线段树并不宜全部区段查看状况，它的应用标准是“邻近的区段的信息内容能够被合拼成2个区段的并区段的信息内容”。即难题是能够被溶解处理的。
（3） 区段改动
当客户改动一个区段的值时，假如连着其子孙后代所有改动，则修改的连接点数一定会远远地超出O(log n)个。因此，假如要想把区段改动实际操作也操纵在O(log n)的時间内，只改动O(log n)个连接点的信息内容就成为必要。
效仿前一节区段查看采用的构思：区段改动时假如改动了一个连接点所表明的区段，也无需去改动它的孩子连接点。殊不知，针对被修改节点的先祖连接点，也务必升级它所纪录的值，不然查看实际操作就毫无疑问会出难题（如同改动单独连接点的状况一样）。
这种挑选出的连接点的先祖连接点立即升级值就可以，而挑选出的连接点的子孙后代却显而易见不可以那么简易地解决：每一个连接点的值务必能由兄弟俩连接点的非常值得到，如这幅图中的事例：
这儿，连接点[0,1]的值应该是4，可是兄弟俩的值又分别是3和5。假如查看[0,0]区段的RMQ，算出去的結果会是3，而标准答案显而易见是4。
难题显而易见取决于，虽然改动了一个连接点之后，无需改动它的孩子连接点，可是它的孩子连接点的信息内容实际上早已被更改了。这就必须我们在连接点里加设一个域：标识。把对连接点的改动状况存储在标识里边，那样，在我们由上而下地浏览某连接点时，就可以把一路上所碰到的全部标识都考虑到进来。
可是，在一个连接点携带标识时，会给升级这一连接点的值产生一些不便。再次上边的事例，假如我将部位0的数据从4改为了3，区段[0,0]的值应当变成3，但事实上，因为区段[0,1]有一个“加上了1”的标识，假如立即把值改动为3，则查看区段[0,0]的情况下大家会获得3 1=4这一不正确結果。可是，把这个3改为2，尽管恰当，却并不形象化，更不利营销推广（参照下边的一个事例）。
因此大家引进延迟时间标识的一些定义。每一个节点新提升一个标识，纪录这一节点是不是被开展了某类改动实际操作(这类改动实际操作会危害他的儿子节点)。還是像上边的一样，针对随意区段的改动，大家先依照查看的方法将其区划成线段树中的节点，随后改动这种节点的信息内容，并给这种节点标上意味着这类改动实际操作的标识。在改动和查看的情况下，如果我们到一个节点p ，而且决策考虑到他的儿子节点，那麼大家就需要看一下节点p 是否有标识，如果有，就需要依照标识改动他的儿子节点的信息内容，而且给子节点都标上同样的标识，另外消除p 的标识。编码架构为：
// node 为线段树的节点种类，在其中Left 和Right 各自表明区段上下节点
// Lch 和Rch 各自表明偏向上下小孩的表针
void Change(node *p, int a, int b) // 当今调查节点为p，改动区段为(a,b]
{
if (a <= p->Left && p->Right <= b)
// 假如当今节点的区段包括在改动区段内
{
...... // 改动当今节点的信息内容，并标出来标识
return;
}
Push_Down(p); // 把当今节点的标识往下传送
int mid = (p->Left p->Right) / 2; // 测算上下子节点的隔开点
if (a < mid) Change(p->Lch, a, b); // 和左小孩有相交，调查左子节点
if (b > mid) Change(p->Rch, a, b); // 和右小孩有相交，调查右子节点
Update(p); // 维护保养当今节点的信息内容（由于他的儿子节点的信息内容很有可能有变更）
}
3、运用
下边得出线段树的好多个运用：
（1）有一列数，初值所有为0。每一次能够开展下列三种实际操作中的一种：
a. 给特定区段的每一个数再加上一个特殊值；
b.将特定区段的全部数置成一个统一的值；
c.了解一个区段上的极小值、最高值、全部数的和。
得出一系列a.b.实际操作后，輸出c的結果。
[问题分析]
这个是典型性的线段树的运用。在每一个连接点上维护保养一下好多个自变量：delta（区段增长值），same（区段被置为某一值），min（区段极小值），max（区段最高值），sum（区段和），在其中delta和same归属于“延迟时间标识”。
（2）在全部不超30000的自然数范畴内探讨一个难题：已经知道n条直线，把节点先后键入让你，随后有m（≤30000）个了解，每一个了解键入一个点，规定这一点在是多少条直线上出現过。
[问题分析]
在这个问题中，我们可以立即对难题解决的区段创建线段树，在线段树上维护保养区段被遮盖的频次。将n条直线插进线段树，随后针对了解的每一个点，立即查看被遮盖的频次就可以。
可是大家在这儿用这道题型，更期待可以表明一个难题，那便是这道题型彻底能够无需线段树。大家将每一个直线分解成(L, 1)，(R 1,-1)的2个事情点，每一个了解点也在相匹配座标处再加上一个了解的事情点，排列以后扫描仪就可以进行题型的了解。大家这儿探讨的难题是一个线下的难题，因而大家也设计方案出了一个非常简单的线下优化算法。线段树在解决线上难题的情况下会更为合理，因为它维护保养了一个即时的信息内容。
这一题型也告知大家，有的题型虽然能够应用线段树解决，可是如果我们可以把握住题型的特性，就很有可能得到更为出色的优化算法。
（3）一次火车经过C个大城市，大城市序号先后为1到C，火车上现有S个坐位，路局要求卖出的火车票只有是坐票，即车里全部的游客都是有座，票务系统是由电子计算机实行的，每一个售票处申请办理包括三个主要参数，各自用O、D、N表明，O为起止站，D为到达站站，N为火车票页数，票务系统对该售票处申请办理做出审理或不审理的决策，仅有在从O到D的路段内火车上都是有N个或N个之上的空座时该售票处申请办理才被审理，你要写一个程序流程，完成这一全自动票务系统。
[问题分析]
这儿我们可以把全部的地铁站依次放到一个数轴上，在数轴上创建线段树，在线段树上维护保养区段的delta与max。每一次分辨一个售票处申请办理是不是行得通便是查看区段上的最高值；每一个插进一个售票处要求，便是给一个区段上全部的原素再加上买票数。
这道题型在线段树上维护保养的信息内容既包含自下高于一切的递推，也包含了从上至下的传送，可以较为全方位地对线段树的操作过程开展训炼。
（4）给一个n*n的格子旗盘，原始时每一个方格全是乳白色。如今要刷M次灰黑色或乳白色的漆料。每一次刷油漆的地区全是一个平行面旗盘边沿的矩形框地区。
键入n,M,及其每一次刷油漆的地区和色调，輸出刷了M次以后旗盘上也有多少个棋格是乳白色。
[问题分析]
最先大家从简易下手，考虑到一维的难题。即针对一个长短为n的乳白色直线，对它开展M次改动（每一次升级某一子地区的色调）。问最终还剩余的乳白色地区有多久。
针对这个问题，非常容易想起创建一棵线段树的实体模型。复杂性为O(Mlgn)。
拓展到二维，必须把线段树开展调节，即最先在横坐标轴上创建线段树，它的每一个连接点是一棵创建在纵轴上的线段树（即树中有树。称之为二维线段树）。复杂性为O(M(logn)^2)。
4、小结
运用线段树，我们可以高效率地了解和改动一个数列中某一区段的信息内容，而且编码也算不上尤其繁杂。
可是线段树也是有一定的局限的，在其中最显著的便是数列中数的数量务必固定不动，即不可以加上或删掉数列中的数。
5、参考文献
（1） 杨弋文章内容：《线段树》：http://download.csdn.net/source/2255479
（2） 刘亚文章内容《线段树的应用》：http://wenku.baidu.com/view/d65cf31fb7360b4c2e3f64ac.html
（3） 朱全员文章内容《线段树及其应用》：http://wenku.baidu.com/view/437ad3bec77da26925c5b0ba.html
（4） 线段树：http://wenku.baidu.com/view/32652a2d7375a417866f8f51.ht
