二叉堆
目的：快速获得队列中最大的，STL打法解决问题
基本功能
- 在O（logN）插入元素
- 在O(1)中访问堆顶元素
- 在O(logN)删除最大
- 在O（logN）删除任意元素
结构
- 最为常用的对结构，本质是完全二叉堆，高度为 log（n）
- STL中有Priority Queue快速实现
- 有序性，爸爸都比孩子大
- n节点的左右孩子分别为2n、2n+1
操作
- 查询： 最大或最小值从堆顶返回，O（1）
- 插入（上浮）： 先插入队尾，与前n/2的元素（父节点）比较，最差不过O(log N)
- 建堆： 直接按照数组顺序读入（不需要按次），之后从倒数第二行开始（n/2节点处） 向自己的子节点尝试下移，如果下移成功，子节点需要继续向上判断，最差最高根节点
- 删除堆中元素：最优方法O（n）：新建labor堆，标记已经删去的元素->目的：不破坏原来的堆结构。当查询的时候顺便修复
- 删除堆顶元素（下沉）：先与末尾元素交换，再由堆顶向下交换
本蒟蒻还不会正经二叉堆，所以优先队列搞起来~
优先队列
priorityQueue ，STL拯救我
特征：自动排序，赛高！解决我不会二叉树的最简单方法
文章部分摘自https://blog.csdn.net/c20182030/article/details/70757660
- 初始化1：
priority_queue <int> i;
priority_queue <double> d;
- 初始化2：
priority_queue<vector<int>, less<int> > pq1;
priority_queue<deque<int>, greater<int> > pq2;
注意：除了使用less<>，greater<>其他的默认大的在前
- 初始化三：
struct node(){
};
bool cmp(node x,node y){
return ...<....;
}
priority_queue <node,vector<node>，cmp>q;
- 初始化三：
struct node {
int x, y;
friend bool operator < (node a, node b)
{
return a.x > b.x; //结构体中，x小的优先级高
}
};
priority_queue<node>q;
- API：
q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
q.back();//返回q的末尾元素
简单的使用：
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int> q;
int main(){
int n,tmp;
cin >> n;
for(int i=1;i<=n;i++){
cin >> tmp;
q.push(tmp);
}
while(!q.empty()){
tmp=q.top();
q.pop();
cout << tmp << endl;
}
}
线段树
今日攻占的核心中的核心！！
用途：查找连续的区间的时候的快速骚操作
基本功能：
1、建树
2、单点查询
3、单点修改
4、区间查询
5、区间修改
结构：
1、线段树是一棵二叉搜索树，储存区间信息
2、每个断点要维护：
· 区间左端点和右端点
· 题目所需要的信息
3、基本思想：二分
4、特殊性质：左孩子范围为[l,mid],右端为[mid+1,r]
对于借点k，左孩子为2k，右孩子2k+1
模板代码（QWQ不会用）：
#include<iostream>
#include<cstdio>
#define maxn 1000000
using namespace std;
int a[maxn],min[4*maxn],n;
//建树操作
void build(int pos,int l,int r){ //pos当前节点编号、l，r代表当前节点所代表区间
if(l==r){
min[pos]=a[pos];
return;
}
int mid=(l+r)>>1;
build(k*2,l,mid);
build(k*2+1,mid);
min[pos]=min(mi[k*2],min[k*2+1]);
}
//区间问询操作
int query_min(int pos,int l,int r,int x,int y){ //pos当前节点位置，l，r当前节点左右，x，y查询节点区间
if(x<l||x>r) return 9999999; //返回极大值代表无信息
if(x<=1&&r<=y) return min[k];
int mid=(l+r)>>1;
return min(query_min(k*2,l,mid,x,y),query_min(k*2+1,mid+1,r,x,y));
}
// 单点修改操作
void change(int pos,int l,int r,int x,int v){ //pos当前节点，l，r当前节点维护的区间，x为原序列中的值，v为要改成的值
if(r<x||l>x) return;
if(l==r&&l==x){
min[k]=v;
return;
}
int mid=(l+r)>>1;
change(pos*2+1,mid+1,r,x,v);
change(pos*2,l,mid,x,v);
min[pos]=min(min[k*2],min[k*2+1]);
}
套用模板查询范围内
#include<cstdio>
#include<algorithm>
#define maxn 100000
#define ll long long
using namespace std;
inline int read(){ //读入优化
int res=0,f=1; //res顾名思义结果 ，f用来判断正负
char ch;
while(ch<'0'||ch>'9'){ //读入前面的空格以及负号
if(ch=='-') f=-1; //如果是负号则f变-1
ch=getchar(); //连续读入，在最后读入负号之后也能再读入一位数字为下面的语句做帮助
}
while(ch>='0'&&ch<='9'){ //连续读入数字
res=res*10+ch-'0'; //更新答案
ch=getchar();
}
return res*f; //返回
}
int n,m;
ll sum[maxn*4];
void change(int k,int l,int r,int p,int v){ //修改pos=k的点，l，r为这个点的左右区间，p为这个点在原序列中的位置，v代表要修改成的值
if(r<p||l>p) return;
if(l==r&&p==l){
sum[k]+=v;
return;
}
int mid=(l+r)>>1;
change(k*2,l,mid,p,v);
change(k*2+1,mid+1,r,p,v);
sum[k]=sum[k*2]+sum[k*2+1];
}
long long query(int k,int l,int r,int x,int y){ //查询k节点，这个节点的左边是l，右边是r，查询区间x-y
if(y<l||x>r) return 0;
if(l>=x&&r<=y) return sum[k];
int mid=(l+r)>>1;
long long res=0;
res = query(k*2,l,mid,x,y);
res += query(k*2+1,mid+1,r,x,y);
return res;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int k=read(),l=read(),r=read(); //k==1表示求区间和，k==0 表示a[l]+r(a[l])是虚拟的目前来看
if(k==0) change(k,k,n,l,r);
else printf("%lld\n",query(1,l,n,l,r));
}
}
Lazy标记回头再说吧。。目前太菜没有深度理解的机会
标记永久化
。。。今天不想写了，去luogu练基础，明天再说吧。
树状数组
用途：快速获取区间和
基本思想：
根据任意的正整数关于2的不重复次幂的唯一分解性质，通过二进制中的最后一位来决定保存前缀的长度，将其分解成为多个子区间，分而治之
通过另外的数组 c[] 来保存已经运算好的值
功能：
1 查找前缀和
2 进行加法操作（看题）
3 更新操作
代码（单点修改）：
#include<iostream>
#define maxn 10000
#define ll long long // 学到新姿势
using namespace std;
int a[maxn],c[maxn],n;
int lowbit(int x){ //返回x的最小次幂
return x&(-x); //背会就好了--返回的是x可被2分解的最小数
}
void add(int pos,int y){ //在pos上增加y
for(int i=pos;i<=n;i+=lowbit(i)) c[i]+=y; // 一定要 += lowbitx（）
}
ll sum(int pos){ // 求pos上的前缀sum
ll sum=0;
for(int i=pos;i>0;i-=lowbit(i)) // 一个
sum+=c[i];
return sum;
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
add(i,a[i]);
}
cout << sum(n);
return 0;
}
区间修改：
不会。。。。。。太菜了
并查集
用途：如名字一般，只有并和查的功能！！
强（缸 手动滑稽）烈推荐：https://blog.csdn.net/u013546077/article/details/64509038
原理：
找爸爸法：
开一个数组把爸爸们记录下来
优化方法：
在每一次插入之前，如果连接的不是根，则插入到根上
代码：
#include<iostream>
#define maxn 1e6
using namespace std;
int pre[(int)maxn],n; //pre存的是某位的爸爸
int find(int x){ //找爸爸
while(pre[x]!=x) x=pre[x];
return x;
}
void join(int x,int y){ //让x的爸爸认y的爸爸做儿子
int fx=find(x),fy=find(y);
if(fx!=fy);
pre[fx]=fy;
}
int main(){
cin >> n;
int tp,rpm;
for(int i=1;i<=n;i++) {
cin >> tp >> rpm;
pre[tp]=rpm;
}
}
RMQ问题
RMQ问题是指求区间最值的问题，RMQ (Range Minimum/Maximum Query)
ST表法：
ST算法是一种更加高效的算法，基于动态规划的思想，以O(nlogn)的预处理代价，换取O(1)的查询时性能。
动态规划方程：f[i , j] = max（f[i , j-1]，f[ i + 2^(j-1), j-1]）
f[i, 0] = a[i]
代码：
#include<iostream>
#include<cmath>
#define maxn 111100
#define logN 25
//因为cmath中的log函数效率差，不如直接设定一个永远到不了的值
using namespace std;
int f[maxn][logN],a[maxn],n,m;
void pre_st(){ //制表
for(int i=1;i<=n;i++)
f[i][0]=a[i]; //因为第二个框框中存的j是用来计算 i+2^j-1（既该f保存的值）
//服务于动态规划的结果
for(int j=1;j<=logN;j++){
for(int i=1;i+(i+(1<<j)-1)<=n;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]); //注释1 （1<<j）是计算出 2^j 把一一直右移即可得到
//注释2 使用刚才得到的动态规划方程
}
}
int main(){
cin >> n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
pre_st(); //制表
cin >> m;
int x,y;
for(int i=1;i<=m;i++){
cin >> x >> y;
int s=log(y-x+1)/log(2); //计算出这一段距离之中最大的2的倍数，以查表
cout << max(f[x][s],f[y-(1<<s)+1][s]) << endl;; //合并左右不分的解
}
return 0;
}
倍增法：
蒟蒻的我还不会，10月4日讲了再说
LCA：
全称：Least Common Ancestors 最近公共祖先
思路1：
给定[L，R]通过dfs，记录遍历结果到R为值，找到从[L,R]中深度最低的点就是最近公共祖先，使用ST表完成O（1）时间内的查询
代码：
尴尬了。。。忘了怎么存图了，10月4日讲完图的存储之后再说！（嘻嘻）