权值线段树 Weighted segment tree

概念

指线段树的结点管辖的不是一段下标，而是一段值域。

通俗点讲，就是，

线段树的每个结点是用来维护一段区间的最大值或总和；

而权值线段树的每个结点储存的一段区间有多少个数；

作用

权值线段树主要用来求区间第 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;
}