树状数组套trie 模板

求区间排名，第K大，单点修改，区间前驱，区间后驱。

时间复杂度O(logn^3)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define BASE (int)1e8

#define MAXN 50010

#define MAXNLOG 28

const int MAXNNODE=MAXN*16*MAXNLOG+MAXN;

int n,m,a[MAXNNODE];

namespace trie

{

    int ch[MAXNNODE][2],siz[MAXNNODE],id=MAXN;

    inline int lowbit(int x){return x&-x;}

    inline int insert(int pos,int val,int d=1)

    {

        val+=BASE;

        bool v;

        for(int i=MAXNLOG-1;~i;i--)

        {

            v=(val>>i)&1;

            if(!ch[pos][v]) ch[pos][v]=++id;

            pos=ch[pos][v];

            siz[pos]+=d;

        }

    }

    inline int nlt(int pos,int val)

    {

        val+=BASE;

        int ans=0; bool v;

        for(int i=MAXNLOG-1;~i;i--)

        {

            v=(val>>i)&1;

            if(v) ans+=siz[ch[pos][0]];

            pos=ch[pos][v];

        }

        return ans;

    }

    inline int add(int pos,int val,int d=1)

    {

        for(;pos<=n;pos+=lowbit(pos))

            insert(pos,val,d);

    }

    inline int query(int pos,int val)

    {

        int ans=0;

        for(;pos>=1;pos-=lowbit(pos)) ans+=nlt(pos,val);

        return ans;

    }

    inline int rnk(int l,int r,int k){return query(r,k)-query(l-1,k)+1;}

    inline int kth(int l,int r,int k)

    {

        int ll=-BASE-1,rr=BASE;

        while(ll<rr)

        {

            int mid=(ll+rr)>>1;

            if(rnk(l,r,mid)>k) rr=mid;

            else ll=mid+1;

        }

        return ll-1;

    }

}

using namespace std;

using namespace trie;

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]),trie::add(i,a[i]);

    for(int i=1;i<=m;i++)

    {

        int cur,l,r,x;

        scanf("%d",&cur);

        if(cur==1) scanf("%d%d%d",&l,&r,&x),printf("%d\n",trie::rnk(l,r,x));

        else if(cur==2) scanf("%d%d%d",&l,&r,&x),printf("%d\n",trie::kth(l,r,x));

        else if(cur==3) scanf("%d%d",&l,&x),trie::add(l,a[l],-1),a[l]=x,trie::add(l,x);

        else if(cur==4) scanf("%d%d%d",&l,&r,&x),printf("%d\n",trie::kth(l,r,rnk(l,r,x)-1));

        else if(cur==5) scanf("%d%d%d",&l,&r,&x),printf("%d\n",trie::kth(l,r,rnk(l,r,x+1)));

    }

    return 0;

}