线段树可以写成结构体的形式，专门用一个元素left和right来存储，这样的写法基本上属于学院派，一些非ACMer会这么写，而理解性上个人觉得并没有什么本质的提升。 作为ACMer的基础中的基础的数据结构，线段树写法一般是开一个4N的数组，用来存储线段树的各个节点。

线段树的节点：[1,N],[1,N/2],[N/2+1,N],… 假如N=9，则存在17个节点：[1,9] [1,5] [6,9] [1,3] [4,5] [6,7] [8,9] [1,2] [3,3] [4,4] [5,5] [6,6] [7,7] [8,8] [9,9] [1,1] [2,2] 可以容易发现线段树是一颗完全树。 节点在数组中的编码方案(采用从1开始数组)是： 0层[1,N] 1层[1,N/2]、[N/2+1,N] 2层[1,N/2/2]、[N/2/2+1,N/2]、[N/2+1,(N+N/2+1)/2]、[(N+N/2+1)/2+1,N] … 容易发现正如完全树的定义一样，除了最后一层，第i层有2^i个节点。 [1 2 4 8 …] 所以如果加上一个1的话，就可以构成了二次幂的坐标了 [1 1 2 4 8…] 加入开始那个1为-1层，那么我们就可以说到第i(i>=0)层，第一个节点的坐标是2^i。 可以试着自己画的一试就知道了，如果第一个节点放到0节点，那么会发现2^i出现的地方是每层的第二个节点，这样便形成了一种数学形式上的复杂，同时也会增大代码的复杂度。