线段树入门小结QUE：线段树？SUM：线段树和树状数组的联系与区别？

称谓：

从刘汝佳的书中得知，“这种数据结构在学术界没有统一的术语，但线段树是最常见的叫法。其他叫法包括区间树（interval

tree）、范围树（range

tree）等，但这些属于在特定的场合（如计算几何）中有着特殊的意义”。怎么叫看读者的心情，以下统一用线段树称呼。

先来作一些了解：

线段树是一棵二叉树，它的左右儿子也都是一棵线段树。（定义）

线段树也叫区间树，为什么叫它区间树呢？因为线段树是一种基于区间的数据结构。

线段树的每个节点代表一个区间

[l,r]，其中存储的是这个区间的特定值。

例如rmq（range minimum/maximum

query，范围最大/最小值）问题，给出n个元素的数组，查询任意区间内的元素最大/最小值。

这个问题就是基于区间查询的，需要用到线段树，而它节点中存储的特定值就是所代表区间的最大/最小值。

某个节点代表区间 [l,r]，其两个儿子节点代表区间分别为

[l,mid],[mid+1,r]（ mid = (l+r)/2 ）。

线段树的操作：

1、点修改

在[l,r]中修改[ll,rr](ll=rr)的时候有两种情况。

第一种，[ll,rr]被[l,mid]包含，此时直接在[l,mid]中修改[ll,rr]

第二种，[ll,rr]被[mid+1,r]包含，此时直接在[mid+1,r]中修改[ll,rr]（同理）

然后递归更新父亲。

不用考虑被截断（因为只是一个点）。

2、区间修改

在[l,r]中修改[ll,rr](ll<rr)的时候有三种情况。

第三种，较复杂的一种，[ll,rr]被mid从中截断，此时在[l,mid]中修改[ll,mid]，在[mid+1,r]中修改[mid+1,rr]，然后将两个查询得到的结果进行update，递归更新父亲。

这样便处理完了修改。

线段树的应用：

rmq问题，存储值，优化dp。

freecode :