线段树（SgmntT）是常用的维护区间信息的数据结构，它可以在O(logn)的时间复杂度下实现单点修改、区间修改、区间查询（区间求和、区间最大值或区间最小值）等操作，常用来解决RMQ问题。
RMQ(RangMinimum/MaximumQury)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)其中i,j=n，返回数列A中下标在i,j里的最小(大）值。也就是说：RMQ问题是指求区间最值的问题。通常该类型题目的解法有递归分治、动态规划、线段树和单调栈/单调队列。
这篇内容断断续续写了两周，随着练习对线段树的理解不断深入，慢慢地学习下来也不觉得它有多么困难，更多的体会还是熟能生巧，虽然它起初看上去确实代码量大一些，但是我觉得只要大家放平心态，循序渐进的掌握下文中的三部分，也没什么难的。
1.线段树线段树会将每个长度不为1的区间划分成左右两个区间来递归求解，通过合并左右两区间的信息来求得当前区间的信息。
比如，我们将一个大小为5的数组nums={10,11,12,13,14}转换成线段树，并规定线段树的根节点编号为1。用数组t[]来保存线段树的节点，t表示线段树上编号为i的节点，图示如下：
图示中每个节点展示了区间和以及区间范围，t左子树节点为t[2i]，右子树节点为t[2i+1]。如果t记录的区间为[a,b]的话，那么左子树节点记录的区间为[a,mid]，右子树节点记录的区间为[mid+1,b]，其中mid=(a+b)/2。
现在我们已经对线段树有了基本的认识，接下来我们看看区间查询和单点修改的代码实现。
区间查询和单点修改线段树首先，我们定义线段树的节点：
/***定义线段树节点*/classNod{/***区间和或区间最大/最小值*/intval;intlft;intright;publicNod(intlft,intright){this.lft=lft;this.right=right;}}
注意其中的val字段保存的是区间的和。定义完树的节点，我们来看一下建树的逻辑，注意代码中的注释，我们为线段树分配的节点数组大小为原数组大小的4倍，这是考虑到数组转换成满二叉树的最坏情况。
publicSgmntT(int[]nums){this.nums=nums;t=nwNod[nums.lngth*4];//建树，注意表示区间时使用的是从1开始的索引值build(1,1,nums.lngth);}/***建树**
parampos当前节点编号*paramlft当前节点区间下界*paramright当前节点区间上界*/privatvoidbuild(intpos,intlft,intright){//创建节点t[pos]=nwNod(lft,right);//递归结束条件if(lft==right){//赋值t[pos].val=nums[lft-1];turn;}//如果没有到根节点，则继续递归intmid=lft+right1;build(pos1,lft,mid);build(pos11,mid+1,right);//当前节点的值是左子树和右子树节点的和pushUp(pos);}/***用于向上回溯时修改父节点的值*/privatvoidpushUp(intpos){t[pos].val=t[pos1].val+t[pos1
1].val;}
我们在建树时，表示区间并不是从索引0开始，而是从索引1开始，这样才能保证在计算左子树节点索引时为2i，右子树节点索引为2i+1。
build()方法执行时，我们会先在对应的位置上创建节点而不进行赋值，只有在递归到叶子节点时才赋值，此时区间大小为1，节点值即为当前区间的值。之后非叶子节点值都是通过pushUp()方法回溯加和当前节点的两个子节点值得出来的。
接下来我们看修改区间中的值，线段树对值的更新方法，