『ACM-XCPC | Data Structure』数据结构梳理

就是负责的数据结构部分啦

Posted by GJ on July 25, 2020

STL

<list>链表:插入删除操作为O(1),不能使用[]访问

<vector>可变长度数组

一般数  
front a.front(); 返回a的第一个元素
back a.back(); 返回a的最后一个元素
  a.size(); 返回a中元素的个数;
a.max_size() vector最大可以为多大
a.end() 得到数组的最后一个单元+1的指针
a.rbegin() 将vector反转后的开始指针返回(其实就是原来的end-1)
a.rend() 将vector反转后的结束指针返回(其实就是i原来的begin+1)
成员函数  
assign a.assign(b.begin(), b.begin()+3); b为向量,将b的0~2个元素构成的向量赋给a
a.assign(4,2);是a只含4个元素,且每个元素为2
push_back a.push_back(5); 在a的最后一个向量后插入一个元素,其值为5 O(n)
pop_back a.pop_back(); 删除a向量的最后一个元素 O(n)
insert a.insert(a.begin()+1,5); 在a的第1个元素(从第0个算起)的位置插入数值5,如a为1,2,3,4,插入元素后为1,5,2,3,4
a.insert(a.begin()+1,3,5); 在a的第1个元素(从第0个算起)的位置插入3个数,其值都为5 a.insert(a.begin()+1,b+3,b+6); b为数组,在a的第1个元素(从第0个算起)的位置插入b的第3个元素到第5个元素(不包括b+6),如b为1,2,3,4,5,9,8,插入元素后为1,4,5,9,2,3,4,5,9,8
erase a.erase(a.begin()+1,a.begin()+3); 删除a中第1个(从第0个算起)到第2个元素,也就是说删除的元素从a.begin()+1算起(包括它)一直到a.begin()+3(不包括它)
swap a.swap(b); b为向量,将a中的元素和b中的元素进行整体性交换
clear a.clear(); 清空a中的元素,大小变为0
empty a.empty(); 判断a是否为空,空则返回ture,不空则返回false
resize a.resize(10); 将a的现有元素个数调至10个,多则删,少则补,其值随机
a.resize(10,2); 将a的现有元素个数调至10个,多则删,少则补,其值为2
capacity a.capacity(); 返回a在内存中总共可以容纳的元素个数
reserve a.reserve(100);将a的容量(capacity)扩充至100,也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才显得有意义,因为这将避免内存多次容量扩充操作(当a的容量不足时电脑会自动扩容,当然这必然降低性能)
  a==b; b为向量,向量的比较操作还有!=,>=,<=,>,<

<stack>栈

成员函数  
q.push(a) 入队。将一个元素a置入队列q中
q.pop() 出队。从队列q中移除第一个元素 //并不返回该元素
q.top() 返回队列q内的第一个元素(也就是第一个被置入的元素)
q.empty() 判断队列q是否为空,当队列q为空时,返回ture;否则返回false
q.size() 访问队列q中的元素个数。

单调栈

  • 复杂度:O(n)​
  • 应用
    • 对于某个元素i:
    • 左边区间第一个比它小的数,第一个比它大的数
    • 确定这个元素是否是区间最值
    • 右边区间第一个大于它的值
    • 到 右边区间第一个大于它的值 的距离
    • 确定以该元素为最值的最长区间
  • CODE

<queue>队列

成员函数  
q.push(a) 入队。将一个元素a置入队列q中
q.pop() 出队。从队列q中移除第一个元素 //并不返回该元素
q.front() 返回队列q内的第一个元素(也就是第一个被置入的元素)
q.back() 返回队列q中最后一个元素(也就是最后被插入的元素)
q.empty() 判断队列q是否为空,当队列q为空时,返回ture;否则返回false
q.size() 访问队列q中的元素个数。

<priority_queue>优先队列

  • 升序队列:priority_queue <int,vector<int>,greater<int> > q;

    降序队列:priority_queue <int,vector<int>,less<int> >q;

  • 插入元素的复杂度:O(logn)​,删除元素的复杂度:O(1)​

成员函数  
q.push(a) 入队。将一个元素a置入队列q中
q.pop() 出队。从队列q中移除第一个元素 //并不返回该元素
q.top() 返回队列q内的第一个元素(也就是第一个被置入的元素)
q.back() 返回队列q中最后一个元素(也就是最后被插入的元素)
q.empty() 判断队列q是否为空,当队列q为空时,返回ture;否则返回false
q.size() 访问队列q中的元素个数。
create() 创建一个空的优先队列
size() 返回队列中的元素数目
max() 返回具有最大优先权的元素
insert(x) 将x插入队列
deleteMax(x) 从队列中删除具有最大优先权的元素,并将该元素返回至x

<deque>双端队列

构造函数  
deque<elem>c 创建一个空的deque
deque<elem>c1(c2) 复制一个deque
deque<elem>c(n) 创建一个deque,含n个数据
deque<elem>c(n,elem) 创建一个含有n个elem拷贝的deque
deque<elem>c(beg,end) 创建一个以[beg;end)区间的deque
~deque<elem>() 销毁所有数据,释放内存
成员函数  
c.begin() 返回第一个元素的迭代器
c.end() 返回指向最后一个元素下一个位置的迭代器
c.rbegin() 返回指向反向队列的第一个元素的迭代器
c.rend() 返回指向反向队列的最后一个元素的下一个位置
c.assign(n,num) 将n个num拷贝复制到容器c
c.assign(beg,end) 将[beg,end)区间的数据拷贝复制到容器c
c.at(pos) 返回索引为pos的位置的元素,会执行边界检查,如果越界抛出out_of_range异常
c.operator[] 下标运算符重载
c.empty() 判断c容器是否为空
c.front() 返回c容器的第一个元素
c.back() 返回c容器的最后一个元素
c.size() 返回c容器中实际拥有的元素个数
c.max_size() 返回c容器可能存放元素的最大数量
c.clear() 清除c容器中拥有的所有元素
c.insert(pos,num) 在pos位置插入元素num
c.insert(pos,n,num) 在pos位置插入n个元素num
c.insert(pos,beg,end) 在pos位置插入区间为[beg,end)的元素
c.erase(pos) 删除pos位置的元素
c.erase(beg,end) 删除区间为[beg,end)的元素
c.push_back(num) 在末尾位置插入元素
c.pop_back() 删除末尾位置的元素
c.push_front(num) 在开头位置插入元素
c.pop_front() 删除开头位置的元素
c.resize(num) 重新定义容器大小
c1.swap(c2) 交换容器c1,c2
swap(c1,c2) 交换容器c1,c2

单调队列

  • 复杂度:O(n)
  • 应用

    • 可以查询区间最值(不能维护区间k大,因为队列中很有可能没有k个元素)
    • 优化DP
  • 单调队列一般是用于优化动态规划方面问题的一种特殊数据结构,且多数情况是与定长连续子区间问题相关联。

  • 代码:

    //在“尾部”添加元素x
    while (l != r && mq[r] <= x) r--;
    mq[++r] = x;
      
    //查询队首元素
    if (l != r) printf("%d\n", mq[l+1]);
    else printf("-1\n");
      
    //弹出队首元素
    if (l != r) l++;
    

<set>集合

  • 复杂度O(logN)每次访问
成员函数  
begin() 返回指向第一个元素的迭代器
end() 返回指向最后一个元素的迭代器
clear() 删除set容器中的所有的元素
empty() 判断set容器是否为空
insert(x) 往set容器中插入x
max_size() 返回set容器包含的元素最大个数
size() 返回当前set容器中的元素个数
erase(it) 删除迭代器指针it处元素
count(a) 查找set中某个元素出现的次数。这个函数在set并不是很实用,因为一个键值在set只可能出现0或1次,这样就变成了判断某一键值是否在set出现过了。
find(a) 查找set中某个元素出现的位置。如果找到,就返回这个元素的迭代器,如果这个元素不存在,则返回 s.end() 。 (最后一个元素的下一个位置,s为set的变量名)
equal_range() 返回集合中与给定值相等的上下限的两个迭代器
get_allocator() 返回集合的分配器
lower_bound() 返回指向大于(或等于)某值的第一个元素的迭代器
key_comp() 返回一个用于元素间值比较的函数
rbegin() 返回指向集合中第一个元素的反向迭代器
swap() 交换两个集合变量
upper_bound() 返回大于某个元素的迭代器
value_comp() 返回一个用于比较元素间的值的函数

<multiset>多重集合

<map>映射

  • 复杂度O(logN)每次访问
  • 红黑树对数据自动排序

<unordered_map>多重映射

  • 每次访问复杂度O(1)
  • 哈希表存储

<string>字符串

成员函数  
assign() 用于赋予新值,assign函数用于将一个字符串的部分内容赋值给另一个string对象
swap() 交换两个字符串的内容
+=、append()、push_back() 在字符串尾部追加内容,”+=”可追加string对象,字符以及C风格字符串,append函数则可以追加string对象和C风格字符串,push_back函数则只能追加字符
insert() 用于插入字符串
erase() 用于删除字符
clear()、~string() clear()删除str的全部字符,后者销毁所有字符,释放内存
size()、length() 返回字符串的字符数
empty() 判断字符串是否为空

运算符重载

struct node{
    string name;
    double score;
    bool operator < (const node &a) const{ // 重载“<”操作符,自定义排序规则   
        return a.score < score;//按score由大到小排序。如果要由小到大排序,使用“>”即可。
    }
};

哈希

哇塞!队友会欸(叉腰 梦幻1e12+7

那我是不是可以……

Hash 表

字符串 Hash

矩阵 Hash

并查集

  • 并查集优化:CODE(秩优化)带权并查集不用

ST表

  • O(1)查询区间最值
  • 复杂度:O(nlogn)预处理,O(1)查询最值
  • CODE

树状数组

  • 注意树状数组无法处理0的情况

一维树状数组

  • 注意初始化d数组
  • 复杂度:O(logN)
  • 树状数组并非支持所有的区间更新,例如区间赋值等

image-20200729205146135

二维树状数组

板子来自LUOGU P4514 上帝造题的七分钟

保证所有数据范围在int范围内

然后……开llMLE

N维树状数组

  • 更新2^n个点
  • 就再添上for就行啦,n重for

线段树

  • 应用
    • 单点修改 询问区间
    • 区间修改 询问区间
    • 单点修改 询问区间gcd
    • 区间修改 询问区间gcd
    • 询问最短权值路径 dfs序 括号序 数据100000 卡别的做法好像是
    • 扫描线与线段树 例如:1 l r 连线 2 l r 去线 3 询问全段未被覆盖 ——-区间修改 我???
    • 区间修改 询问连续段 例:以01段为例 分段,各小段,再合并更新
    • 网网络流???

有一个没写进来,HYSBZ2733永无乡的线段树合并//看了看自己的代码秃然有点不太懂

  • CODE
  • 线段树+扫描线_矩形面积并:CODE

主席树

可持久化线段树

  • 复杂度
    • 建树:O(nlogn)
    • 询问:O(mlogn)
    • 总复杂度:O((n+m)logn)
    • 空间复杂度:O(nlogn^2)
  • 应用
    • 题目给你一个序列,每次修改后算一个新的版本,询问某个版本中某个值
  • CODE
  • 求区间不同元素个数:CODE

平衡树

在这里插入图片描述

Treap

Treap的本质是一颗二叉查找树,只是在每个结点上都附加了一个优先级的信息。保证每个点的优先级都比左右儿子小,利用优先级,我们可以把这颗树看成一个小根堆。

  • Treap树在随机给优先级的情况下,可以在期望O(logn)的时间复杂度里完成:
    • 一个结点的插入
    • 一个结点的删除
    • 查询第K大的值
    • 给定一个值返回它是第几大
    • 返回某值的前驱结点(严格小于key的最大数)
    • 返回某值的后继结点(严格大于key的最小数)
  • CODE

fqh-Treap

  • 复杂度:O(nlogn)

  • 同上:CODE
  • 区间翻转:CODE

Splay

它的主要思想是:对于查找频率较高的节点,使其处于离根节点相对较近的节点

  • 复杂度:O(nlogn)

  • 普通平衡树:CODE
  • 区间翻转:CODE