线段树是个很神奇的数据结构。
为了表述方便，假设n为2的幂，所有的log以2为底
单点修改线段树
现在有一个问题，我们应该怎么解决它呢？
我们只用存储所有同次幂不相交的2的幂的长度的区间即可。可以证明这只有$2n$个。
然后， 每一个大区间包含两个稍小一点的区间，可以从大区间到这两个小区间连边，于是构成了一个二叉树
单点修改
单点修改的时候，所有包含此数的区间的和都会变动，所以我们就依次从儿子向上更改即可，可以证明包含一个数的区间只有$log\ n$个
区间查询
查询比较麻烦一点，因为我们可以通过不超过$O(log\ n)$个记录的区间可以构成任意一个查询的区间。
如果一个区间的左右儿子都被用到了，那么这个区间必定会被用到。
那么，就可以不停的左右分割，直到分成了一个个属于待查区间的区间，把它们加起来即可。
区间修改线段树
首先要理解的就是懒标记表示当前这个子树都需要同时干些什么事情（e.g. 同时加上某个值，同时赋某个值）。
然后要设计一个下推操作，表示当前的区间的懒标记被处理了。
这个下推操作很简单，就是把当前的区间的和根据懒标记更新，并且把左右儿子的懒标记更新
区间修改
和查询一样把待查区间分成一个个小区间，然后对每个小区间打一个懒标记表示这个区间都要同时加上某个数，并且下推。
区间查询
和原来一样，只是要注意下推
容易写错的地方
- 在区间修改时左右儿子都更新完了要把当前的区间的和更新