ImOlivia_uu!

原创！

这是一件伟大的事情，因为本文的核心诞生于2023年4月12日，距离我开始学习OI仅7个月。
但是当时我还是一名被各种碾压的蒟蒻，于是放弃更新本文，如今，作为略有提升的蒟蒻，我要完善它。

设想

这是对线段树的一个空间优化，因为我当时刚学线段树，还不知道有动态开点这个东西，但是我设想的这个线段树，是完全符合普通线段树的规则，只是略作修改，使其和动态开点线段树一样，变成一棵满二叉树。

哦对了，还有一点很特殊，当时写的线段树都是根为0的，所以左节点是p2+1，右节点是p\2+2。

建树

普通建树

线段树模板中我们使用的建树方式是将父节点/2下放给子节点的

这样，在设置数组的时候我们总共需要n*4的数组（实际上占了4n-1的空间），这样的建树方式简单明了，容易记忆，同时也广为流传。

优化——完全二叉树建树

但是，如果我们把这棵线段树建成完全二叉树，它的空间需求就可以从n4降到n2（实际为定值2n-1）（如图）

经过计算，我们只需要找到不小于现节点区间大小的最小二的幂num，如果现节点区间大小大于num的3/4，则分界点为l+num/2，否则为r-num/4。

代码如下:

struct
{
	int sum;
} tree[n<<1]; //线段树
int t=1; //填充

void pushup(ll p)
{
	tree[p].sum=tree[p*2+1].sum+tree[p*2+2].sum;
}

void build(ll p,ll l,ll r)
{
	if(l==r)
	{
		tree[p].sum=t;
		t++;
		return;
	}
	
	//这里可能会使常数大一些
	//就是求不小于r-l+1即区间大小的2的幂 
	int num=pow(2,__lg(r-l+1));
	if((r-l+1)>num)
	{
		num<<=1;
	}
	
	//这个我目前没有证明 
	ll mid;
	if(r-l+1>num/4*3)
	{
		mid=l+num/2-1;
	}
	else
	{
		mid=r-num/4;
	}
	
	build(p*2+1,l,mid);
	build(p*2+2,mid+1,r);
	
	pushup(p);
}

这种建树方法将空间复杂度减少了一半。
事实上，因为完全二叉树的特性，我们也可以用循环建树，代码如下：

struct
{
  int sum;
}tree[n<<1];//线段树

void build(ll n)
{
	int num=pow(2,__lg(n));
	if(n>num)
	{
		num<<=1;
	}
	
	int a=2*n-num;
	int b=n;
	int i;
	for(i=2*n-2;a>=1;a--,i--)
	{
		tree[i].sum=a;
	}
	a=2*n-num;
	for(;b>a;b--,i--)
	{
		tree[i].sum=b;
	}
	for(;i>=0;i--)
	{
		tree[i].sum=tree[i*2+1].sum+tree[i*2+2].sum;
	}
} 

更新

普通更新

线段树的更新为：从上至下分发懒惰标记，在从下至上重新pushup。
这里不再赘述。

优化——完全二叉树更新