~~世界上真的有。。。CS~~

众所周知

线段树是一种非常强大的静态区间数据结构，它有着优秀的对数级时间复杂度，可以快速地解决包含结合律的信息处理。
举个栗子，区间和，区间最值，这些都是可以由两个相邻不相交的小区间合并而来。
但是，如果我说，

\mathbf{你其实不了解线段树的强大}

，你相信吗。

前置芝士，不懂就问

二分

权值线段树的强大在于它具有单调性，二分可以解决很多与值域相关的问题

离散化

离散化是对于缩小值域，减小空间开销来说十分必要。

线段树

（不是你连线段树都不会还学什么主席树？）

动态开点

主席树必须使用动态开点，否则会有极其恐怖的空间开销（详见后文）。

下面引入

假设你有一段长度为

N

的一个序列

a

，从

a_1

到

a_n

，现在你看它们很不爽，想调查它们，所以给出了一个查询操作：

给出形如 l r k 的三元组，查询序列 $a_l$ 到 $a_r$ 中第 $k$ 小的数，并输出。

聪明的你立刻想到，要是自己学过

\mathcal{莫队}

和

\mathcal{Treap}

，自己就可以通过一些神奇的区间挪动来简单的解决这道题了。

但是你不是十分的聪明，所以你只能另寻他法。

好在你的同学HZX十分的聪明，他告诉你，这道题可以用权值线段树来解决。

所以，权值是什么？

权值，就是指一个值，在序列中出现的次数。
比如说下面这个序列：

1 1 4 5 1 4

其中1的权值就是3，4的权值是2，5的权值是1。

那么，权值线段树又是什么？？

想想我们平时打的线段树，都是在原序列的基础上建立的。

而权值线段树，就是在原数组的权值数组上建立的。

以上面的序列为例，我们来建立一棵权值线段树。

首先，先把这个序列的权值数组求出来

3 0 0 2 1 0

（下标从 1 开始）

然后对着这个数组建立线段树即可（建树方法与普通线段树相同）。

细心的同学或许发现了，权值数组其实只和原数组的数值大小有关，也就是说，

\mathbf{权值数组第一个非0的数的下标是原数组的最小值}

\mathbf{权值数组最后一个非0的数的下标是原数组的最大值}

不理解可以自己看上面的两个序列自己推。

这个东西，我们通常叫做

\mathbf{值域}

。

道理我都懂，可是怎么做呢？

很简单，我们考虑这样一种思路：将原序列的前缀（从1到1，从1到2 。。。从1到n），分别看做是一个序列，对于它们（前缀数组）分别建立权值线段树，也就是说，我们一共要建

N

棵权值线段树，其中的第

i

棵表示原数组区间

[1,i]

的权值数组所建成的线段树。。。

嗯。。。

那又有什么用？

有的兄弟，有的。

我们不难发现，每棵权值线段树的形态都是一样的，虽然我们会将部分点省略，可是从存储的角度来说，它们都是一样的。

这意味着什么？

意味着不同的两棵线段树的相对应的节点之间可以做减法，当然，是它们存储的值做减法。

将在线段树上做减法简化一下，我们把它放到一段权值序列上。

2 0 0 1 0 0

这是第3棵权值线段树对应的权值数组[1,1,4]

3 0 0 1 1 0

这是第5棵权值线段树对应的权值数组[1,1,4,5,1]

如果我们把后者的每一个值都减去前者对应的值，那么恭喜你，得到了一个新的权值数组：

1 0 0 0 1 0

这是什么，仔细观察，发现它恰好与[5,1]这个序列的权值数组相同，如果自己多尝试几次，就会得出一个结论：

[1,R] 的权值数组与 [1,L] 的权值数组之间的差

就等于[L+1,R] 的权值数组

巧了，既然权值数组可以做减法，权值线段树也可以做减法，那么两者的含义是否相同？

相同的

所以我们只需要将第

R

棵权值线段树减去（这里指节点信息相减）第

L-1

棵权值线段树，就可以得到一棵新的权值线段树，代表区间

[L,R]

的权值数组所建立的权值线段树（当然，代码实现中并不需要把这棵权值线段树建出来）。

这其实省了很多事，我们只需要

N

棵前缀的权值线段树，就可以通过减法得到

\frac{N\times(N+1)}{2}

棵权值线段树的节点信息，省了很多时间和空间（你建树也是要时间的）。

问题来了，我知道这个又有什么用？

先别急，我的思路还没讲完。

假设我们有了一棵权值线段树，表示

[L,R]

区间，那么我们在上面查找第

K

小的数，只需要配凑就好了。

什么，你问我怎么配凑？

方法如下：
先看左半边的数的个数（因为是权值数组，所以数值越靠左，数值就越小，比

a

小的数，一定在权值数组上，在

a

（这里指下标）左边），记为

sum

。如果

sum \ge K

，那么区间第

K

小数一定在区间的左半边，否则就肯定在区间的右半边（自己好好想想）。

看到了这个二分，那么其实只要每次递归询问即可（有个小细节，如果值在左区间，查询的

K

不变，但是如果在右区间，在右区间查询右区间的区间第

K-sum

小值，其实这很好理解）。每次查询的规模为上一次的

\frac{1}{2}

，可以用主定理判断时间复杂度：

T(n)=T(\frac{1}{2}\times n)+\Theta(1)

T(n)=\Theta(\log_2 n)

单次的时间复杂度为对数级，时间性能十分优越。

但是问题又来了

你开

n

棵权值线段树，每棵的空间是

\Theta(4\times n)

的，那空间直接跑到

\Theta(n^2)

级别了，那你还打什么题。

难道，我们就要放弃这样一种时间非常优越的算法了吗？

实则不然，一个叫黄嘉泰的神犇在考场上仔细琢磨，发现前一棵权值线段树和后一棵权值线段树之间，有大量的节点信息是重复的。

具体来说，第

i-1

棵权值线段树和第

i

棵权值线段树之间，只有包含了区间

[i,i]

的节点才会有变化，这些节点的数量是

\Theta(\log_2 n)

级别的。

所以我们并不需要真的将那些没有变化的节点建出来占用空间，只需要让当前节点的其中一个子节点（左或右，视情况而定）指向前一棵权值线段树的对应节点就可以了。

不过这样一来就不能用普通线段树的

\Theta(n)

的建树方法了，只能每次对第

i

个点单独修改，还需要一个叫动态开点的技巧。

这样一来，每次修改操作会导致

\Theta(\log_2 n)

的新节点被建出来，总共只要

\Theta(n\times log_2 n)

的节点，是不是少了很多？

那么其实这道题已经做完了。

Talk is CHEAP ,Show you my Code

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
const int INF=1e9+10,N=2e5+10;
int root[N],tot=0;
struct node{
	int ls,rs,w;
}a[N*30];//动态开点，空间要预留好
void build(int &x,int l,int r){//建一棵0的空树，有的题不建会RE
	x=++tot;
	if(l==r) return;
	int mid=l+r>>1;
	build(a[x].ls,l,mid);
	build(a[x].rs,mid+1,r);
}
int update(int pos,int last,int l,int r,int w){//修改点，借用的上一棵线段树的点，覆盖的区间，加的值 
	int x=++tot;
	a[x]=a[last];
	a[x].w+=w;
	if(l==r) return x;
	int mid=l+r>>1;
	if(pos<=mid) a[x].ls=update(pos,a[x].ls,l,mid,w);
	else a[x].rs=update(pos,a[x].rs,mid+1,r,w);
	return x;
}
int query(int L,int R,int l,int r,int k){
	if(l==r) return l;
	int mid=l+r>>1,lk=a[a[R].ls].w-a[a[L].ls].w;
	if(lk>=k) return query(a[L].ls,a[R].ls,l,mid,k);
	else return query(a[L].rs,a[R].rs,mid+1,r,k-lk);
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,q;cin>>n>>q;
	V<int>a(n+1),b,c(n+1);
	for(int i=1;i<=n;i++)cin>>a[i];
	b=a;
	sort(b.begin()+1,b.end());
	int nn=unique(b.begin()+1,b.end())-b.begin()-1;
	for(int i=1;i<=n;i++) c[i]=lower_bound(b.begin()+1,b.begin()+1+nn,a[i])-b.begin();//数据过大，要离散化
	build(root[0],1,nn);
	for(int i=1;i<=n;i++) root[i]=update(c[i],root[i-1],1,nn,1);
	while(q--){
		int l,r,k;cin>>l>>r>>k;
		cout<<b[query(root[l-1],root[r],1,nn,k)]<<"\n";
	}
	return 0;
}

如果你不是很理解上面的代码，可以自己用AI去问，也可以学习其他常熟更为优秀的代码。

好了，你已经学会了主席树了，现在要给你上点强度了

放心，很简单的。

例题

看过题了，想想怎么打？

暴力：这肯定会

\color{navy}{\text{TLE}}

那我们就直接想怎么用主席树。

怎么想到用主席树的呢？因为这是一道十分经典的二维偏序问题。

什么是二维偏序？

你可以大致理解为对于同一个变量

i

，它同时满足两种形如

i \le b

或

a_i \le d

的不等关系，它就可以说具有二维偏序关系。

那为什么可以用主席树做？

因为主席树可以看作在一个平面直角坐标系上（这个坐标系以数组下边为

x

轴，以数组值域为

y

轴），维护一个一个离散的数点，然后查询操作，就相当于询问一个

(a,c)

为左下角，

(b,d)

为右上角的矩形所覆盖的点数。

所以我们看到一些偏序关系，就可以想到是否可以使用主席树进行维护。

练习

当然，题目有时候并不会直接给出明显的偏序关系，但是会通过一些性质来推导出偏序关系。

例如下面这道

P3899 [湖南集训] 更为厉害

当做课后练习，已经给出提示，推导偏序关系。

还有一些课后练习，自己想做就做，我给出一点思路

P3567 [POI 2014] KUR-Couriers，思考绝对众数与序列长度的关系，二分。

P1383 高级打字机，为什么叫“可持久化”呢，小朋友？

后记

2025.10.17 updated ，修改了一些笔误,thx一个喜欢打aqtw的人。

2025.10.18 updated ，增加了“前置芝士：二分”，原因是怕有些人不明白为什么要用权值线段树，不清楚主席树最初满足的需求。

浅尝主席树

文章操作