订阅
线段树写法有很多种，一般来说有：①链表写法，因为线段树是一颗二叉树，写成二叉链表是没有问题的；②数组表示，素组表示一般来说比链表写法看似空了很多节点，而实际上，因为没有二叉链表的node *left、node * right指针，实际上是大大地节省了空间，而且没有链表指针转换操作，速度也会加快。
其中数组表示也有几种细微差别的写法：①节点下标从0开始还是1开始(注意是下标，不是值，值是正负或者实数都是无关系的)；②mid节点属于左边还是右边，这个会引起线段树最终的形状，比如mid属于左边，那么线段树的最后一层节点，偏左边；而mid属于右边，那么最后一层的节点往往会从右边开始排列。
注意：不管哪种写法线段树并非一颗完全二叉树！下文你就会自觉地发现。其中mid属于右边的写法，因为最终的节点在右边开始，已然不是完全二叉树。
ACMer学线段树一般都是需要使用线段树的数组表示，比较简约的一种方式是这里的这种方式，实际上利用了数组在内存地址的连续性，从而加快了进程，也节省了空间。
假设我们N个连续的节点需要建立线段树，如果最下层有节点，那么最左边一定不是空的。而最左边节点也就是左儿子是：[l,(l+r)>>1]。因此就是(1+N)不停除以2。那么线段树的深度为\(\lceil\log_2 (1+N)\rceil\) (根节点深度这里定义为1). 假如是满二叉树，那么节点数为
$$2^{\lceil\log_2 (1+N)\rceil}-1$$
通过matlab画图比较，容易得到下面的图像：
1-80个节点的情况
1-1e5的情况
例如N=20时：
线段树节点超过2N个的证明