应用场景
假设有这样的问题。 n个，有m次操作，操作为修改某一个数或查询一段区间的值
在分析下，如果对数组元素的修改可以在o(1)中完成，则需要o(1 )才能求出某个区间的值，如果m和n都大，则这种复杂度难以接受。
以前学习的3358www.Sina.com/算法解决了区间求和问题，时间复杂度为o(1)，但涉及前缀和操作时，既需要重新计算前缀，也需要重新计算数组，时间复杂度也为o
有没有办法兼顾这两个操作，降低时间的复杂性？
这就是我们要学习的修改修改和查询的时间复杂性线段树！
O(logn)！！！
先看看底线档的树长。
包括以下数组： 为了便于计算，数组的下标从1开始)
我们把它转换成了线树。 就像这样。
1 )叶子的节点(绿色)中保存了原始数组元素的值
2 )每个父节点是其两个子节点的值之和
3 )每个父节点记录它表示区间的范围，上图中的“1-2”表示1到2的区间
让我们来看看线档木是如何降低操作复杂性的！
算法思想
例如，需要调查2-5区间的和
使用递归的想法：
2~5之和
=2~3之和4~5之和
=3 5 4~5之和
=3 5 11
=19
总之，沿着名为查询操作的线路树再添加一个就可以了。
把区间分开
例如，要使节点2的值为3-5，必须沿红色部分逐个更改段树，直到根节点为止。
无论是修改操作还是查询操作，时间复杂度都是修改操作
下一步，我们来看看如何实现分段树！
O(logn)
首先，必须在内联树中创建原始数组，并基于树提供查询和修改操作。
算法实现
从上图可以看出，线段树约为建树，利用完全二叉树的性质，可以直接用完全二叉树保存。
如上图所示，对各节点进行编号。数组
所以，如果知道根节点的编号，就可以快速高效地找到左右子树的根节点
voidbuild(introot，int start，int end ) if ) start==end ) { tree[root]=num[start]； 返回； } int leftroot=root * 2； //左节点int rightroot=root * 2 1； //右节点intmid=(startend )/2； build (左根、开始、mid )； //递归计算左节点build (right root，mid 1，end )； //递归右节点tree [ root ]=tree [ left root ] tree [ right root ]； //根节点值=左根右根}
根节点编号是n,那它的左子树编号是2n,右子树的编号是2n+1
intquery(int root，int start，int end，int l，intr ) if ) l=startr=end ) { return tree[root]； } int leftroot=root * 2； int rightroot=root * 2 1； int mid=(开始)/2； int sum=0； if(L=mid ) sum=query (左根，开始，mid，l，r )； (if ) rmid ) ) sum=query ) rightroot，mid 1，end，l，r )； } return sum； } 查询
/***修改[l，r]区间的数量都是k值* @ param root * @ paramstart * @ param end * @ paraml * @ paramr * @ paramk */void update (id更新) } int leftroot=root * 2； int rightroot=root * 2 1； int mid=(开始)/2； if(L=mid ) )更新(left root，start，mid，l，r，k )； }if(rmid ) )更新) rightroot，mid 1，end，l，r，k )； } tree [ root ]=tree [ left root ] tree [ right root ]； } 修改
！！！：考虑下按区间修改元素值的复杂度？
1 )实现段树时，实际存储一定比原始数组大。 通常，将tree数组的长度设置为原始数据长度的3-4倍。
2 )本文中，只是为了学习线段树的实现原理，实际上使用结构体存储器对原排列的start、end更为简洁