数据结构

动态开点

有的时候线段树节点很多，并不需要一次全部建完整棵树，此时需要动态开点。

由于点是动态开的，所以每个点的字节点不是固定的，需要特意存一下。

权值线段树

权值线段数维护的不再是区间了，而是一堆桶。

举个例子，我们现在有一个长度为 10 的数组 1,5,2,3,4,1,3,4,4,4。

\(1\) 出现了 \(2\) 次，\(2\) 出现了 \(1\) 次，\(3\) 出现了 \(2\) 次，\(4\) 出现了 \(4\) 次，\(5\) 出现了 \(1\) 次。

那么这个线段树长这样：

线段数合并

代码

namespace XDS{
	ll tot=0;
	struct XDS_{ll lson,rson,val;}tr[N*40];
	#define ls(p) tr[p].lson
	#define rs(p) tr[p].rson
	#define va(p) tr[p].val
	#define bdmd ll mid=(l+r)>>1
	inline ll NewP(ll val){
		++tot;
		ls(tot)=0;
		rs(tot)=0;
		va(tot)=val;
		return tot;
	}
	inline void UpdateP(ll &p,ll l,ll r,ll x,ll val){
		if(!p)p=NewP(0);
		if(rx)return;
		if(l==r)va(p)+=val;
		else{
			bdmd;
			UpdateP(ls(p),l,mid,x,val);
			UpdateP(rs(p),mid+1,r,x,val);
			va(p)=va(ls(p))+va(rs(p));
		}
		return;
	}
	inline ll Ask(ll p,ll l,ll r,ll le,ll ri){
		if(!p)return 0;
		if(rri)return 0;
		if(le<=l&&r<=ri)return va(p);
		else{
			bdmd;
			ll ans1=Ask(ls(p),l,mid,le,ri);
			ll ans2=Ask(rs(p),mid+1,r,le,ri);
			return ans1+ans2;
		}
	}
	inline ll Merge(ll p1,ll p2,ll l,ll r){
		if(!p1)return p2;
		if(!p2)return p1;
		if(l==r)va(p1)+=va(p2);
		else{
			bdmd;
			ls(p1)=Merge(ls(p1),ls(p2),l,mid);
			rs(p1)=Merge(rs(p1),rs(p2),mid+1,r);
			va(p1)=va(ls(p1))+va(rs(p1));
		}
		return p1;
	}
	#undef ls
	#undef rs
	#undef va
	#undef md
}

例题

练习题