权值线段树

就是把线段树变成桶。

用线段树维护桶。

代码：

模板：P1138 第 k 小整数

#include<bits/stdc++.h>
using namespace std;
int n,k;
struct segmentTree{
	struct node{
		int sum;
	}tr[40000<<2];
	#define lid now<<1
	#define rid now<<1|1
	void update(int now,int l,int r,int x,int y,int k)
	{
		if(x<=l&&r<=y)
		{
			tr[now].sum=k;return ;
		}
		int mid=(l+r)>>1;
		if(x<=mid) update(lid,l,mid,x,y,k);
		if(y>mid) update(rid,mid+1,r,x,y,k);
		tr[now].sum=tr[lid].sum+tr[rid].sum; 
	}
	int query(int now,int l,int r,int k)
	{
		if(l==r) return l;
		int mid=(l+r)>>1;
		if(tr[lid].sum>=k)  query(lid,l,mid,k);
		else  query(rid,mid+1,r,k-tr[lid].sum);
	}
}st;
int cnt;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) 
	{
		int t;cin>>t;
		st.update(1,1,30000,t,t,1);
	//	cout<<"upd\n";
	}
	if(k<=0||k>=st.tr[1].sum)
	{
		cout<<"NO RESULT";return 0;
	}
	cout<<st.query(1,1,30000,k);
}

作用

1. 查询第 \(k\) 大的数。

int kth(int now,int l,int r,int k)
{
	if(l==r) return l;
	int mid=(l+r)>>1;
	if(tr[lid].sum>=k) return kth(lid,l,mid,k);
	else return kth(rid,mid+1,r,k-tr[lid].sum);
}

2. 算逆序对（就是模板粘上去即可）

动态开点树

可以是线段树，也可以是权值线段树。

代码：

模板： P3369 【模板】普通平衡树

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int root=1,cnt=1;
int mx=2e7+1;
struct sgt{
	struct node{
		int sum,ls,rs;
	}tr[2000000<<1];
	#define lid tr[now].ls
	#define rid tr[now].rs
	void update(int &now,int l,int r,int x,int y,int k)
	{
		if(!now) now=++cnt;
		if(x<=l&&r<=y)
		{
			tr[now].sum+=k;
			return ;
		 } 
		int mid=(l+r)>>1;
		if(x<=mid) update(lid,l,mid,x,y,k);
		if(y>mid) update(rid,mid+1,r,x,y,k);
		tr[now].sum=tr[lid].sum+tr[rid].sum;
	}
	int query(int now,int l,int r,int x,int y)
	{
		if(x<=l&&r<=y) return tr[now].sum;
		int mid=(l+r)>>1,res=0;
		if(x<=mid) res+=query(lid,l,mid,x,y);
		if(y>mid) res+=query(rid,mid+1,r,x,y);
		return res; 
	}
	int kth(int now,int l,int r,int k)
	{
		if(l==r) return l;
		int mid=(l+r)>>1;
		if(tr[lid].sum>=k) return kth(lid,l,mid,k);
		else return kth(rid,mid+1,r,k-tr[lid].sum);
	}
}st;
map<int,int>mp;
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int op,t;
		scanf("%lld%lld",&op,&t);
		if(op==1)
		{
			st.update(root,-mx,mx,t,t,1);
			mp[t]++;
		}
		else if(op==2)
		{
			st.update(root,-mx,mx,t,t,-1);
			mp[t]--;
			if(!mp[t]) mp.erase(t);
		}
		else if(op==3)
		{
			cout<<st.query(root,-mx,mx,-mx,t-1)+1<<endl;
		}
		else if(op==4)
		{
			int res=st.kth(root,-mx,mx,t);
			cout<<res<<endl;
		}
		else if(op==5)
		{
			cout<<(--mp.lower_bound(t))->first<<endl;
		}
		else if(op==6)
		{
			cout<<mp.upper_bound(t)->first<<endl;
		}
	}
}

• 要注意的一点是，\(update\) 的时候的 \(now\) 要写成 int &now 来更改值；

• 每个操作 \(update\) 或者 \(query\) 的范围可以是负数、传进去的参数也可以是负数。

作用

缩小使用的空间。