主席树和可持久化线段树有什么区别?

一、主席树和可持久化线段树

主席树和可持久化线段树没有区别。主席树学名为可持久化线段树，可以用来解决线段树存储历史状态的问题。我们在进行单点修改后，线段树只有一条链节点被修改，可以让修改后的树与修改前的树共享节点，节省时间空间。

应用：

查找一个区间的第k大的值；

查询某个数的排名；

查询整个数组的排序；

查询前驱和后继。

单点修改

void update(int node,int start,int end,int pos){

    if(start==end) tr[node]++;

    else{

        int mid=start+end>>1;

        if(pos<=mid) update(node<<1,start,mid,pos);

        else update(node<<1|1,mid+1,end,pos);

    }

}//tr[i]表示值为i的元素个数,pos是要查找的位置

查询区间中的数出现次数

int query(int node,int start,int end,int ql,int qr){

    if(start==ql&&end==qr) return tr[node];

    int mid=start+end>>1;

    if(qr<=mid) return query(node<<1,start,mid,ql,qr);

    else if(ql>mid) return query(node<<1|1,mid+1,end,ql,qr);

    else return query(node<<1,start,mid,ql,qr)+query(node<<1|1,mid+1,end,ql,qr);

}//对单点查询同样适用

查询所有数的第k大值

int kth(int node,int start,int end,int k){

    if(start==end) return start;

    int mid=start+end>>1;

    int s1=tr[node<<1],s2=tree[node<<1|1];

    if(k<=s2) return kth(node<<2|1,mid+1,end,k);

    else return kth(node<<1,start,mid,k-s2);

} //注意是第k大，从右边开始减，如果是第k小就减去左边

查询前驱(后继同）

int findpre(int node,int start,int end){ //找这个区间目前最大的

    if(start==end) return start; //找到直接返回

    int mid=start+end>>1;

    if(t[node<<1|1]) return findpre(node<<1|1,mid+1,end);

    return findpre(node<<1,start,mid);

}

int pre(int node,int l,int r,int pos){ //求pos的前驱

    if(r

        if(t[node]) return findpre(node,l,r);

        return 0;

    }

    int mid=l+r>>1,res;

    if(mid+1

    return pre(node<<1,l,mid,pos);  //在左区间寻找

}

延伸阅读：

二、权值线段树

线段树的叶子节点保存的是当前值的个数。

每个节点保存区间左右端点以及所在区间节点的个数。

由于值域范围通常较大，一般会配合离散化或动态开点等策略优化空间。