动态开点线段树

引入

在普通的线段树中，我们一般要开 \(4N\) 的数组以避免越界。然而，在一些题目中，空间限制并不允许我们这样做。

考虑如下问题：

有一个长度为 \(n\) 的数组，初始全部为 \(0\)。给出 \(q\) 次操作，每次操作形如 1 x y k，表示将区间 \([x,y]\) 内每个数加上 \(k\)；或者形如 2 x y，表示要输出区间 \([x,y]\) 内每个数的和。\((1\le n\le 10^9,1\le q\le 10^4)\)

一道区间修改，区间查询的裸题，很容易想到用线段树实现，但\(n\) 的范围很大，开 \(4N\) 的数组肯定不行，而操作次数 \(q\) 比较小，也就是说如果 \(4N\) 的数组全部开满会有很多空间是没有用上的。

这个时候，就需要使用动态开点线段树。

动态开点线段树

我们来观察一下普通线段树的左儿子和右儿子的表示方法：

左儿子：p<<1

右儿子：p<<1|1

这样，虽然我们可以直接算出左右儿子，比较方便，但是，这样也浪费了大量的空间。

在学习二叉树的时候，二叉树还有哪种存储方法呢？

链式储存法，即对一个节点建立左右儿子指针，指向它的左右儿子。这样，建立新节点时，就不会浪费多余的空间。

这样一来，没有了空间的浪费，我们所需要的空间就大大减少了。对于动态开点二叉树，我们只需要开 \(q \log n\) 的数组就可以了。

为什么是 \(q \log n\) ？

一共 \(q\) 次询问，每次最多新开 \(2 \log n\)个节点，所以空间复杂度是 \(O(q \log n)\)

实现

动态开点线段树的实现和普通线段树差别不大，只是需要在使用节点时判断当前节点是否存在，如果不存在要建立新节点。

下面列出了与普通线段树有所不同的部分（洛谷 P3372 【模板】线段树 1）

因为动态开点，也就不需要提前build。

const int Q=1e4+10;
namespace SegmentTree{
	struct node{//左右孩子，延迟标记，区间和
		int ls,rs;
		ll add,sum;
	}t[Q*100];//一共q次询问，每次最多新开2*logn个节点，所以空间复杂度是O(qlogn)
	
	int tot=0,root=0;//总结点个数,根节点编号
	 
	void Pushdown(int x,int l,int r){//下推标记 
		int &lx=t[x].ls,&rx=t[x].rs,mid=(l+r)>>1;
		if(!lx) lx = ++tot;
		t[lx].w+=t[x].w;
		t[lx].sum+=(mid-l+1)*t[x].w;
		if(!rx) rx = ++tot;
		t[rx].w+=t[x].w;
		t[rx].sum+=(r-mid)*t[x].w;
		t[x].w=0;
	}
	
	
	void Pushup(int x){
		int &lx=t[x].ls,&rx=t[x].rs;
		t[x].sum=t[lx].sum+t[rx].sum;
	}
	
	
	void update(int &x,int l,int r,ll v,int L,int R)
	{//注意x需要引用传递，因为你可能需要加入新节点
		if(!x) x = ++tot;
		if(l>=L&&r<=R) {
			t[x].w+=v;
			t[x].sum+=v*(r-l+1);
			return;
		}
		int mid=(l+r)>>1;
		Pushdown(x,l,r);
		if(L<=mid) update(t[x].ls,l,mid,v,L,R);
		if(R>mid) update(t[x].rs,mid+1,r,v,L,R);
		Pushup(x);
	}
	
	
	ll query(int &x,int l,int r,int L,int R){
		if(!x) return 0;
		ll res=0;
		if(l>=L&&r<=R) return t[x].sum;
		int mid=(l+r)>>1;
		Pushdown(x,l,r);
		if(L<=mid) res+=query(t[x].ls,l,mid,L,R);
		if(R>mid) res+=query(t[x].rs,mid+1,r,L,R);
		Pushup(x);
		return res;
	}
}