线段树详解（含代码实现经过测试）

目录

1.线段树介绍
2.线段树原理及其实现
2.1区间修改
 2.2区间查询
 2.3区间更新

1.线段树介绍

什么是线段树？线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 [1] 
对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。-----来自百度。

2.线段树原理及其实现

线段树主要是把一段大区间 平均地划分 成两段小区间进行维护，再用小区间的值来更新大区间。这样既能保证正确性，又能使时间保持在 log ⁡ 级别（因为这棵线段树是平衡的）。也就是说一个[L,R]区间会被划分为两个区间分别是[L,(L+R)/2]和[(L+R)/2+1,

线段树详解（含代码实现经过测试）最先出现在Python成神之路。