概念
指线段树的结点管辖的不是一段下标，而是一段值域。
通俗点讲，就是，
线段树的每个结点是用来维护一段区间的最大值或总和；
而权值线段树的每个结点储存的一段区间有多少个数；
作用
权值线段树主要用来求区间第 kk 大值或区间第 kk 小值。
例题① —— P1637 三元上升子序列
题目大意
在 a 数组中统计满足 i<j<k 且 a_i<a_j<a_k 的三元组 {i,j,k} 的数量（1≤i,j,k≤n）。
暴力100分思路
两重循环枚举，第一层枚举中心点 j，第二次循环从 1 扫到中心点前求 i 可能的数量，再第二层循环从中心点后扫到 n，求 k 可能的数量，最后将它们相乘。
暴力100分代码（拒绝抄袭，已将所有代码加入防抄袭）
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int ans=0;
for(int i=1;i<=n;i++)
{
int cnt1=0, cnt2=0;
for(int j=1;j<i;j++)
{
if(a[j]<a[i])
{
cnt1++;
}
}
for(int j=i+1;j<=n;j++)
{
if(a[i]<a[j])
{
cnt2++;
}
}
ans+=cnt1*cnt2;
}
cout<<ans;
return 1;
}权值线段树优化
刚刚的暴力写法建立在题目不卡常的情况下，若题目卡常就寄了。这时我们可以用权值线段树优化时间复杂度。
从 1 到 50000 建一棵权值线段树，每次询问先前有多少个点 id 大于当前点并且已入线段树，最后在把对应权值处在线段树上 +1。
注意：
要统计两次分别是 i 和 k。
统计完第一次后要重新建树。
代码（已加防抄袭）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N], n, m, tag[4*N], tree[4*N];
int cnt1[400005], cnt2[400005];
void pushup(int cur)
{
tree[cur]=tree[cur*2]+tree[cur*2+1];
return ;
}
void addtag(int cur, int lt, int rt, int val)
{
tag[cur]+=val;
tree[cur]+=(rt-lt+1)*val;
return ;
}
void pushdown(int cur, int lt, int rt)
{
if(tag[cur]==0)
{
return ;
}
int mid=lt+rt>>1;
addtag(cur*2,lt,mid,tag[cur]);
addtag(cur*2+1,mid+1,rt,tag[cur]);
tag[cur]=0;
return ;
}
void build(int cur, int lt, int rt)
{
if(lt==rt)
{
tree[cur]=0;
return ;
}
int mid=lt+rt>>1;
build(cur*2,lt,mid);
build(cur*2+1,mid+1,rt);
pushup(cur);
return ;
}
int query(int cur, int lt, int rt, int qx, int qy)
{
if(qy<lt||qx>rt)
{
return 0;
}
if(qx<=lt&&rt<=qy)
{
return tree[cur];
}
pushdown(cur,lt,rt);
int mid=lt+rt>>1;
return query(cur*2,lt,mid,qx,qy)+query(cur*2+1,mid+1,rt,qx,qy);
}
void update(int cur, int lt, int rt, int qx, int qy, int val)
{
if(qy<lt||qx>rt)
{
return ;
}
if(qx<=lt&&rt<=qy)
{
addtag(cur,lt,rt,val);
return ;
}
pushdown(cur,lt,rt);
int mid=lt+rt>>1;
update(cur*2,lt,mid,qx,qy,val);
update(cur*2+1,mid+1,rt,qx,qy,val);
pushup(cur);
return ;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,1e5);
for(int i=1;i<=n;i++)
{
cnt1[i]=query(1,1,1e5,1,a[i]-1);
update(1,1,1e5,a[i],a[i],1);
}
build(1,1,1e5);
int ans=0;
for(int i=n;i>=1;i--)
{
cnt2[i]=query(1,1,1e5,a[i]+1,1e5);
update(1,1,1e5,a[i],a[i],1);
ans+=cnt1[i]*cnt2[i];
}
cout<<ans;
return 0;
}例题②—— P1908 逆序对
题目大意
求 a 数组中 a_i>a_j 且 i<j 的二元组 {i,j}。
权值线段树解法
就不写暴力了，快速进入正题。
这题跟上题很相似，唯一不同的两点是本题建树只建一次和要从小到大排序。
代码（加防抄袭）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
struct node
{
int v, id;
}a[N];
int n, m, tag[4*N], tree[4*N];
int cnt1[400005], cnt2[400005];
bool cmp(node x, node y)
{
if(x.v==y.v)
{
return x.id<y.id;
}
return x.v<y.v;
}
void pushup(int cur)
{
tree[cur]=tree[cur*2]+tree[cur*2+1];
return ;
}
void addtag(int cur, int lt, int rt, int val)
{
tag[cur]+=val;
tree[cur]+=(rt-lt+1)*val;
return ;
}
void pushdown(int cur, int lt, int rt)
{
if(tag[cur]==0)
{
return ;
}
int mid=lt+rt>>1;
addtag(cur*2,lt,mid,tag[cur]);
addtag(cur*2+1,mid+1,rt,tag[cur]);
tag[cur]=0;
return ;
}
void build(int cur, int lt, int rt)
{
if(lt==rt)
{
tree[cur]=0;
return ;
}
int mid=lt+rt>>1;
build(cur*2,lt,mid);
build(cur*2+1,mid+1,rt);
pushup(cur);
return ;
}
int query(int cur, int lt, int rt, int qx, int qy)
{
if(qy<lt||qx>rt)
{
return 0;
}
if(qx<=lt&&rt<=qy)
{
return tree[cur];
}
pushdown(cur,lt,rt);
int mid=lt+rt>>1;
return query(cur*2,lt,mid,qx,qy)+query(cur*2+1,mid+1,rt,qx,qy);
}
void update(int cur, int lt, int rt, int qx, int qy, int val)
{
if(qy<lt||qx>rt)
{
return ;
}
if(qx<=lt&&rt<=qy)
{
addtag(cur,lt,rt,val);
return ;
}
pushdown(cur,lt,rt);
int mid=lt+rt>>1;
update(cur*2,lt,mid,qx,qy,val);
update(cur*2+1,mid+1,rt,qx,qy,val);
pushup(cur);
return ;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].v;
a[i].id=i;
}
sort(a+1,a+1+n,cmp);
build(1,1,5e5);
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=query(1,1,5e5,a[i].id+1,5e5);
update(1,1,5e5,a[i].id,a[i].id,1);
}
cout<<ans;
return 0;
}