【模板】权值线段树(值域线段树)

原文

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

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

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

动态开点线段树

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

P3369普通平衡树

#include<bits/stdc++.h>
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22