主席树入门浅谈
程序员文章站
2024-02-13 23:13:40
...
前言
前因:朋友推给我一个主席树算法变种题,由于板子有改动就不会了,所以得出结论,算法没吃透精髓,然后白学。因此写了一篇博客
写博客的原因有:
1:以前自己假装懂了算法,会用板子,但是发现这样的习惯不好,必须得养成手撸算法的习惯,算法模型才是真正的吃透。(个人经验所得吧)
2:写这篇博客当然主要方便自己以后复习,有一些遗忘的时候,可以回头来瞧瞧。
如果不能理解得话,请多见谅
———————————————————————————————————————
主席树
主席树 全称 可持久化线段树
作用:可持久化维护区间权值和
白话:维护某一段时间内的线段树
可持久线段树一定程度上优化了空间——
普通线段树可以满足可持久,但是需要n个线段树
给定一个数组
模拟主席树模型
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);
}
}