离散化（Discretization）在计算机科学和算法领域，是一种将连续的数值或大量不连续的数值，转换为有限且相对较小的离散值（通常是整数）的技术。离散化在处理大范围数值、优化空间复杂度和时间复杂度、方便索引或哈希操作时十分常用。

---

离散化的基本概念

假设有一组数值数据，例如：

[1000, 5000, 10000, 5000, 1000]

这些数据值跨度比较大，且不连续。如果直接用于某些算法（如区间查询、树状数组、线段树等），会导致空间开销很大甚至不可行。此时可以把这组数值“压缩”或“映射”到一个连续且较小的区间，比如：

1000 -> 1
5000 -> 2
10000 -> 3

这样，原数组就变成了：

[1, 2, 3, 2, 1]

这里的1,2,3即是离散化的“坐标”或“秩（rank）”，方便数据结构操作。

---

离散化的基本步骤

以 vector<int> arr 为例，演示离散化的常见步骤：

1. 复制并排序：复制一份数组，然后排序去重，得到所有不同的数值，构建映射基准。
2. 查询映射：对原数据的每个元素，用二分查找在排序去重后的数组中找到对应的位置，即映射后的离散值。

示例代码：
```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
vector<int> arr = {1000, 5000, 10000, 5000, 1000};
vector<int> values = arr; // 复制

// 1. 排序去重
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());

// 2. 离散化映射
for (int i = 0; i < (int)arr.size(); i++) {
// 二分查找映射值
int pos = (int)(lower_bound(values.begin(), values.end(), arr[i]) - values.begin());
cout << "原值: " << arr[i] << " 离散化后为: " << pos + 1 << endl; // 位置+1 方便从1开始编号
}

return 0;
}
```

输出：

原值: 1000 离散化后为: 1
原值: 5000 离散化后为: 2
原值: 10000 离散化后为: 3
原值: 5000 离散化后为: 2
原值: 1000 离散化后为: 1


---

为什么要用离散化？

1. 减少空间复杂度
   
   例如，某些数据范围的最大值是10^9，建线段树或树状数组开销很大或不可行。离散化后把数据映射到1 ~ n范围内(n为元素个数或不同元素个数)，更容易建树结构。

2. 方便排序和二分
   
   离散化后元素有序且连续，方便使用二分查找和索引访问。

3. 消除数据稀疏性
   
   把原数据稀疏的数值映射为紧凑的序号，方便存储和查询。

---

离散化的应用场景

• 区间查询（线段树、树状数组）
• 排序与排名问题
• 统计出现次数或频率问题
• 区间合并、区间计数问题

---

注意事项

• 离散化后得到编号是从0开始还是1开始，可以根据具体需要选择。
• 映射过程中的二分查找时间复杂度为 O(log n)。
• 离散化仅改变数值表示，不影响原数据的相对排序关系。

---

总结：

离散化是一种常用的数据预处理技术，将大数值或稀疏数据转换成紧凑且连续的编号，使得后续算法和数据结构操作更高效、更方便。掌握离散化在C++中实现，对于解决各种数据量大、范围广的算法问题非常重要。
好的，下面详细讲解C++中的**哈希（Hashing）**知识点。

---

哈希（Hashing）详解

哈希是计算机科学中非常重要的数据处理和存储技术，常用于快速查找、去重和映射。哈希通过把输入（键）映射为固定长度的“哈希值”，实现高效的数据访问。

---

1. 基本概念

• 哈希函数（Hash Function）：将输入（通常是字符串、数字、对象）映射为一个整数的函数。
  
• 哈希值（Hash Value）：经过哈希函数计算得到的整数。
  
• 哈希表（Hash Table）：一种用于快速查找的数据结构，利用哈希函数把键映射到数组的“桶”（bucket）索引，实现常数时间复杂度平均查找。

---

2. 哈希的作用

• 快速查找（字典、映射）
  
• 去重（集合）
  
• 频率统计
  
• 快速判重
  
• 数据加密（密码学）
  
• 数据分布与负载均衡

---

3. C++中哈希的常用实现

3.1 标准库 std::unordered_map 和 std::unordered_set

C++的标准库为哈希提供了封装好的关联容器：

• std::unordered_map<Key, Value>：基于哈希表的键值对映射
  
• std::unordered_set<Key>：基于哈希表的键集合

这些容器底层实现了哈希表，对于常用内置类型（int, string等）提供了默认的哈希函数。

示例：
```cpp
#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

int main() {
unordered_map<string, int> mp;
mp["apple"] = 3;
mp["banana"] = 5;

cout << "apple count: " << mp["apple"] << endl;
cout << "banana count: " << mp["banana"] << endl;

// 检查某个键是否存在
if (mp.find("orange") == mp.end()) {
cout << "orange not found" << endl;
}

return 0;
}
```

---

4. 哈希函数设计

为了避免哈希冲突（不同的键映射到了相同的位置），哈希函数设计非常重要。

4.1 内置哈希函数

• 对于整数类型，通常是取模或直接返回数字本身（因为数字本身就是很好的随机数）。
  
• 对于字符串，C++ STL采用了基于多项式滚动的哈希函数。

4.2 自定义哈希函数

在一些场合（比如自定义类型、性能要求很高时），需要定义自定义哈希函数。

示例：自定义类型的哈希函数

#include <iostream>
#include <unordered_map>

using namespace std;

struct Point {
    int x, y;

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希函数
struct PointHash {
    size_t operator()(const Point& p) const {
        return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
    }
};

int main() {
    unordered_map<Point, int, PointHash> mp;
    mp[{1, 2}] = 10;
    mp[{3, 4}] = 20;

    cout << "mp[{1, 2}] = " << mp[{1, 2}] << endl;

    return 0;
}

4.3 高级哈希设计（抗冲突）

• 使用大质数及多项式递推法
• 双重哈希（double hashing）
• 加盐（salt）技术，防止攻击实例

---

5. 解决哈希冲突的方法

哈希冲突是哈希表最核心的问题之一。常用解决方法：

1. 链接法（Separate chaining）
   
   每个哈希桶存储一个链表（或其他结构）来保存发生冲突的元素。

2. 开放地址法（Open addressing）
   
   当某个槽位冲突时，寻找下一个空槽（线性探测，二次探测，双重哈希等）

std::unordered_map实现通常使用链接法。

---

6. 自己实现一个简单的哈希表示例

下面给出用链地址法实现的简易哈希表示范:

#include <iostream>
#include <vector>
#include <list>

using namespace std;

class SimpleHash {
    static const int SIZE = 769; // 取质数大小避免冲突聚集
    vector<list<int>> table;

public:
    SimpleHash() {
        table.resize(SIZE);
    }

    int hash(int key) {
        return key % SIZE;
    }

    void insert(int key) {
        int h = hash(key);
        for (int val : table[h]) {
            if (val == key) return; // 已经存在
        }
        table[h].push_back(key);
    }

    bool find(int key) {
        int h = hash(key);
        for (int val : table[h]) {
            if (val == key) return true;
        }
        return false;
    }
};

int main() {
    SimpleHash sh;
    sh.insert(100);
    sh.insert(186);

    cout << sh.find(100) << endl; // 输出1，表示找到
    cout << sh.find(200) << endl; // 输出0，表示未找到

    return 0;
}

---

7. 哈希表的时间复杂度

• 插入、删除、查找的平均时间复杂度：O(1)
• 最坏情况下（大量哈希冲突）：O(n)

---

8. 总结

知识点	说明
哈希函数	输入映射为整数，主要设计目标是“分布均匀”和“计算快”
哈希表	利用哈希函数实现的快速查找结构，核心是解决冲突
哈希冲突解决	主要用链表、开放地址法等方法避免冲突影响性能
C++标准库支持	std::unordered_map 和 std::unordered_set
自定义哈希函数	针对自定义类型或优化场景，需要实现适当的哈希函数和相等比较运算符
哈希的应用	字典、缓存、去重、各种需要快速查找的场合

---

如果你想了解更具体的内容，比如字符串哈希、滚动哈希、密码学哈希、或者哈希在某些算法中（如双指针、滑动窗口等）的应用，也可以告诉我！
好的，下面详细讲解 RMQ（Range Minimum Query） 的相关知识点及其在 C++ 中的实现。

---

RMQ（区间最小值查询，Range Minimum Query）

---

1. 什么是RMQ？

给定一个数组，你要支持在区间 [L, R] 内快速找到区间最小值。

换言之，我们有一个数组 arr，需要多次查询：
- 查询区间 [L, R] 中的最小元素。

---

2. RMQ应用场景

• 在线查询区间最小值
• 动态规划优化（比如序列最优分割）
• 处理区间统计问题（最近公共祖先、最大公约数等问题也有类似结构）

---

3. 常用的RMQ数据结构和算法

数据结构/算法	预处理时间	查询时间	备注
朴素遍历	无	O(R-L+1)	毫无技巧，查询慢适合数据量小
线段树	O(n)	O(log n)	支持动态修改，高效查询
稀疏表（Sparse Table）	O(n log n)	O(1)	不支持修改，查询极快，适合静态数组
斐波那契堆等其它	-	-	一般不用于RMQ

---

4. 典型实现详解

4.1 线段树实现RMQ

线段树可以区间查询最值，同时支持修改。

#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
private:
    vector<int> tree;
    int n;

    void build(vector<int>& arr, int idx, int l, int r) {
        if (l == r) {
            tree[idx] = arr[l];
            return;
        }
        int mid = (l + r) / 2;
        build(arr, idx*2, l, mid);
        build(arr, idx*2+1, mid+1, r);
        tree[idx] = min(tree[idx*2], tree[idx*2+1]);
    }

    int query(int idx, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return INT_MAX; // 不相交
        if (ql <= l && r <= qr) return tree[idx]; // 完全覆盖
        int mid = (l + r) / 2;
        return min(query(idx*2, l, mid, ql, qr), query(idx*2+1, mid+1, r, ql, qr));
    }

public:
    SegmentTree(vector<int>& arr) {
        n = (int)arr.size();
        tree.resize(n*4);
        build(arr, 1, 0, n-1);
    }

    int query(int l, int r) {
        return query(1, 0, n-1, l, r);
    }
};

int main() {
    vector<int> arr = {1, 3, -2, 8, -7, 3};
    SegmentTree seg(arr);
    cout << seg.query(1, 4) << endl; // 查询区间[1,4]最小值，输出 -7
    return 0;
}

---

4.2 稀疏表（Sparse Table）

• 预处理：O(n log n) 时间复杂度
• 查询：O(1) 时间复杂度
• 原理：利用区间长度为 2^k 的最小值合成更长的区间最小值

代码示例

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class SparseTable {
private:
    vector<vector<int>> st;
    vector<int> log_table;
    int n;

public:
    SparseTable(const vector<int>& arr) {
        n = (int)arr.size();
        log_table.resize(n+1);
        log_table[1] = 0;
        for(int i=2; i<=n; i++)
            log_table[i] = log_table[i/2] + 1;

        int max_log = log_table[n];
        st.assign(n, vector<int>(max_log+1));

        for(int i=0; i<n; i++)
            st[i][0] = arr[i];

        for(int j=1; j<=max_log; j++) {
            for(int i=0; i+(1<<j)-1 < n; i++) {
                st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
            }
        }
    }

    int query(int L, int R) {
        int length = R - L + 1;
        int k = log_table[length];
        return min(st[L][k], st[R - (1 << k) + 1][k]);
    }
};

int main() {
    vector<int> arr = {1, 3, -2, 8, -7, 3};
    SparseTable st(arr);
    cout << st.query(1, 4) << endl; // 输出 -7
    cout << st.query(0, 2) << endl; // 输出 -2
    return 0;
}

---

5. 哪种RMQ数据结构适合你？

情况	数据结构	备注
纯查询，数据不修改	稀疏表	查询最快，写代码复杂度适中
查询和更新都需要	线段树/树状数组	支持动态修改，查询较快
数据量特大，修改少	预处理稀疏表+线段树	综合利用两者优点
特殊范围查询（最大、最大公约数等）	可改造线段树或稀疏表	只要满足区间结合性质都可以

---

6. RMQ的原理补充

• 线段树基于分治思想递归合并区间最值。
  
• 稀疏表基于重叠区间查询性质，利用 min(a,b) 可分离区间合并。

稀疏表查询时，
- 区间长度 ( len = R-L+1 )
- 取 ( k = \lfloor \log_2 len \rfloor )
- 用两个长度为 (2^k) 的区间mid重叠覆盖整个查询区间

例如，查询区间是 [L,R]，两个区间是 [L, L+2^k-1] 和 [R-2^k+1, R]

---

7. 拓展

• RMQ 还可以支持最大值、最大公约数等区间计算，只要满足结合律。
• 可借助线段树和稀疏表更改存储层内容实现多种区间查询。

---

8. 总结

• RMQ是常用的区间查询问题
  
• 线段树支持动态修改，动态处理了一些复杂查询
  
• 稀疏表不支持修改，但查询速度是 (O(1))
  
• 根据需求选择合适的数据结构，实现简单且高效

---

如果你需要，我还能帮你写RMQ的其他变形，比如区间最大值、区间求和，或者支持修改版本。欢迎随时问！
好的，下面我会依次详细讲解你列出的每一个C++算法与数据结构知识点。每个知识点会单独处理，内容包括基本概念、原理、实现思路、代码示例、常见应用，以及注意事项等。

---

1. LCA（Lowest Common Ancestor）——最近公共祖先

---

基本概念

• 给定一棵树上的两个节点 (u, v)，他们的最近公共祖先（LCA）是指既是 (u) 和 (v) 的祖先，又在所有这样的祖先中距离 (u) 和 (v) 最近的节点。
• LCA 是树论中的经典问题，常用于求路径性质、求距离、合并信息等。

---

常见实现方法

• 倍增法（Binary Lifting）
  预处理每个节点的 (2^k) 级父节点。
• Tarjan离线算法（基于并查集）
  离线处理所有LCA查询。
• 树上欧拉序+RMQ
  先进行欧拉序遍历，形成序列，再用RMQ求区间最小值。

---

倍增法实现步骤

1. DFS计算每个节点深度。
2. 预处理每个节点的祖先 fa[node][k]，表示节点的 (2^k) 级祖先。
3. 查询时，从两个节点开始，将深度较大的节点向上跳，直到两节点深度相同。
4. 然后同时向上跳，直到两节点的祖先相同，那个祖先即为LCA。

---

C++代码示例

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 100010;
const int LOG = 20;

vector<int> adj[MAXN];   // 树的邻接表
int fa[MAXN][LOG];      // fa[u][k]表示u的2^k祖先
int depth[MAXN];        // depth[u]表示节点u的深度

void dfs(int u, int f) {
    fa[u][0] = f;
    for (int i = 1; i < LOG; i++) {
        if (fa[u][i - 1] != -1)
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
        else
            fa[u][i] = -1;
    }
    for (int v : adj[u]) {
        if (v != f) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    // 先提升深度
    int diff = depth[u] - depth[v];
    for (int i = 0; i < LOG; i++) {
        if ((diff >> i) & 1) {
            u = fa[u][i];
        }
    }
    if (u == v) return u;
    // 同时提升
    for (int i = LOG - 1; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

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

    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    memset(fa, -1, sizeof(fa));
    depth[1] = 0;
    dfs(1, -1);

    int q;
    cin >> q;
    while (q--) {
        int u,v;
        cin >> u >> v;
        cout << lca(u,v) << "\n";
    }
    return 0;
}

---

应用

• 计算树上两点距离
  
• 判断路径包含关系
  
• 树链剖分中的辅助操作
  
• 最近公共祖先是很多树算法的基础

---

注意事项

• 根节点深度通常定义为0或1，根据实现调整
  
• 预处理范畴通常为 (O(N \log N)) ，查询为 (O(\log N))
  
• 注意节点编号和输入格式，避免越界

---

2. 树上差分

---

基本概念

• 树上差分是一种利用差分思想处理树上区间更新的技巧。
• 当需要对树上的某些路径或子树范围进行多次修改，更新操作通过差分数组变成对根路径节点作加/减处理，最后通过一次DFS求前缀和还原。

例如：

假设我们需要将树中某节点的子树内所有节点增加某个值，可以使用树上差分。

---

实现思路

• 先对树做DFS给每个节点编号，使子树节点连续（通常使用 DFS 序）
• 维护一个一维差分数组 diff[]
• 对子树加值时，对 diff[dfs_in[u]] += k; diff[dfs_out[u]+1] -= k;
  
• 最后通过一次前缀和，计算每个节点的最终值。

---

代码结构示例

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100010;
vector<int> adj[MAXN];
int dfs_in[MAXN], dfs_out[MAXN];
int timer;
int diff[MAXN];
int val[MAXN];

void dfs(int u, int f) {
    dfs_in[u] = ++timer;
    for (auto v : adj[u]) {
        if (v != f) dfs(v, u);
    }
    dfs_out[u] = timer;
}

int main() {
    int n, q;
    cin >> n >> q;
    for(int i=1; i<n; i++) {
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, -1);

    for (int i=0; i<q; i++) {
        int u, k;
        cin >> u >> k;
        // 对u子树加k
        diff[dfs_in[u]] += k;
        diff[dfs_out[u] + 1] -= k;
    }

    // 前缀和还原值
    for (int i=1; i<=n; i++) {
        diff[i] += diff[i-1];
    }

    // 按dfs_in编号赋值给节点
    vector<int> ans(n+1);
    for (int i=1; i<=n; i++) {
        ans[i] = diff[dfs_in[i]];
        cout << ans[i] << " ";
    }
    cout << "\n";

    return 0;
}

---

应用

• 批量给子树节点赋值或者更新
  
• 区间修改 + 单点查询类题
  
• 树上区间维护问题的优化手段

---

注意事项

• 需要事先进行树的DFS序编号
  
• 整个方案基于差分数组一维实现
  
• 处理路径更新时较复杂，要小心差分区间的界限

---

3. 树状数组（Fenwick Tree）

---

基本概念

• 树状数组是一种高效维护数组前缀和的结构，支持单点更新和区间查询（前缀和）的数据结构。
• 代码简洁，性能常用于处理大数据量频繁查询和修改问题。

---

核心思想

• 利用二进制低位（lowbit）思想快速跳跃和聚合信息。
• lowbit(x) = x & (-x) 表示x的二进制最低位1所代表的值。

---

支持操作

• 单点修改: 在数组某点增加一个值。
• 前缀和查询: 查询从数组起点到某个点的区间和。

---

C++代码示例

#include <iostream>
#include <vector>
using namespace std;

class FenwickTree {
private:
    vector<int> tree;
    int n;

public:
    FenwickTree(int size) {
        n = size;
        tree.assign(n + 1, 0);
    }

    int lowbit(int x) {
        return x & (-x);
    }

    // 单点加值
    void update(int idx, int delta) {
        while (idx <= n) {
            tree[idx] += delta;
            idx += lowbit(idx);
        }
    }

    // 前缀和查询
    int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= lowbit(idx);
        }
        return sum;
    }

    // 区间查询 [l, r]
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

int main() {
    FenwickTree fenw(10);
    fenw.update(3, 5); // 第3个位置加5
    fenw.update(5, 2);
    cout << fenw.query(1, 5) << endl;  // 输出7 = 5 + 0 + 0 + 0 + 2
    return 0;
}

---

应用

• 区间求和、逆序对等问题
  
• 频繁单点修改，前缀和查询场景
  
• 和线段树相比代码简单，使用方便

---

注意事项

• 数组下标一般从1开始
  
• 不能直接处理区间修改（需要借助树状数组的高级技巧）
  
• 只支持加法修改，不适用于复杂操作（如区间赋值）

---

4. 字典树（Trie）

---

基本概念

• 字典树是一种树形数据结构，用于存储字符串集合，支持字符串的快速查找、插入等操作。
• 典型用来解决字符串检索、前缀匹配问题。

---

基本结构

• 每个节点有多个指向下一个字符节点的指针（通常用数组或哈希表实现，字符集大小为常数）
• 字符串由根节点出发沿路径遍历其字符对应的边。
• 通常节点保存是否为单词结尾、包含子节点信息。

---

C++示例代码

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1000000;
const int ALPHABET = 26;  // 字母大小写

int trie[MAXN][ALPHABET];
int isEnd[MAXN];  // 标记单词结尾
int idx = 0;      // 当前节点计数，根节点是0

// 插入字符串
void insert(const char* s) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        if (!trie[p][c]) trie[p][c] = ++idx;
        p = trie[p][c];
    }
    isEnd[p]++;
}

// 查询字符串是否存在
bool query(const char* s) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        if (!trie[p][c]) return false;
        p = trie[p][c];
    }
    return isEnd[p] > 0;
}

int main() {
    insert("hello");
    insert("world");
    cout << query("hello") << "\n";  // 输出1
    cout << query("hell") << "\n";   // 输出0
    cout << query("world") << "\n";  // 输出1
    return 0;
}

---

应用

• 字符串集合的快速插入、查询
  
• 前缀匹配、自动补全
  
• 字符串相关问题如AC自动机、字符串统计等核心基础结构

---

注意事项

• 节点指针数组开的大小要足够大，根据字符串数和长度判断
  
• 不同题目字符集不同，也要调整 ALPHABET 和映射方式
  
• 对内存需求较大，细心实现和释放

---

5. 单调栈

---

基本概念

• 单调栈是一种特别的栈，栈内元素保持单调性（递增或递减）。
• 常用于解决下一个更大/小元素、柱状图面积、最长有效区间等问题。

---

工作原理

• 遍历数组，如果当前元素比栈顶元素符合单调规则，则直接入栈。
• 否则弹出栈顶元素处理（如计算区间、面积），直到满足单调条件。

---

C++示例（求每个位置右边第一个更小元素）

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> nextSmallerElement(const vector<int>& arr) {
    int n = (int)arr.size();
    vector<int> res(n, -1);
    stack<int> st; // 存储元素下标

    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[i] < arr[st.top()]) {
            res[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }

    return res;
}

int main() {
    vector<int> arr = {3, 7, 1, 7, 8, 4};
    vector<int> res = nextSmallerElement(arr);
    for (int x : res)
        cout << x << " ";  // 输出下标或-1
    return 0;
}

---

应用

• 找下一个更大/更小元素
  
• 求最大矩形面积（柱状图）
  
• 单调栈是解决很多单调序列性质问题的基础工具

---

注意事项

• 确认栈维持递增还是递减
  
• 注意边界条件，例如元素相等处理规则
  
• 输出结果中有无对应的边界情况(-1等处理)

---

6. 单调队列

---

基本概念

• 单调队列是一种使队列中的元素保持单调性的结构。
• 常用于滑动窗口中查询最大值或最小值。

---

工作流程

• 遍历数组，维持队列元素是单调非增或非减。
• 入队时，将队尾不满足单调性的元素弹出。
• 窗口移动时，将队头元素如果过期弹出。

---

C++示例（滑动窗口最大值）

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // 存储下标，保证队列头是最大值
    vector<int> res;
    for (int i = 0; i < (int)nums.size(); i++) {
        while (!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();
        dq.push_back(i);

        if (i >= k - 1) {
            while (dq.front() <= i - k)
                dq.pop_front();
            res.push_back(nums[dq.front()]);
        }
    }
    return res;
}

int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    for(int x: res) cout << x << " ";
    return 0;
}

---

应用

• 滑动窗口最大/最小值问题
  
• 单调结构优化某些动态规划和双指针问题
  
• 队列型问题的高效实现

---

注意事项

• 维护队列内元素的下标而非值，方便判定元素区间过期
  
• 注意窗口边界更新，避免访问数组越界
  
• 对单调性方向掌握好（增或减）

---

7. SPFA（Shortest Path Faster Algorithm）

---

基本概念

• SPFA是 Bellman-Ford 算法的一种优化，解决单源最短路径问题，尤其是存在负权边时。
• 适合图中边比较稀疏且无负权环检测。

---

算法流程

• 利用队列维护被松弛的节点
  
• 起点松弛后入队，松弛邻居节点后再入队
  
• 直到队列空，最短距离收敛

---

C++示例

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 100010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, w;
};

vector<Edge> adj[MAXN];
int dist[MAXN];
bool inQueue[MAXN];
int cnt[MAXN];   // 节点入队次数(判负环)

bool spfa(int start, int n) {
    memset(dist, 0x3f, sizeof(dist));
    memset(inQueue, 0, sizeof(inQueue));
    memset(cnt, 0, sizeof(cnt));
    dist[start] = 0;
    queue<int> q;
    q.push(start);
    inQueue[start] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;
        for (auto &e : adj[u]) {
            int v = e.to;
            if (dist[v] > dist[u] + e.w) {
                dist[v] = dist[u] + e.w;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    if (++cnt[v] > n)
                        return false; // 有负环
                }
            }
        }
    }
    return true;
}

int main() {
    int n,m;
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
    }
    if(spfa(1,n))
        for(int i=1;i<=n;i++)
            cout << dist[i] << " ";
    else
        cout << "Negative cycle detected\n";
    return 0;
}

---

应用

• 解决负权边单源最短路径
  
• 路径规划、网络流的潜在辅助

---

注意事项

• 效率一般情况下不错，最坏((O(NM)))与Bellman-Ford一致
  
• 检测负环可通过节点入队次数限制实现
  
• 图中边权涉及负数时慎用Dijkstra算法

---

8. 线段树

---

（此知识点前面在“RMQ”已详细介绍，补充更多通用线段树知识）

---

线段树核心

• 二叉树结构维护数组区间信息
• 时间复杂度：构建O(n), 单次查询/修改O(log n)

---

支持操作

• 区间查询 如区间最小、最大、和等
  
• 单点更新 或支持区间更新（带懒标记）

---

一般实现形式

struct SegmentTree {
    int n;
    vector<int> tree;

    void build(const vector<int>& arr, int idx, int l, int r){
        if(l == r){
            tree[idx] = arr[l];
            return;
        }
        int mid = (l+r)>>1;
        build(arr, idx*2, l, mid);
        build(arr, idx*2+1, mid+1, r);
        tree[idx] = tree[idx*2] + tree[idx*2+1]; // 例如区间和
    }

    void update(int idx, int l, int r, int pos, int val){
        if(l == r){
            tree[idx] = val;
            return;
        }
        int mid = (l+r)>>1;
        if(pos <= mid) update(idx*2, l, mid, pos, val);
        else update(idx*2+1, mid+1, r, pos, val);
        tree[idx] = tree[idx*2] + tree[idx*2+1];
    }

    int query(int idx, int l, int r, int ql, int qr){
        if(ql > r || qr < l) return 0;
        if(ql <= l && r <= qr) return tree[idx];
        int mid = (l+r)>>1;
        return query(idx*2,l,mid,ql,qr) + query(idx*2+1,mid+1,r,ql,qr);
    }
};

---

注意事项

• 线段树数组大小一般开4倍左右
  
• 可加懒惰标记支持区间修改
  
• 掌握递归边界处理技巧

---

9. 拓扑排序（Topological Sorting）

---

基本概念

• 一个有向无环图（DAG）顶点的线性序列，使得所有有向边 (u \to v)，都满足 (u) 在序列中位于 (v) 前面。
• 用于任务调度、依赖问题。

---

经典算法

• Kahn算法：维护入度为0的节点队列，反复出队，更新邻居入度。
• DFS算法：对未访问节点进行深度搜索，搜索结束后将结点压栈。

---

C++示例（Kahn算法）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> adj(n+1);
    vector<int> inDeg(n+1,0);
    for(int i=0;i<m;i++){
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        inDeg[v]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(inDeg[i]==0) q.push(i);
    vector<int> topo;
    while(!q.empty()){
        int u=q.front();q.pop();
        topo.push_back(u);
        for(auto v:adj[u]){
            if(--inDeg[v]==0) q.push(v);
        }
    }
    if((int)topo.size() != n)
        cout<<"Graph has cycle\n";
    else
        for(int x: topo)
            cout<<x<<" ";
    return 0;
}

---

注意事项

• 只适用无环图
  
• 判断有环很重要
  
• 可以解决课程安排、任务调度问题

---

10. 强连通分量（SCC）

---

基本概念

• 有向图中强连通分量指所有节点互相可达的最大子图。
• SCC分解将图拆成若干强连通子图。

---

常用算法

• Tarjan算法（基于DFS）
• Kosaraju算法（两次DFS）

---

Tarjan算法实现示例

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 100010;
vector<int> adj[MAXN];
int dfn[MAXN], low[MAXN], time_cnt;
bool inStack[MAXN];
stack<int> st;
int scc_id[MAXN], scc_cnt;

void tarjan(int u) {
    dfn[u] = low[u] = ++time_cnt;
    st.push(u);
    inStack[u] = true;
    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        scc_cnt++;
        int x;
        do {
            x = st.top();
            st.pop();
            inStack[x] = false;
            scc_id[x] = scc_cnt;
        } while (x != u);
    }
}

int main() {
    int n,m;
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
    }
    for (int i=1; i<=n; i++)
        if (!dfn[i]) tarjan(i);
    cout << scc_cnt << "\n";
    for(int i=1;i<=n;i++){
        cout << scc_id[i] << " ";
    }
    return 0;
}

---

应用

• 识别强连接子图
  
• 化简有向图
  
• 判负环、二分图、谢尔宾算法等

---

11. 树形DP

---

基本概念

• 树形DP是利用树的结构特点，自底向上解决问题的动态规划方法。
• 适用于计算子树信息，合并子节点信息。

---

一般流程

• 构建树的邻接表
• 通过DFS递归，先处理子节点
  
• 子节点的结果传递到父节点，计算父节点值

---

简单例子

计算树中每个节点的子树大小

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100010;
vector<int> adj[MAXN];
int sz[MAXN];

void dfs(int u, int f) {
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v != f) {
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
}

int main() {
    int n; cin >> n;
    for(int i=1;i<n;i++){
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, -1);

    for(int i=1; i<=n; i++){
        cout << sz[i] << " ";
    }
    return 0;
}

---

应用

• 计算子树大小、深度、距离和
  
• 树的路径性质统计
  
• 多种树形优化转换问题

---

12. 压状DP（状态压缩DP）

---

基本概念

• 状态压缩DP使用位掩码（二进制状态压缩）来表示组合状态，常用于组合数目有限的子集DP。
• 适合解决集合划分、TSP、匹配等问题。

---

基本思想

• 使用整数的二进制位表示元素是否被选中。
• DP数组以掩码下标，表示不同子集状态。
• 转移根据添加元素、合并子集等操作。

---

示例（求集合子集的和）

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int arr[20];
    for(int i=0;i<n;i++) cin>>arr[i];

    int maxMask = 1 << n;
    int dp[maxMask];
    dp[0] = 0;

    for(int mask = 1; mask < maxMask; mask++){
        dp[mask] = 0;
        for(int i = 0; i < n; i++){
            if(mask & (1 << i)){
                dp[mask] = dp[mask^(1 << i)] + arr[i];
                break;
            }
        }
    }

    for(int mask=0; mask < maxMask; mask++)
        cout << "Subset " << mask << " sum= " << dp[mask] << "\n";
    return 0;
}

---

应用

• 旅行商问题(TSP)
  
• 集合划分、匹配问题
  
• 状态空间复杂度受限，一般适合不超过20个状态

---

总结

以上是你需求中所有知识点的详细讲解与示例。每个主题都有典型的实现代码和注意点，适合用作复习或快速入门。

如果你需要针对某一具体问题进行更深入的代码分析或调优，欢迎继续提问！

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> arr = {1000, 5000, 10000, 5000, 1000};
    vector<int> values = arr;  // 复制

    // 1. 排序去重
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());

    // 2. 离散化映射
    for (int i = 0; i < (int)arr.size(); i++) {
        // 二分查找映射值
        int pos = (int)(lower_bound(values.begin(), values.end(), arr[i]) - values.begin());
        cout << "原值: " << arr[i] << " 离散化后为: " << pos + 1 << endl; // 位置+1 方便从1开始编号
    }

    return 0;
}