基础数据结构
\(\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