权值线段树

layout: post
title: 权值线段树
subtitle: 线段树的特殊运用，可以称之为小小平衡树
categories: 数据结构
tags: [线段树]

顾名思义，维护权值的线段树。在一定情况下可以代替平衡树使用。

原理是用线段树维护桶，节点维护子树中数的个数。所以空间开销与数据的值域相关。

那要是值域过大怎么办:离散化和动态开点，离散化可以将数据值域缩小到数据数量,将空间复杂度变为 \(O(n)\)，缺点是需要离线。而需要在线则需支持动态开点，即用多少开多少。

权值线段树:支持平衡树操作（翻转除外），并附带离散化

P3369普通平衡树

#include
using namespace std;
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define LL long long
#define N 100010
struct node_val_tree
{
	int l,r,mid;
	int d;
};
struct val_tree
{
	node_val_tree t[4*N];
	void build(int i,int l,int r)
	{
		t[i].l=l;t[i].r=r;t[i].mid=(l+r)>>1;
		t[i].d=0;
		if(l==r) return;
		build(i<<1,l,t[i].mid);
		build(i<<1|1,t[i].mid+1,r);
		return;
	}
	void insert(int i,int l,int k)
	{
		if(l==t[i].l&&t[i].r==l)
		{
			if(t[i].d+k>=0)t[i].d+=k;
			return;
		}
		if(l<=t[i].mid) insert(i<<1,l,k);
		if(t[i].mid+1<=l) insert(i<<1|1,l,k);
		t[i].d=(t[i<<1].d+t[i<<1|1].d);
		return; 
	}
	int kth(int i,int k)
	{
		if(t[i].l==t[i].r)
		{
			return t[i].l;
		}
		int res=0;
		if(k<=t[i<<1].d) res+=kth(i<<1,k);
		if(t[i<<1].d+1<=k) res+=kth(i<<1|1,k-t[i<<1].d);
		return res;
	}
	int query(int i,int l,int r)
	{
		if(l>r) return 0;
		if(l<=t[i].l&&t[i].r<=r)
		{
			return t[i].d;
		}
		int res=0;
		if(l<=t[i].mid) res+=query(i<<1,l,r);
		if(t[i].mid+1<=r) res+=query(i<<1|1,l,r);
		return res;
	}
	int rk(int k)
	{
		return query(1,1,k-1)+1;
	}
	int pre(int k)
	{
		return kth(1,rk(k)-1);
	}
	int nxt(int k)
	{
		return kth(1,rk(k+1));
	}
}t;
int n,opt[N],x[N];
int b[N],id[N],tot;
int c[N];
bool cmp_val(int xxx,int yyy)
{
	return b[xxx]