参考链接
四倍空间的原因如上图所示，但是实际操作时，我们可以直接开三倍空间也是可以的。
原因分析：
由于在分割区间时，我们计算mid使用下取整，所以左边区间大小大于等于右边区间大小，如果要实现上图中的树，极端情况下实现最多的空节点，那么节点总数必然是$3\ast 2^k$次方的形式，即所有次底层中每两个节点中有一个节点为叶子结点，也就是上图中的形式。
那么次底层的节点总数为$\frac{2n}{3}$，因为所有的叶子结点数为n。次底层中的一半才占据了三分之一的叶子结点。最底层所需的节点总数（包含空节点）为$\frac{4n}{3}$。由于空节点也是需要开辟空间，所以我们总需要的节点个数为$\frac{4n}{3}\ast 2-1$。也就是$\frac{8n}{3}$，小于3n。
笔者亲测，洛谷线段树题目中使用$\frac{8n}{3}$，并不会产生段溢出。