主席树和数据离散化|笔记

给一个数列,询问某区间内第k小

本文大量参考MenCi的笔记

权值线段树

将数据作为标号,数据在数列中出现的次数作为权值,得到一组新数据.对该数据建立线段树.

显然可以在该权值线段树上查找第k小:

若k小于等于左子树权值,对左子树查找第k小
若k大于左子树权值,对右字数查找第k - val(left_son)小

如果数据极分散,将浪费大量空间.考虑离散化

数据离散化

设原始数据arr.建立一个备份set_

对set_先后进行排序,去重,将数据有序化

对arr中每个元素,查找在set中的位置,完成离散

//discrete
        memcpy(set_,arr,(n + 1) * sizeof(int));
        sort(set_ + 1,set_ + 1 + n);
        int *set_end = unique(set_ + 1,set_ + 1 + n);
        for (int i = 1;i <= n;++ i)
                arr[i] = lower_bound(set_ + 1,set_end,arr[i]) - set_;

主席树

主席树是包含多个历史版本的线段树.因此每颗线段树形态完全相同

当一颗线段树发生改变时,改变节点到根节点的路径全部复制一遍.查询时从第t个根节点查询得到的就是第t版本的线段树

前缀和

注意到本题如果对所有区间[l,r]都增加一个树版本,共耗费时间将为O(n^2 * logn)

事实上查找第k大所需的信息只是某区间的元素数量(某结点的权值),注意到区间元素数量可以由前缀和维护.

事实上由于每颗树形态相同,整个主席树都可以由前缀和维护.版本[l,r]的树实为树[0,r] - 树[0,l - 1]

总复杂度降为O(nlogn)

完整代码如下:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define llint long long
using namespace std;
int arr[400000];
struct node{
        node *lson,*rson;
        int l,r,val;
        node(int ql,int qr){
                // build a void tree
                l = ql;r = qr;
                val = 0;
                if(ql == qr){
                        lson = rson = NULL;
                }
                else{
                        int mid = ((r - l) >> 1) + l;
                        lson = new node(ql,mid);
                        rson = new node(mid + 1,qr);
                }
        }
        node(node *ori,node *ls,node *rs){
                lson = ls;rson = rs;
                l = ori->l;r = ori->r;val = ori->val + 1;
        }

        void maintain(){
                val = lson->val + rson->val;
                return ;
        }
        node* insert(int ival){
                int mid = ((r - l) >> 1) + l;
                if (ival == l && ival == r)
                        return new node(this,NULL,NULL);
                if (ival <= mid)
                        return new node(this,lson->insert(ival),rson);
                else 
                        return new node(this,lson,rson->insert(ival));
        }

}*roots[4000000];
int query(node *ql,node *qr,int k){
        if(ql->l == ql->r)
                return qr->l;
        int lval = qr->lson->val - ql->lson->val;
        if (k <= lval)
                return query(ql->lson,qr->lson,k);
        else
                return query(ql->rson,qr->rson,k - lval);
}
int main (){
        int m,n;
        static int set_[400000];
        cin >> n >> m;
        arr[0] = -0x7fffffff;
        for (int i = 1;i <= n;++ i)
                scanf("%d",&arr[i]);
        //discrete
        memcpy(set_,arr,(n + 1) * sizeof(int));
        sort(set_ + 1,set_ + 1 + n);
        int *set_end = unique(set_ + 1,set_ + 1 + n);
        for (int i = 1;i <= n;++ i)
                arr[i] = lower_bound(set_ + 1,set_end,arr[i]) - set_;
        //build trees
        int size_ = set_end - set_ - 1;
        roots[0] = new node(1,size_);
        for (int i = 1;i <= n;++ i)
                roots[i] = roots[i - 1]->insert(arr[i]);
        //query
        int beg,end,k;
        for (int i = 1;i <= m;++ i){
                scanf("%d%d%d",&beg,&end,&k);
                printf("%d\n",set_[query(roots[beg - 1],roots[end],k)]);

        }
        return 0;
}

以上.