权值线段树

数据结构

发布日期: 2020-05-05

~~兴致冲冲的去学主席树(lll￢ω￢)才发现好多前置技能都没学~~

~~甚至学了这么久线段树才知道还有一个权值线段树~~

权值线段树每个节点保存当前节点值出现的次数，相当于一个桶，权值线段树可以查询一个数出现的次数、一段区间数出现的次数、第K大/小值、查询某个数的排名、前驱和后继，但由于数据通常很大，经常要用到离散化处理，~~感觉比正常线段树要简单，其他的东西我这个萌新就不多赘述~~

例题

~~随便贴个逆序对例题，另外，树状数组真香~~

HDU1394

const int maxx = 5005;
int tree[maxx<<2];
int a[maxx];
void update(int root,int l,int r,int pos){
    if (l==r){
        tree[root]++;
        return;
    }
    int mid=(l+r)>>1;
    if (pos<=mid){
        update(root<<1,l,mid,pos);
    }else {
        update(root<<1|1,mid+1,r,pos);
    }
    tree[root]=tree[root<<1]+tree[root<<1|1];
}
int query(int root,int l,int r,int ql,int qr){
    if (ql<=l && r<=qr){
        return tree[root];
    }
    int mid=(l+r)>>1;
    if (qr<=mid){
        return query(root<<1,l,mid,ql,qr);
    }else if (ql>mid){
        return query(root<<1|1,mid+1,r,ql,qr);
    }else {
        return query(root<<1,l,mid,ql,qr)+query(root<<1|1,mid+1,r,ql,qr);
    }
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        int ans=0;
        memset(tree,0,sizeof(tree));
        for (int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            a[i]++;
            ans+=query(1,1,n,a[i],n);
            update(1,1,n,a[i]);
        }
        int minn=ans;
        for (int i=1;i<=n;i++){
            ans=ans+(n-a[i]+1)-a[i];
            minn=min(ans,minn);
        }
        printf("%d\n",minn);
    }
}

~~此题水的暴力也能过~~

动态开点

普通线段树一般要开四倍的空间，当数据过大时内存肯定不够，因为普通线段树很多节点我们根本用不上，所以当我们需要的时候再去开个节点，用多少开多少，只需要多开两个数组存储每个节点左儿子和右儿子的root，当前需要的节点没有开的时候按顺序一个个开就好了，~~其他和普通线段树如出一辙，本萌新也不赘述~~

例题

~~再随便贴个逆序对,此题方法很多~~

CF 1042D

动态开点+权值线段树

#define ll long long
const int N=1e7+50;
const ll inf=2e14;
int n,m;
ll t,sum,ans=0;
int rt,ls[N],rs[N],num[N],cnt;

void update(int &p,ll l,ll r,ll pos){
    if(!p) p=++cnt;
    num[p]++;
    if(l==r) return;
    ll mid=(l+r)>>1;
    if(pos<=mid) update(ls[p],l,mid,pos);
    else update(rs[p],mid+1,r,pos);
}

int query(int p,ll l,ll r,ll L,ll R){
    if(!p) return 0;
    if(L<=l&&r<=R) return num[p];
    int res=0;
    ll mid=(l+r)>>1;
    if(L<=mid) res+=query(ls[p],l,mid,L,R);
    if(R>mid) res+=query(rs[p],mid+1,r,L,R);
    return res;
}

int main(){
    scanf("%d%lld",&n,&t);
    update(rt,-inf,inf,0);
    for(int i=1;i<=n;++i){
        scanf("%d",&m);
        sum+=m;
        ans+=query(rt,-inf,inf,sum-t+1,inf);
        update(rt,-inf,inf,sum);
    }
    printf("%lld\n",ans);
}

离散化+权值线段树

#define ll long long
#define rep(i,be,en) for (ll i=be;i<=en;i++)
const int N=2e5+50;
ll t,n,m,k,fl=0;
ll lisan[N<<1];     //用来离散的存离散后的结果数组
ll s[N];        //用来存原始状态
ll tree[N<<3];
void update(ll root,ll l,ll r,ll pos){
    if (l==r){
        tree[root]++;
        return;
    }
    ll mid=(l+r)>>1;
    if (pos<=mid){
        update(root<<1,l,mid,pos);
    }else {
        update(root<<1|1,mid+1,r,pos);
    }
    tree[root]=tree[root<<1]+tree[root<<1|1];
}
ll query(ll root,ll l,ll r,ll ql,ll qr){
    if (ql<=l && r<=qr){
        return tree[root];
    }
    ll mid=(l+r)>>1;
    if (qr<=mid){
        return query(root<<1,l,mid,ql,qr);
    }else if (ql>mid){
        return query(root<<1|1,mid+1,r,ql,qr);
    }else {
        return query(root<<1,l,mid,ql,qr)+query(root<<1|1,mid+1,r,ql,qr);
    }
}
int main() {
    ll ans=0,cnt=0;
    scanf("%lld%lld",&n,&t);
    lisan[++cnt]=0;
    rep(i,1,n){
        scanf("%lld",&s[i]);
        s[i]+=s[i-1];
        lisan[++cnt]=s[i];
        lisan[++cnt]=s[i]-t;
    }
    sort(lisan+1,lisan+cnt+1);
    ll len=unique(lisan+1,lisan+cnt+1)-lisan-1;
    update(1,1,len,lower_bound(lisan+1,lisan+len+1,0)-lisan);
    for(ll i=1;i<=n;i++){
        ll x=lower_bound(lisan+1,lisan+len+1,s[i])-lisan;
        ll y=lower_bound(lisan+1,lisan+len+1,s[i]-t)-lisan;
        ans+=i-query(1,1,len,1,y);
        update(1,1,len,x);
    }
    printf("%lld\n",ans);
    return 0;
}

离散化+树状数组 ~~树状数组真香~~

#define ll long long
#define lowbit(x) x&-x
const int N=2e5+5;
ll c[N],ls[N],s[N],t,ans=0;
ll n;
void update(ll i,ll x){
    while(i<=n){
        c[i]+=x;
        i+=lowbit(i);
    }
}
ll sum(ll i){
    ll ss=0;
    while(i){
        ss+=c[i];
        i-=lowbit(i);
    }
    return ss;
}
int main(){
    scanf("%lld%lld",&n,&t);
    for(ll i=1;i<=n;i++){
        scanf("%lld",&s[i]);
        s[i]+=s[i-1];
        ls[i]=s[i];
        if(s[i]<t) ans++;
    }
    sort(ls+1,ls+n+1);
    ll len=unique(ls+1,ls+n+1)-ls-1;
    for(ll i=1;i<=n;i++){
        ll x=upper_bound(ls+1,ls+len+1,s[i]-t)-ls;
        ans+=i-sum(x-1)-1;
        x=lower_bound(ls+1,ls+len+1,s[i])-ls;
        update(x,1ll);
    }
    printf("%lld\n",ans);
}