一，什么是线段树
线段树是一种二叉搜索树，它将一个区间划分成一些单元区间
每个单元区间对应线段树中的一个叶结点
将[1,n]分解成若干特定的子区间(数量不超过4*n)
用线段树对“编号连续”的一些点，进行修改或者统计操作，修改和统计的复杂度都是O(log2(n))
用线段树统计的东西，必须符合区间加法，
也就是说，如果已知左右两子树的全部信息，比如要能够推出父节点
否则，不可能通过分成的子区间来得到[L,R]的统计结果
一个问题，只要能化成对一些“连续点”的修改和统计问题，基本就可以用线段树来解决了
解决问题时常会用到离散化
由上图可知，每个节点的左孩子区间范围为[l，mid]，右孩子为[mid+1,r]
对于结点k，左孩子结点为2*k(k<<1)，右孩子为2*k+1(k<<1|1)
原文：https://www.cnblogs.com/adelalove/p/11778751.html