学习记录

энтджей

2026-06-13 13:49:42

发布于：浙江

20阅读

0回复

0点赞

2026/2/24

1.map:

(1).定义map：
- 导入：#include <map>
- 定义：map<建的类型，值的类型> 名字;
  - 如：map<int,int> m;
(2). map相关操作：

函数	功能说明
`begin()`	返回一个迭代器，指向map中的第一个键值对。
`end()`	返回一个迭代器，指向map中最后一个键值对的下一个位置。
`erase()`	根据键删除一个键值对。
`clear()`	清空map中的所有键值对
`empty()`	如果map为空则返回true
`size()`	返回map中键值对的数量
`find()`	查找一个键是否存在于map中，如果找到了则返回该键对应的迭代器，否则返回map::end()
`swap()`	交换两个map
`rbegin()`	返回一个指向map尾部的逆向迭代器
`rend()`	返回一个指向map头部的逆向迭代器
`count()`	返回指定元素出现的次数
`max_size()`	返回可以容纳的最大元素个数
`insert()`	插入元素
`key_comp()`	返回比较元素key的函数
`value_comp()`	返回比较元素value的函数

(3). map的两种遍历方式：

    // 方式1：范围for循环遍历
    map<string, string> mp1;
    for (auto &item : mp1) {
        string key = item.first;   // 键
        string val = item.second;  // 值
    }

    // 方式2：迭代器遍历
    map<string, string> mp2;
    for (auto it = mp2.begin(); it != mp2.end(); it++) {
        cout << it->first << it->second << endl;
    }

2.set

(1).定义set：
- 导入：#include <set>
- 定义：set<类型> 名字;
  - 如：set<int> s;
(2).set的相关操作

函数	功能说明
`begin()`	返回一个迭代器，指向集合中的第一个元素（`std::set` 为有序首元素，`std::unordered_set` 为哈希表首个存储元素）。
`end()`	返回一个迭代器，指向集合中最后一个元素的下一个位置（尾后迭代器，不可解引用）。
`erase()`	可按值、迭代器或迭代器范围删除集合中的元素，按值删除时返回删除的元素个数（0 或 1）。
`clear()`	清空集合中的所有元素，清空后集合大小为 0。
`empty()`	如果集合为空则返回 `true`，否则返回 `false`。
`size()`	返回集合中当前存储的元素个数。
`find()`	查找指定值的元素，找到则返回该元素的迭代器，未找到则返回 `end()`。
`swap()`	交换两个同类型集合的内容（元素、大小等），效率高。
`rbegin()`	返回指向集合尾部的逆向迭代器（仅 `std::set` 支持，`unordered_set` 无逆向迭代器）。
`rend()`	返回指向集合头部的逆向迭代器（仅 `std::set` 支持，`unordered_set` 无逆向迭代器）。
`count()`	返回集合中指定值的元素出现次数（集合元素唯一，故返回值为 0 或 1）。
`max_size()`	返回集合理论上可容纳的最大元素个数（受系统内存、编译器限制）。
`insert()`	插入单个元素或元素范围，插入重复元素时会失败，返回 `pair<迭代器, bool>` 标识结果。
`key_comp()`	返回用于比较集合元素（键）的比较函数对象（仅 `std::set` 支持，`unordered_set` 无此函数）。
`value_comp()`	返回用于比较集合元素（值）的比较函数对象（仅 `std::set` 支持，`unordered_set` 无此函数）。
`emplace()`	直接在集合中构造元素（避免拷贝/移动），效率比 `insert()` 更高，返回值同 `insert()`。
`emplace_hint()`	结合迭代器提示插入元素（仅 `std::set` 有优化效果），进一步提升插入效率。
`bucket_count()`	返回哈希表的桶数量（仅 `std::unordered_set` 支持，`std::set` 无此函数）。

2026/2/25

1.deque
- (1).定义deque：
  - 导入：#include <deque>
  - 定义：deque<类型> 队列名;
    - 如： deque<int> q;
- (2).deque的操作：

    deque<int> q;    //定义双端队列
    int x;           //一个数字
    q.push_front(x); //在队首加入x
    q.push_back(x);  //在队尾加入x
    q.pop_front();   //弹出队首
    q.pop_back();    //弹出队尾
    q.front();       //获取队首
    q.back();        //获取队尾
    q.empty();       //检测是否为空 空返回true 不空返回false
    q.size();        //获取队列长度
    q.clear();       //清空队列

2.list
- (1).定义list：
  - 导入：#include <list>
  - 定义：list<类型> 链表名;
    - 如： list<int> L;
3.pair
- (1).定义pair：
  - 导入：#include <utility>
  - 定义：pair<类型,类型> 变量名;
    - 如： pair<int,int> p;

2026/6/6

1.ST表

(1). ST表的数据结构定义：
- $dpi][j]$ 表示左端点为 $i$ ，右端点为 $i + 2^{j-1}$ ，区间长度为 $2^j$ 的区间最值。递推关系为：
  $dp[i][j] = max(dp[i][j - 1],dp[i + 1 << (j - 1)][j - 1])$
  其中 $1 << (j - 1)$ 表示 $2^{j - 1}$

(2). ST表的相关代码：

void ST_create(){ // ST表的创建
    for(int i = 1; i <= n; i++) {
        // 表示[i, i]区间的最值，区间长度为2^0 = 1
        F[i][0] = a[i];
    }
    // 下标 j 的取值范围
    int k = log2(n);
    // 先枚举区间的长度
    for(int j = 1; j <= k; j++) {
        // 左端点取值范围是 N - 2^j + 1
        for(int i = 1; i <= n - (1 << j) + 1; i++) {
            F[i][j] = max(F[i][j - 1], F[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int ST_query(int l, int r) { // 求[l, r]区间的最值
    int k = log2(r - l + 1); //确定给每个小区间的长度，r-l+1是区间长度
    return max(F[l][k], F[r - (1 << k) + 1][k]);  //取最大值
}

2026/6/13

1.线段树

(1).如何建树：

// int -> long long
void build(int p, int l, int r) { // 根节点 左节点 右节点
    // 将左节点和右节点的数据放入p节点下
    tree[p].l = l;
    tree[p].r = r;
    // 当前是叶子节点，当左节点等同于右节点时，已将到达最后一层
    if(l == r) {
        tree[p].value = arr[l]; // 放入值，放入arr[r]也是一个道理
        return ;                // 结束，退出之后不执行了 或者写else形式
    }
    // (l + r) >> 1 找出中间值
    int mid = (l + r) / 2;
    build(p * 2, l, mid);                                      // 构建左子树
    build(p * 2 + 1, mid + 1, r);                              // 构建右子树
    tree[p].value = tree[p * 2].value + tree[p * 2 + 1].value; // 回溯
}

(2).单点修改：

// int -> long long
void update(int p, int x, int z) { // 单点修改 根节点 需要修改的节点 需要修改值
    // 找到需要查询的位置
    if(tree[p].l == tree[p].r) {
        // 对于找到的位置进行修改(给x的位置增加)
        tree[p].value += z;
        return ;
    }
    // 二分范围
    int mid = (tree[p].l + tree[p].r) / 2; // 当前节点左右 区划分
    if(x <= mid) {
        // 如果需要修改的左半边范围正好包含
        update(p * 2, x, z);
    } else if(x > mid) {
        // 如果需要修改的右半边范围正好包含
        update(p * 2 + 1, x, z);
    }
    tree[p].value = tree[p * 2].value + tree[p * 2 + 1].value; // 回溯
}

(3).区间查询：

// int -> long long
int query(int p, int x, int y) { // 区间查询 根节点 查询区间左 查询区间右
    // 需要查询的范围包含了p下标的所有
    if(x <= tree[p].l && y >= tree[p].r) {
        // 范围p下标包含的值
        return  tree[p].value;
    }
    int mid = (tree[p].l + tree[p].r) / 2; // 二分范围
    int flag = 0;                          // 记录总和
    if(x <= mid) {                         // 如果需要修改的范围正好包含
        flag += query(p * 2, x, y);        // 去左子树取值
    }
    if(y > mid) {                          // 如果需要修改的范围正好包含
        flag += query(p * 2 + 1, x, y);    // 去右子树取值
    }
    return flag;
}