首页 > 其他分享 >基础数据结构

基础数据结构

时间：2023-06-22 17:34:40浏览次数：45  
标签：cur int void 基础 mid mathcal inline 数据结构

基础数据结构

\(\mathcal{Part}\) 1. 链表

大家应该比较熟，直接说特点啦

  • 可以 \(\mathcal{O}(1)\) 查询后继
  • \(\mathcal{O}(n)\) 查询元素
  • \(\mathcal{O}(1)\) 插入和删除元素

至于 STL 的话，感觉不怎么好用，而且手写更方便（又不是什么很难得东西

  • 应用1

链式前向星，应该印在脑子里了吧

struct node{int to, nxt; }edge[MAXM];
int head[MAXN], e_cnt;
inline void add(int from, int to){edge[++ e_cnt].to = to, edge[e_cnt].nxt = head[from], head[from] = e_cnt; }
  • 应用2

哈希表，我得评价是不如双哈希，就不写了

\(\mathcal{Part}\) 2.二叉堆

我们现在要建立这样一个数据结构，支持

  • 插入一个数 \(x\)
  • 查询 \(\max x\)
  • 删掉 \(\max x\)，如果有多个只删除一个
  • 二叉堆

二叉堆是一个完全二叉树，分为大顶堆和小顶堆，大顶堆的根节点比他所有儿子以及孙子等要大，小根堆则同理

那么查询操作就直接输出根节点就好了

插入操作呢？

我们将 \(x\) 插入到这个堆最下面，然后以交换为基本规则，交换到符合规则，时间复杂度 \(\mathcal{O}(\log n)\)

inline void up(int x) {
    while (x > 1 && t[x] > t[x / 2]) 
        swap(t[x/2], t[x]), x /= 2;;
}

删除操作呢？

一样的，我们把根节点和最后一个节点交换，把根节点删掉，再进行下潜操作，时间复杂度 \(\mathcal{O}(\log n)\)

inline void down(int x) {
    while (x <= cnt) {
        if (x * 2 > cnt) break;
        if (x * 2 == cnt) {
            if (t[x] < t[x*2]) swap(t[x], t[x*2]);
            break;
        }
        int s = x * 2 + (t[x*2] < t[x*2+1]);
        if (t[x] < t[s]) swap(t[x], t[s]), x = s;
        else break;
    }
}

完整代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 7;

int n;

struct Tree{
    int cnt, t[MAXN];

    inline void up(int x) {
        while (x > 1 && t[x] > t[x / 2]) 
            swap(t[x/2], t[x]), x /= 2;;
    }
    inline void down(int x) {
        while (x <= cnt) {
            if (x * 2 > cnt) break;
            if (x * 2 == cnt) {
                if (t[x] < t[x*2]) swap(t[x], t[x*2]);
                break;
            }
            int s = x * 2 + (t[x*2] < t[x*2+1]);
            if (t[x] < t[s]) swap(t[x], t[s]), x = s;
            else break;
        }
    } 
    inline void add(int x) {t[++ cnt] = x; up(cnt); }
    inline int top(){return t[1]; }
    inline void pop(){t[1] = t[cnt --]; down(1); }
}t;

int main () {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1, op, x; i <= n; i ++) {
        cin >> op;
        if (op == 1) cin >> x, t.add(-x);
        else if (op == 2) cout << -t.top() << '\n';
        else if (op == 3) t.pop(); 
    }
    return 0;
}

当然，这东西有STL

  • 大根堆：priority_queue<int> Q1
  • 小根堆：priority_queue<int, vector<int>, greater<int>> Q2;
  • 对顶堆

用来查询第 \(k\) 小的数（如果你会平衡树可以不看的）

我们建立两个堆，一个大顶一个小顶堆

大顶堆存的是排名为 \([1,k)\) 的数，小根堆则存另外的数

显然，小根堆的堆顶就是答案

其次，我们要注意维护好这两个堆的大小

\(\mathcal{Part}\) 3. 并查集

  • 模板

过于简单直接上代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e4 + 7;

int n, m, fa[MAXN];

void init() {
	for (int i = 1; i <= MAXN; i ++) fa[i] = i;
}

inline int find(int x) {
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

inline void merge(int x, int y) {
	int fx = find(x), fy = find(y);
	if (fx == fy) return ;
	fa[fx] = fy;
}

inline bool check(int x, int y) {
	return find(x) == find(y);
}
  • 逆序思想

我们现在要维护删边操作，我们并不会，怎么办？

我们可以反向思考，把它变成加边操作，于是就可以解决这个问题

  • 离线思想

给定的边有边权，我们要维护边权大于等于 \(k\) 的联通块数量怎么办？

我们可以先把询问存下来，对他进行排序，同时对边权进行排序

然后一条边一条地加，最后跟询问匹配即可

  • 带权并查集

考虑维护 \(d\) 数组表示这个点到其父亲的距离

每次在 \(find\) 中更新 \(d_x=d_x+d_{f_x}\) 即可，\(merge\) 中维护

最后根据情况输出答案即可

  • 扩展域并查集

一组点可能有多钟关系，这时候，我们吧并查集空间开大几倍

比如有 \(A,B,C\) 三种关系，我们将 \(1,n\) 存 \(A\) 关系，\(n+1,2n\) 存 \(B\) 关系，\(2n+1,3n\) 存 \(C\) 关系

然后就可以维护啦

\(\mathcal{Part}\) 4.树状数组

  • 单修区查

现在，我们要自己设计一个树形数据结构，支持两种操作

  • 单点修改
  • 查找一个 \(x\) 的前缀和

这个数据结构需要有如下性质

  • 修改一个值只影响到少数区间
  • 对于任意一个前缀和的询问，可以用少数区间把询问的前缀拼出来

那树状数组是个什么东西呢？

首先上个经典的图

图

我们记 \(c_x\) 表示 \([x-lowbit(x)+1,x]\) 的区间和

那 \(lowbit\) 是啥东西呢？

表示为 lowvit(x)=x&(-x)，意思是找到最后一个一所对应的权值（注：不是位置！

现在看看原理：（lxl坚信一点用都没有）

  • 询问

我们假设要询问 \([1,x]\) 的值，我们先求出 \([x-lowbit(x)+1,x]\) 的和，即 \(c_i\)，然后递推下去，知道访问 \([1,0]\) 这个区间停止，时间复杂度为 \(\mathcal{O}(\log n)\) 的（二进制啊

#define lb(x) (x & -x)
int query(int x) {
	int ans = 0;
	for (int i = x; i; i -= lb(i)) ans += a[i];
	return ans;
}
  • 修改

我们看修改 \(x\) 的值会影响到哪些值

这里根据略微复杂的分类讨论可以得到修改 \(x\) 影响到 \(x+lowbit(x)\) 即递推下去的值，同样，时间复杂度为 \(O(\log n)\)

inline void modify(int x, int y) {
	for (int i = x; i <= n; i += lb(i)) a[i] += y;
}

变形：权值线段树

我们维护一个数轴，把添加一个值当做单点修改，查询当做区间查询即可

  • 区修单查

我们采用反演思想

我们把区间修改做个差分，就是查询后缀和

比如 \([x,y]\) 改成 \([x,n]-[y+1,n]\) 即可

现在怎么维护一个后缀修改

我们看查询，我们想要知道修改这个点 \(x\) 影响到了哪些点

显然左端点小于 \(x\) 的点，我们结合刚刚讲到的权值线段树，就有个思路

我们直接区间查询 \([1,x)\) 的修改不就行了？那修改就变成了单点修改，于是我们就会做了

这类问题例题可以去看逆序对

\(\mathcal{Part}\) 5.线段树

一样的，我们现建立一个数据结构，使它满足上面两个性质

首先上个经典的图

其中，根节点表示一整个区间，左右子节点各表示一半区间

线段树可以维护任何负有传递性的东西，但是常数较大，注意下面的函数都是 \(\mathcal{O}(\log n)\)

  • 建树，\(build\)

直接按照上述规则建树即可，注意要在最后上传信息

struct Node{int sum, lg; }t[4 * MAXN];
#define ls(i) (i << 1)
#define rs(i) (i << 1 | 1)
inline void push_up(int x) {t[x].sum = t[ls(x)].sum + t[rs(x)].sum; }

inline void build(int cur, int l, int r) {
    if (l == r) {
        t[cur].sum = a[l];
        return ;
    } 
    int mid = l + r >> 1;
    build(ls(cur), l, mid); build(rs(cur), mid + 1, r);
    push_up(cur);
}
  • 单点修改

直接找到这个点修改即可，同时也要上传信息

inline void modify(int cur, int l, int r, int x, int y) {
    if (l == r) {
        sum[cur] += y;
        return ; 
    }
    int mid = l + r >> 1;
    if (x <= mid) modify(ls(cur), l, mid, x, y);
    else modify(rs(cur), mid + 1, r, x, y);
    push_up(cur);
}
  • 区间查询

判断区间是否相交即可，注意不要用 else，有可能两个区间都有相交

inline int query(int cur, int l, int r, int x, int y) {
    if (x <= l && y >= r) return sum[cur];
    int mid = l + r >> 1, ans = 0;
    if (x <= mid) ans += query(ls(cur), l, mid, x, y);
    if (y > mid) ans += query(rs(cur), mid + 1, r, x, y);
    return ans; 
}
  • 区间修改

递归到每个子节点进行修改?

如果这么做时间复杂度为 \(\mathcal{O}(size)\)，size 为整个树的大小

有什么方法？

我们注意到只有查询才会查询这个节点的具体的值，我们于是可以将这个节点加个标记

表示我的所有儿子都要修改，但是因为我懒，我等到你查到我儿子我再把这个标记传给他

所以这叫懒惰标记，每次往下递归都要下传

inline void f(int cur, int l, int r, int k) {
    t[cur].sum += (r - l + 1) * k;
    t[cur].lg += k;
}
inline void push_down(int cur, int l, int r) {
    int mid = l + r >> 1;
    f(ls(cur), l, mid, t[cur].lg);
    f(rs(cur), mid + 1, r, t[cur].lg);
    t[cur].lg = 0;
}

区修区查完整代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAXN = 1e5 + 7;

int n, m, a[MAXN];

struct Segt_Tree{
	struct Node{int sum, lg; }t[MAXN * 4];
	
	#define ls(i) (i << 1)
	#define rs(i) (i << 1 | 1)
	inline void push_up(int x) {t[x].sum = t[ls(x)].sum + t[rs(x)].sum; }
	
	inline void build(int cur, int l, int r){
		if (l == r) {
			t[cur].sum = a[l];
			return ;
		}
		int mid = l + r >> 1;
		build(ls(cur), l, mid); build(rs(cur), mid + 1, r);
		push_up(cur);
	}
	
	inline void f(int cur, int l, int r, int k){
		t[cur].sum += (r - l + 1) * k;
		t[cur].lg += k;
	}
	inline void push_down(int cur, int l, int r) {
		int mid = l + r >> 1;
		f(ls(cur), l, mid, t[cur].lg);
		f(rs(cur), mid + 1, r, t[cur].lg);
		t[cur].lg = 0;
	}
	
	inline void modify(int cur, int l, int r, int x, int y, int k) {
		if (x <= l && y >= r) {
			f(cur, l, r, k);
			return ;
		}
		int mid = l + r >> 1;
		push_down(cur, l, r);
		if (x <= mid) modify(ls(cur), l, mid, x, y, k);
		if (y > mid ) modify(rs(cur), mid + 1, r, x, y ,k);
		push_up(cur);
	}
	inline int query(int cur, int l, int r, int x, int y) {
		if (x <= l && y >= r) return t[cur].sum; 
		int mid = l + r >> 1, ans = 0;
		push_down(cur, l, r);
		if (x <= mid) ans += query(ls(cur), l, mid, x, y);
		if (y > mid ) ans += query(rs(cur), mid + 1, r, x, y);
		return ans;
	}
}t;

signed main () {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	t.build(1, 1, n);
	for (int i = 1, flag; i <= m; i ++) {
		cin >> flag;
		if (flag == 1) {
			int x, y, k;
			cin >> x >> y >> k;
			t.modify(1, 1, n, x, y, k);
		} else if (flag == 2) {
			int x, y;
			cin >> x >> y;
			cout << t.query(1, 1, n, x, y) << '\n';
		}
	}
	return 0;
}

\(\mathcal{Part}\) 6.后记

数据结构他是灵活的，所以要多加练习，特别是线段树，应用非常之广泛，当然，我并没有学分块，所以只会线段树

标签：cur,int,void,基础,mid,mathcal,inline,数据结构
From： https://www.cnblogs.com/Phrvth/p/17498033.html

相关文章

  • 01-C语言基础语法
    目录一.C语言发展史二.数据类型三.常量和变量四.字符串和转义字符五.选择语句六.循环语句七.函数一.C语言发展史1963年ALGOL60作为C语言最早的模型，剑桥大学将其发展成为CPL(CombinedProgramingLanguage)。1967年，剑桥大学的MatinRichards对CPL语言进行了简......
  • 安卓系列之 kotlin 项目实战--基础 demo
    本章记录一个基础的demo项目，使用kotlin+协程+retrofit+okhttp3+MVVM实现。功能需求调用天气api，在主页显示天气情况。大致流程api申请及实体分析网络请求权限添加kotlin，协程，网络框架等依赖网络框架Retrofit+okhttp3主页页面绘制基础类构建调用接口并显示在当前页面api申请......
  • 8086汇编语言基础学习（四）——汇编语言程序设计基础
    8086汇编语言基础学习（四）——汇编语言程序设计基础DOS中常用的系统调用：1.单字符输入并显示（01H功能调用）描述：从键盘输入一个字符的ASCII码送入寄存器AL中，并送显示器显示。如果按下的是Ctrl＋Break组合键，则终止程序执行。1号功能调用无须入口参数，出口参数在AL中格式： 2.单字符......
  • 基础知识-关键字
    资料参考2021年计算机组成原理考研复习指导|王道考研【重学计算机】计算机组成原理|cnblogs|闪客sun2021年操作系统考研复习指导|王道考研【重学计算机】计算机操作系统|cnblogs|闪客sun计算机组成原理可以在计算机中直接执行的语言和用助记符编写的语言是（机器......
  • 宋红康-Java基础复习笔记详细版
    Java基础复习笔记第01章：Java语言概述1.Java基础学习的章节划分第1阶段：Java基本语法Java语言概述、Java的变量与进制、运算符、流程控制语句（条件判断、循环结构）、break\continue、IDEA开发工具的使用、数组第2阶段：面向对象编程（基础、进阶、高级）第3阶段：Java高级应用异常......
  • Android NDK 开发基础：C 语言的内存管理
    简介C语言的内存管理，分成两部分。一部分是系统管理的，另一部分是用户手动管理的。系统管理的内存，主要是函数内部的变量（局部变量）。这部分变量在函数运行时进入内存，函数运行结束后自动从内存卸载。这些变量存放的区域称为”栈“（stack），”栈“所在的内存是系统自动管理的。用户手动管理......
  • 基础的框架漏洞 6
    一、log4j远程代码执行漏洞原理:Log4j是Apache的一个开源项目，是一款基于Java的开源日志记录工具。该漏洞主要是由于日志在打印时当遇到~$后，以:号作为分割，将表达式内容分割成两部分，前面一部分prefix，后面部分作为key，然后通过prefix去找对应的iookup，通过对应的lookup实例调用lookup......
  • Kotlin协程：Flow基础原理
    本文分析示例代码如下：launch(Dispatchers.Main){flow{emit(1)emit(2)}.collect{delay(1000)withContext(Dispatchers.IO){Log.d("liduo","$it")}Log.d("liduo",&......
  • Android 屏幕适配基础
    Pixels和dp、sp的区别不同屏幕密度下,1p显示的物理长度不同1dp在不同屏幕上显示相同的物理长度sp只用在字体上，和dp一样为了让在不同设备上有一致的显示效果单位尺寸搞清楚屏幕的各种单位含义,是屏幕适配的基础屏幕尺寸含义：手机对角线的物理尺寸单位：英寸（inch），1英寸=2.54cm屏幕尺寸......
  • 基础算法：二分，贪心等 学习笔记
    普及组基础算法这些都是零零散散接触过的基础算法，写个笔记把这些整理到一起来。线性降维技巧之前在学校洛谷团队里看到一个题单，觉得这些技巧可能有用，就转存了。前缀和差分前缀和是一种对区间求和问题进行降维的方法。具体地，对于给定数组\(A[n]\)，求出\(A[l,r]\)区间和这个......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99