权值线段树

权值线段树，也成为值域线段树，是一种维护 值 而非 下标 的线段树。

前置知识

1. 权值线段树的本质仍然是线段树，需要先学习 下标线段树。
2. 权值线段树的本质是用线段树维护 桶，需要先学习桶。

权值线段树和下标线段树的联系与区别

下标线段树维护的信息是数列的区间信息，而权值线段树维护的是数列中每个数的出现次数。

权值线段树的代码实现

变量声明以及节点的新增、删除

struct Node{
	ll cnt;
	int ch[2];
}T[maxnode+1];
int rt[maxtot+1],seq=1,tot;
int del[maxnode+1],cnt;
int new_node(){
	return cnt?del[cnt--]:++tot;
}
void erase(const int u){
	del[++cnt]=u;
	T[u]={0ll,{0,0}};
}

修改操作

C++Copy
void modify(int&u,const int l,const int r,const int pos,const ll val){
	if(!u)u=new_node();
	T[u].cnt+=val;
	if(l==r)return;
	const int mid=(l+r)>>1;
	if(pos<=mid)modify(T[u].ch[0],l,mid,pos,val);
	else modify(T[u].ch[1],mid+1,r,pos,val);
}

合并操作

对于要合并的两棵子树：

1. 若两棵子树的根中有至少 $1$ 个不存在，直接返回；
2. 合并当前节点的信息；
3. 递归合并左子树；
4. 递归合并右子树；
5. 进行 pushup 操作（若有）。

C++Copy
int merge(const int x,const int y){
	if(!x||!y)return x|y;
	T[x].cnt+=T[y].cnt;
	T[x].ch[0]=merge(T[x].ch[0],T[y].ch[0]);
	T[x].ch[1]=merge(T[x].ch[1],T[y].ch[1]);
	erase(y);
	return x;
}

考虑该做法的时间复杂度，假设初始时有 $k$ 个节点待合并，其中 if(!x||!y) 这一操作只会在外界调用 merge 函数（低于 $O(k)$ 次）和 u1、u2 同时非空时的左右子节点。对于后者，每次都会让节点数减少 $1$ 个，最多调用 $O(k)$ 次，所以总时间复杂度为 $O(k)$（此处假设 pushup 函数是 $O(1)$ 的）。

分裂操作

C++Copy
void split(const int x,int&y,const ll k){
	if(!x)return;
	y=new_node();
	ll v=T[T[x].ch[0]].cnt;
	if(k>v)split(T[x].ch[1],T[y].ch[1],k-v);
	else std::swap(T[x].ch[1],T[y].ch[1]);
	if(k<v)split(T[x].ch[0],T[y].ch[0],k);
	T[y].cnt=T[x].cnt-k;
	T[x].cnt=k;
}

查询操作

与下标线段树相同。

例题：权值线段树

例题：线段树合并

例题：线段树分裂