欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

主席树入门浅谈

程序员文章站 2024-02-13 23:13:40
...

前言

前因:朋友推给我一个主席树算法变种题,由于板子有改动就不会了,所以得出结论,算法没吃透精髓,然后白学。因此写了一篇博客
写博客的原因有:
1:以前自己假装懂了算法,会用板子,但是发现这样的习惯不好,必须得养成手撸算法的习惯,算法模型才是真正的吃透。(个人经验所得吧)
2:写这篇博客当然主要方便自己以后复习,有一些遗忘的时候,可以回头来瞧瞧。

如果不能理解得话,请多见谅
———————————————————————————————————————

主席树

主席树 全称 可持久化线段树
作用:可持久化维护区间权值和
白话:维护某一段时间内的线段树

可持久线段树一定程度上优化了空间——O(nlogn)O(nlogn)
普通线段树可以满足可持久,但是需要n个线段树

给定一个数组[2,3,1,3][2,3,1,3]
模拟主席树模型
主席树入门浅谈

pos=1

主席树模型
主席树入门浅谈
普通线段树模型
主席树入门浅谈

pos=2

主席树模型

主席树入门浅谈
普通线段树模型
主席树入门浅谈

pos=3

主席树模型
主席树入门浅谈
普通线段树模型
主席树入门浅谈

pos=4

主席树模型

主席树入门浅谈
普通线段树模型

主席树入门浅谈

运用

其次就是模型的运用
例题:
1:区间内k大的数(入门题
2:区间内小于等于k的个数
3:区间内不同数的个数
4:区间内点权k大的个数

修改的板子

查询函数不写的原因,每个题要求不一样,写的也就不一样。

const int N=5e5+5;
namespace zhuxi
{
    struct node
    {
        int left,right,value;
    }s[N*40];
    int cnt=0,root[N];
    void modify(int l,int r,int pre,int &now,int value)
    {
        s[++cnt]=s[pre];
        now=cnt;
        s[cnt].value++;
        if(l==r)
            return ;
        int mid=(l+r)>>1;
        if(value<=mid)
            modify(l,mid,s[pre].left,s[now].left,value);
        else
            modify(mid+1,r,s[pre].right,s[now].right,value);
    }
}