《算法导论》第 14 章 - 数据结构的扩张

        大家好！今天我们来深入学习《算法导论》第 14 章 —— 数据结构的扩张。这一章主要介绍了如何基于现有数据结构（如二叉搜索树）扩展出新的功能，以满足更复杂的问题需求。我们会从动态顺序统计树讲到区间树，每个知识点都会配上完整可运行的 C++ 代码，方便大家动手实践。

思维导图

14.1 动态顺序统计

        在很多场景中，我们不仅需要像普通 BST 那样查找元素，还需要知道元素在集合中的排名（秩），或者查找集合中第 i 小的元素。动态顺序统计树就是为了解决这类问题而设计的。

基本概念

  • 秩（Rank）：一个元素的秩是指该元素在集合的线性序中所处的位置（从 1 开始计数）
  • 第 i 个顺序统计量：集合中第 i 小的元素

数据结构设计

        动态顺序统计树在普通 BST 的基础上，为每个节点增加了一个size属性，表示以该节点为根的子树中包含的节点总数（包括自身）。

// 动态顺序统计树节点结构
struct Node {int key;         // 节点关键字int size;        // 以该节点为根的子树大小Node *left;      // 左孩子Node *right;     // 右孩子Node *parent;    // 父节点// 构造函数Node(int k) : key(k), size(1), left(nullptr), right(nullptr), parent(nullptr) {}
};

核心操作实现

更新节点大小

当树的结构发生变化（插入或删除节点）时，需要更新相关节点的size属性：

// 更新节点的size（等于左子树size + 右子树size + 1）
void updateSize(Node *node) {if (node != nullptr) {node->size = 1;  // 自身if (node->left != nullptr) {node->size += node->left->size;}if (node->right != nullptr) {node->size += node->right->size;}}
}
查找第 i 个元素
// 查找以node为根的子树中第i个最小元素（1-based）
Node* select(Node *node, int i) {if (node == nullptr) return nullptr;  // 空树或i超出范围// 左子树的节点数int leftSize = (node->left != nullptr) ? node->left->size : 0;if (i == leftSize + 1) {// 当前节点就是第i个元素return node;} else if (i <= leftSize) {// 第i个元素在左子树中return select(node->left, i);} else {// 第i个元素在右子树中，注意要调整i的值return select(node->right, i - (leftSize + 1));}
}

计算元素的秩
// 计算x在以root为根的树中的秩
int rank(Node *root, Node *x) {// x的左子树大小 + 1（自身）int r = (x->left != nullptr) ? x->left->size + 1 : 1;Node *y = x;// 向上追溯到根节点while (y != root) {if (y == y->parent->right) {// 如果y是其父节点的右孩子，则需要加上父节点左子树大小 + 1（父节点自身）r += (y->parent->left != nullptr) ? y->parent->left->size + 1 : 1;}y = y->parent;}return r;
}
插入操作

插入操作在普通 BST 插入的基础上，需要从新插入的节点向上更新所有祖先的size属性：

// 向以root为根的树中插入关键字key，返回新的根节点
Node* insert(Node *root, int key) {// 普通BST插入逻辑Node *parent = nullptr;Node **current = &root;while (*current != nullptr) {parent = *current;(*current)->size++;  // 沿途节点size加1if (key < (*current)->key) {current = &((*current)->left);} else {current = &((*current)->right);}}*current = new Node(key);(*current)->parent = parent;return root;  // 返回新的根节点
}
删除操作

        删除操作相对复杂，需要先找到要删除的节点，执行删除（考虑三种情况：叶子节点、只有一个孩子、有两个孩子），然后更新相关节点的size属性：

// 查找关键字为key的节点
Node* find(Node *root, int key) {Node *current = root;while (current != nullptr && current->key != key) {if (key < current->key) {current = current->left;} else {current = current->right;}}return current;
}// 找到以node为根的树中的最小值节点
Node* minimum(Node *node) {while (node->left != nullptr) {node = node->left;}return node;
}// 替换子树
void transplant(Node *&root, Node *u, Node *v) {if (u->parent == nullptr) {root = v;  // u是根节点} else if (u == u->parent->left) {u->parent->left = v;  // u是左孩子} else {u->parent->right = v;  // u是右孩子}if (v != nullptr) {v->parent = u->parent;  // 更新v的父节点}
}// 从树中删除节点z，返回新的根节点
Node* deleteNode(Node *root, Node *z) {if (z == nullptr) return root;  // 节点不存在Node *y = nullptr;Node *x = nullptr;// 确定要删除的实际节点yif (z->left == nullptr || z->right == nullptr) {y = z;} else {y = minimum(z->right);  // 找到后继节点}// 确定y的孩子xif (y->left != nullptr) {x = y->left;} else {x = y->right;}// 更新x的父节点if (x != nullptr) {x->parent = y->parent;}// 替换ytransplant(root, y, x);// 如果y不是z，则将y的内容复制到zif (y != z) {z->key = y->key;}// 更新受影响节点的sizeNode *p = y->parent;while (p != nullptr) {updateSize(p);p = p->parent;}delete y;  // 释放内存return root;
}

综合案例：动态顺序统计树的应用

下面是一个完整的示例，展示了动态顺序统计树的各种操作：

#include <iostream>
#include <iomanip>
using namespace std;// 节点结构定义
struct Node {int key;int size;Node *left;Node *right;Node *parent;Node(int k) : key(k), size(1), left(nullptr), right(nullptr), parent(nullptr) {}
};// 辅助函数声明
void updateSize(Node *node);
Node* select(Node *node, int i);
int getRank(Node *root, Node *x);  // 重命名rank为getRank
Node* insert(Node *root, int key);
Node* find(Node *root, int key);
Node* minimum(Node *node);
void transplant(Node *&root, Node *u, Node *v);
Node* deleteNode(Node *root, Node *z);// 辅助函数实现
void updateSize(Node *node) {if (node != nullptr) {node->size = 1;if (node->left != nullptr) node->size += node->left->size;if (node->right != nullptr) node->size += node->right->size;}
}Node* select(Node *node, int i) {if (node == nullptr) return nullptr;int leftSize = (node->left != nullptr) ? node->left->size : 0;if (i == leftSize + 1) return node;else if (i <= leftSize) return select(node->left, i);else return select(node->right, i - (leftSize + 1));
}// 重命名rank为getRank，避免与标准库冲突
int getRank(Node *root, Node *x) {int r = (x->left != nullptr) ? x->left->size + 1 : 1;Node *y = x;while (y != root) {if (y == y->parent->right) {r += (y->parent->left != nullptr) ? y->parent->left->size + 1 : 1;}y = y->parent;}return r;
}Node* insert(Node *root, int key) {Node *parent = nullptr;Node **current = &root;while (*current != nullptr) {parent = *current;(*current)->size++;if (key < (*current)->key) current = &((*current)->left);else current = &((*current)->right);}*current = new Node(key);(*current)->parent = parent;return root;
}Node* find(Node *root, int key) {Node *current = root;while (current != nullptr && current->key != key) {if (key < current->key) current = current->left;else current = current->right;}return current;
}Node* minimum(Node *node) {while (node->left != nullptr) node = node->left;return node;
}void transplant(Node *&root, Node *u, Node *v) {if (u->parent == nullptr) root = v;else if (u == u->parent->left) u->parent->left = v;else u->parent->right = v;if (v != nullptr) v->parent = u->parent;
}Node* deleteNode(Node *root, Node *z) {if (z == nullptr) return root;Node *y = nullptr, *x = nullptr;if (z->left == nullptr || z->right == nullptr) y = z;else y = minimum(z->right);if (y->left != nullptr) x = y->left;else x = y->right;if (x != nullptr) x->parent = y->parent;transplant(root, y, x);if (y != z) z->key = y->key;Node *p = y->parent;while (p != nullptr) {updateSize(p);p = p->parent;}delete y;return root;
}// 中序遍历打印树（用于调试）
void inorder(Node *node) {if (node != nullptr) {inorder(node->left);cout << node->key << "(" << node->size << ") ";inorder(node->right);}
}int main() {Node *root = nullptr;// 插入一些元素int keys[] = {15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9};for (int key : keys) {root = insert(root, key);}cout << "树的中序遍历（带size）: ";inorder(root);cout << endl << endl;// 测试select操作for (int i = 1; i <= 11; i++) {Node *node = select(root, i);if (node != nullptr) {cout << "第" << i << "小的元素是: " << node->key << endl;}}cout << endl;// 测试rank操作，使用重命名后的getRankint testKeys[] = {15, 7, 20, 2};for (int key : testKeys) {Node *node = find(root, key);if (node != nullptr) {cout << "元素" << key << "的秩是: " << getRank(root, node) << endl;}}cout << endl;// 测试删除操作int delKey = 6;Node *delNode = find(root, delKey);if (delNode != nullptr) {cout << "删除元素" << delKey << "后，树的中序遍历: ";root = deleteNode(root, delNode);inorder(root);cout << endl << endl;// 再次测试select和rank操作cout << "删除后，第3小的元素是: " << select(root, 3)->key << endl;cout << "删除后，元素7的秩是: " << getRank(root, find(root, 7)) << endl;}return 0;
}

运行结果：

14.2 如何扩张数据结构

        扩张数据结构是指在现有数据结构的基础上添加新的信息和操作，以解决特定问题。以下是扩张数据结构的一般步骤：

  1. 选择基础数据结构：通常选择能高效支持基本操作的数据结构（如 BST、红黑树等）

  2. 确定要添加的信息：根据问题需求，确定需要在原有结构上添加哪些额外信息

  3. 验证新信息可以被维护：确保在基础数据结构的所有操作（插入、删除等）执行后，新添加的信息仍能被正确维护

  4. 实现新的操作：基于添加的信息，实现解决问题所需的新操作

设计原则

  • 局部性：新信息应能通过节点本身及其子节点的信息计算得出
  • 高效性：维护新信息的额外时间不应显著增加原有操作的时间复杂度
  • 必要性：只添加解决问题所必需的信息，避免冗余

动态顺序统计树就是一个典型的扩张例子：

  • 基础数据结构：二叉搜索树（BST）
  • 添加的信息：每个节点的size属性
  • 维护方式：插入 / 删除时更新路径上所有节点的size
  • 新操作：select和rank

14.3 区间树

区间树是一种支持区间查询的数据结构，它能高效地找出与给定区间重叠的所有区间。

区间表示与问题定义

  • 区间通常表示为[low, high]，其中low是区间的起点，high是区间的终点
  • 两个区间[a,b]和[c,d]重叠当且仅当a ≤ d且c ≤ b
  • 区间树的主要操作：插入区间、删除区间、查询所有与给定区间重叠的区间

数据结构设计

区间树基于 BST 扩展而来，每个节点存储：

  • 一个区间[low, high]
  • 以区间的low为关键字构建 BST
  • 额外添加max属性，表示以该节点为根的子树中所有区间的high的最大值

// 区间结构
struct Interval {int low;   // 区间起点int high;  // 区间终点Interval(int l, int h) : low(l), high(h) {}
};// 区间树节点结构
struct IntervalNode {Interval *interval;  // 区间int max;             // 子树中最大的high值IntervalNode *left;  // 左孩子IntervalNode *right; // 右孩子IntervalNode *parent;// 父节点// 构造函数IntervalNode(int low, int high) : interval(new Interval(low, high)), max(high), left(nullptr), right(nullptr), parent(nullptr) {}
};

区间树的类图：

@startuml
class Interval {- int low- int high+ Interval(int l, int h)
}class IntervalNode {- Interval* interval- int max- IntervalNode* left- IntervalNode* right- IntervalNode* parent+ IntervalNode(int low, int high)
}IntervalNode "1" *-- "1" Interval : contains
IntervalNode "1" --* "0..1" IntervalNode : left child
IntervalNode "1" --* "0..1" IntervalNode : right child
@enduml

核心操作实现

更新 max 值
// 更新节点的max值（自身high和左右子树max中的最大值）
void updateMax(IntervalNode *node) {if (node != nullptr) {node->max = node->interval->high;  // 自身区间的highif (node->left != nullptr && node->left->max > node->max) {node->max = node->left->max;}if (node->right != nullptr && node->right->max > node->max) {node->max = node->right->max;}}
}
插入操作
// 向区间树中插入新区间
IntervalNode* insertInterval(IntervalNode *root, int low, int high) {// 普通BST插入（以low为关键字）IntervalNode *parent = nullptr;IntervalNode **current = &root;while (*current != nullptr) {parent = *current;// 更新当前节点的max值if (high > (*current)->max) {(*current)->max = high;}// 继续查找插入位置if (low < (*current)->interval->low) {current = &((*current)->left);} else {current = &((*current)->right);}}// 创建新节点*current = new IntervalNode(low, high);(*current)->parent = parent;return root;
}
区间查询操作

查询所有与给定区间[low, high]重叠的区间：

// 检查两个区间是否重叠
bool overlap(Interval *a, Interval *b) {return a->low <= b->high && b->low <= a->high;
}// 查询与target重叠的所有区间
void queryOverlapping(IntervalNode *node, Interval *target, vector<Interval*>& result) {if (node == nullptr) return;// 先检查左子树if (node->left != nullptr && node->left->max >= target->low) {queryOverlapping(node->left, target, result);}// 检查当前节点if (overlap(node->interval, target)) {result.push_back(node->interval);}// 再检查右子树if (node->right != nullptr && node->interval->low <= target->high) {queryOverlapping(node->right, target, result);}
}

查询算法的流程图：

删除操作

删除操作需要在删除节点后更新相关节点的max值：

// 查找最小值节点（最左节点）
IntervalNode* intervalMinimum(IntervalNode *node) {while (node->left != nullptr) {node = node->left;}return node;
}// 区间树的替换操作
void intervalTransplant(IntervalNode *&root, IntervalNode *u, IntervalNode *v) {if (u->parent == nullptr) {root = v;} else if (u == u->parent->left) {u->parent->left = v;} else {u->parent->right = v;}if (v != nullptr) {v->parent = u->parent;}
}// 删除区间节点
IntervalNode* deleteIntervalNode(IntervalNode *root, IntervalNode *z) {if (z == nullptr) return root;IntervalNode *y = nullptr;IntervalNode *x = nullptr;// 确定要删除的节点yif (z->left == nullptr || z->right == nullptr) {y = z;} else {y = intervalMinimum(z->right);}// 确定y的孩子xif (y->left != nullptr) {x = y->left;} else {x = y->right;}// 更新x的父节点if (x != nullptr) {x->parent = y->parent;}// 替换yintervalTransplant(root, y, x);// 如果y不是z，则复制y的内容到zif (y != z) {// 保存z的区间指针以便后续释放Interval *oldInterval = z->interval;// 复制y的内容到zz->interval = y->interval;z->max = y->max;// 释放y的区间（因为已经转移给z了）y->interval = nullptr;delete oldInterval;}// 更新受影响节点的max值IntervalNode *p = y->parent;while (p != nullptr) {updateMax(p);p = p->parent;}// 释放y的内存if (y->interval != nullptr) {delete y->interval;}delete y;return root;
}// 查找包含特定区间的节点
IntervalNode* findIntervalNode(IntervalNode *root, int low, int high) {IntervalNode *current = root;while (current != nullptr) {if (current->interval->low == low && current->interval->high == high) {return current;} else if (low < current->interval->low) {current = current->left;} else {current = current->right;}}return nullptr;
}

综合案例：区间树的应用

下面是一个完整的区间树应用示例：

#include <iostream>
#include <vector>
using namespace std;// 区间结构定义
struct Interval {int low;int high;Interval(int l, int h) : low(l), high(h) {}
};// 区间树节点结构定义
struct IntervalNode {Interval *interval;int max;IntervalNode *left;IntervalNode *right;IntervalNode *parent;IntervalNode(int low, int high) : interval(new Interval(low, high)), max(high), left(nullptr), right(nullptr), parent(nullptr) {}
};// 辅助函数声明
void updateMax(IntervalNode *node);
IntervalNode* insertInterval(IntervalNode *root, int low, int high);
bool overlap(Interval *a, Interval *b);
void queryOverlapping(IntervalNode *node, Interval *target, vector<Interval*>& result);
IntervalNode* intervalMinimum(IntervalNode *node);
void intervalTransplant(IntervalNode *&root, IntervalNode *u, IntervalNode *v);
IntervalNode* deleteIntervalNode(IntervalNode *root, IntervalNode *z);
IntervalNode* findIntervalNode(IntervalNode *root, int low, int high);// 辅助函数实现
void updateMax(IntervalNode *node) {if (node != nullptr) {node->max = node->interval->high;if (node->left != nullptr && node->left->max > node->max) {node->max = node->left->max;}if (node->right != nullptr && node->right->max > node->max) {node->max = node->right->max;}}
}IntervalNode* insertInterval(IntervalNode *root, int low, int high) {IntervalNode *parent = nullptr;IntervalNode **current = &root;while (*current != nullptr) {parent = *current;if (high > (*current)->max) {(*current)->max = high;}if (low < (*current)->interval->low) {current = &((*current)->left);} else {current = &((*current)->right);}}*current = new IntervalNode(low, high);(*current)->parent = parent;return root;
}bool overlap(Interval *a, Interval *b) {return a->low <= b->high && b->low <= a->high;
}void queryOverlapping(IntervalNode *node, Interval *target, vector<Interval*>& result) {if (node == nullptr) return;if (node->left != nullptr && node->left->max >= target->low) {queryOverlapping(node->left, target, result);}if (overlap(node->interval, target)) {result.push_back(node->interval);}if (node->right != nullptr && node->interval->low <= target->high) {queryOverlapping(node->right, target, result);}
}IntervalNode* intervalMinimum(IntervalNode *node) {while (node->left != nullptr) {node = node->left;}return node;
}void intervalTransplant(IntervalNode *&root, IntervalNode *u, IntervalNode *v) {if (u->parent == nullptr) {root = v;} else if (u == u->parent->left) {u->parent->left = v;} else {u->parent->right = v;}if (v != nullptr) {v->parent = u->parent;}
}IntervalNode* deleteIntervalNode(IntervalNode *root, IntervalNode *z) {if (z == nullptr) return root;IntervalNode *y = nullptr;IntervalNode *x = nullptr;if (z->left == nullptr || z->right == nullptr) {y = z;} else {y = intervalMinimum(z->right);}if (y->left != nullptr) {x = y->left;} else {x = y->right;}if (x != nullptr) {x->parent = y->parent;}intervalTransplant(root, y, x);if (y != z) {Interval *oldInterval = z->interval;z->interval = y->interval;z->max = y->max;y->interval = nullptr;delete oldInterval;}IntervalNode *p = y->parent;while (p != nullptr) {updateMax(p);p = p->parent;}if (y->interval != nullptr) {delete y->interval;}delete y;return root;
}IntervalNode* findIntervalNode(IntervalNode *root, int low, int high) {IntervalNode *current = root;while (current != nullptr) {if (current->interval->low == low && current->interval->high == high) {return current;} else if (low < current->interval->low) {current = current->left;} else {current = current->right;}}return nullptr;
}// 打印区间
void printInterval(Interval *interval) {cout << "[" << interval->low << ", " << interval->high << "]";
}int main() {IntervalNode *root = nullptr;// 插入一些区间root = insertInterval(root, 15, 20);root = insertInterval(root, 10, 30);root = insertInterval(root, 17, 19);root = insertInterval(root, 5, 20);root = insertInterval(root, 12, 15);root = insertInterval(root, 30, 40);// 查询与[14, 16]重叠的区间Interval *target = new Interval(14, 16);vector<Interval*> result;queryOverlapping(root, target, result);cout << "与区间[14, 16]重叠的区间有：" << endl;for (Interval *interval : result) {printInterval(interval);cout << " ";}cout << endl << endl;// 删除区间[10, 30]IntervalNode *nodeToDelete = findIntervalNode(root, 10, 30);if (nodeToDelete != nullptr) {root = deleteIntervalNode(root, nodeToDelete);cout << "删除区间[10, 30]后，与[14, 16]重叠的区间有：" << endl;result.clear();queryOverlapping(root, target, result);for (Interval *interval : result) {printInterval(interval);cout << " ";}cout << endl;}// 释放内存delete target;// 完整的内存释放还需要遍历树删除所有节点，这里简化处理return 0;
}

运行结果：

思考题

  1. 如何在动态顺序统计树上实现范围查询（即查找所有关键字在 [a, b] 之间的元素），并计算该范围内元素的个数？

  2. 试设计一种基于红黑树的区间树，确保所有操作（插入、删除、查询）都能在 O (log n) 时间内完成。

  3. 如何扩展区间树，使其能高效支持 “查找包含点 x 的所有区间” 这一操作？

  4. 设计一种数据结构，支持在 O (1) 时间内查找最小值，在 O (log n) 时间内插入和删除元素，以及在 O (log n) 时间内查找第 i 小的元素。

本章注记

  • 数据结构的扩张是解决复杂问题的重要技术，其核心在于找到合适的基础结构和需要添加的信息
  • 红黑树常被用作扩张的基础结构，因为它能在 O (log n) 时间内支持插入、删除等操作
  • 除了本章介绍的动态顺序统计树和区间树，还有许多其他重要的扩张数据结构，如：
    • 线段树：用于处理区间上的范围查询和更新
    • 二叉索引树（Fenwick 树）：高效支持前缀和查询和点更新
    • 平衡二叉搜索树：如 AVL 树、Splay 树等，在 BST 基础上添加了平衡条件

        希望本章内容能帮助大家理解数据结构扩张的思想和方法。通过动手实现这些数据结构，相信大家能更深入地掌握其中的原理和技巧。如果有任何疑问或建议，欢迎在评论区留言讨论！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/news/918158.shtml
繁体地址，请注明出处：http://hk.pswp.cn/news/918158.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Vue 3.6 Vapor模式完全指南：告别虚拟DOM，性能飞跃式提升

Vue 3.6 Vapor模式完全指南：告别虚拟DOM，性能飞跃式提升

什么是 Vapor 定义: Vue 3.6 新增的编译/渲染模式&#xff0c;不再构建/对比虚拟 DOM&#xff0c;而是将模板编译为“直达 DOM 的更新代码”&#xff0c;以更低内存与更快更新获得接近 Solid/Svelte 的性能。特点更快: 跳过 VDOM 创建与 diff&#xff0c;直接按依赖精准更新。…
阅读更多...
Java类和对象课上练习题目设计

Java类和对象课上练习题目设计

我们可以做一个简易银行账户类&#xff0c;支持存款、取款、查看交易记录等。 示例&#xff1a;BankAccount 类 java 复制 编辑 public class BankAccount { private String accountNumber; // 账号 private String ownerName; // 开户人姓名 private double balance; …
阅读更多...
Python数据双效处理：同步转换与换算的高级技术与工程实践

Python数据双效处理：同步转换与换算的高级技术与工程实践

引言&#xff1a;转换与换算在现代数据处理中的核心价值在大数据与实时处理需求激增的时代&#xff0c;高效的数据处理方案成为核心竞争力。根据2025年Python数据工程调查报告&#xff1a;75%的数据处理任务需要同时执行转换和换算操作优化良好的双效处理可提升3-8倍性能关键应…
阅读更多...
Go语言实战案例:文件上传服务

Go语言实战案例:文件上传服务

在 Web 开发中&#xff0c;文件上传 是常见需求&#xff0c;例如头像上传、文档存储、图片分享等功能。Go 语言的标准库 net/http 已经内置了对 multipart/form-data 类型的支持&#xff0c;能让我们轻松构建一个文件上传服务。本文将带你实现一个可运行的文件上传接口&#xf…
阅读更多...
【Lua】常用的库

【Lua】常用的库

os库&#xff1a;os.time() -- 输出当前时间的时间戳 os.time({year 2014, month 8, day 14}) -- 获取指定时间的时间戳local nowTime os.date("*t") -- 以表的形式获取当前的时间信息for k,v in pairs(nowTime) doprint(k,v) end--以上for循环示例输出 {year 2…
阅读更多...
Mac上安装和配置MySQL（使用Homebrew安装MySQL 8.0）

Mac上安装和配置MySQL（使用Homebrew安装MySQL 8.0）

在Mac上安装MySQL是一个简单高效的过程&#xff0c;尤其是通过Homebrew这一强大的包管理工具。本文将详细介绍如何在macOS 15.6系统中使用Homebrew安装MySQL 8.0版本&#xff0c;并完成基本配置&#xff0c;帮助您快速启动并安全使用MySQL。1. 安装Homebrew&#xff08;若未安装…
阅读更多...
【Datawhale AI夏令营】从Baseline到SOTA：深度剖析金融问答RAG管道优化之路

【Datawhale AI夏令营】从Baseline到SOTA：深度剖析金融问答RAG管道优化之路

从Baseline到SOTA&#xff1a;深度剖析金融问答RAG管道优化之路 引言 检索增强生成&#xff08;Retrieval-Augmented Generation, RAG&#xff09;已成为构建知识密集型AI应用的事实标准 1。然而&#xff0c;从一个简单的“hello world”级别的RAG&#xff0c;进化到一个能在竞…
阅读更多...
AI鉴伪技术：守护数字时代的真实性防线

AI鉴伪技术：守护数字时代的真实性防线

文章目录一、引言&#xff1a;AI伪造技术的“数字病毒”与鉴伪技术的“免疫疫苗”二、合合信息三大AI鉴伪技术解析2.1 人脸视频鉴伪技术&#xff1a;毫秒级击穿“数字假面”2.1.1 技术突破&#xff1a;从“像素级标记”到“多模态交叉验证”2.2 AIGC图像鉴别技术&#xff1a;让…
阅读更多...
论文reading学习记录7 - daily - ViP3D

论文reading学习记录7 - daily - ViP3D

文章目录前言一、题目和摘要二、引言三、相关工作四、方法五、训练前言 开冲&#xff0c;清华大学的&#xff0c;带HDmap的端论文&#xff0c;用的Query&#xff0c;和UniAD一样。 一、题目和摘要 ViP3D: End-to-end Visual Trajectory Prediction via 3D Agent Queries ViP3…
阅读更多...
Java学习第一百零九部分——Jenkins（一）

Java学习第一百零九部分——Jenkins（一）

目录 一、前言简介 二、核心价值与优势 三、关键概念 四、下载安装与配置 五、总结归纳概述 一、前言简介 Jenkins 是一个开源的、基于 Java 的自动化服务器。它的核心使命是实现持续集成和持续交付。简单来说&#xff0c;Jenkins 是一个强大的工具&#xff0c;用于自动化…
阅读更多...
微算法科技(NASDAQ：MLGO)使用循环QSC和QKD的量子区块链架构，提高交易安全性和透明度

微算法科技(NASDAQ：MLGO)使用循环QSC和QKD的量子区块链架构，提高交易安全性和透明度

随着量子计算技术的快速发展&#xff0c;传统区块链所依赖的加密算法面临着被破解的潜在风险。量子计算的强大计算能力可能会在未来打破现有加密体系的安全性&#xff0c;从而对区块链中的交易数据造成威胁。为了应对这一挑战&#xff0c;将量子技术与区块链相结合成为了必然的…
阅读更多...
MyBatis SQL映射与动态SQL：构建灵活高效的数据访问层 MyBatis SQL映射与动态SQL：构建灵活高效的数据访问层

MyBatis SQL映射与动态SQL：构建灵活高效的数据访问层 MyBatis SQL映射与动态SQL：构建灵活高效的数据访问层

&#x1f504; MyBatis SQL映射与动态SQL&#xff1a;构建灵活高效的数据访问层 &#x1f680; 引言&#xff1a;动态SQL是MyBatis框架的核心优势之一&#xff0c;它让我们能够根据不同条件动态构建SQL语句&#xff0c;避免了传统JDBC中大量的字符串拼接。本文将深入解析MyBati…
阅读更多...
v-model双向绑定指令

v-model双向绑定指令

文章目录前言v-model.lazy 延迟同步v-model.trim 去掉空格前言 v-model指令是Vue.js中实现双向数据绑定的一种重要机制。它可以将表单控件的值与Vue.js实例中的数据进行双向绑定&#xff0c;即当表单控件的值发生变化时&#xff0c;Vue.js实例中的数据也会随之更新&#xff0c…
阅读更多...
电脑IP地址是“169.254.x.x”而无法上网的原因

电脑IP地址是“169.254.x.x”而无法上网的原因

一、核心原因&#xff1a;自动私有 IP 地址&#xff08;APIPA&#xff09;的启用APIPA 机制&#xff1a;这是 Windows 等操作系统内置的一种 “备用方案”。当电脑设置为 “自动获取 IP 地址”&#xff08;通过 DHCP 协议&#xff09;&#xff0c;但无法从路由器、光猫等网络设…
阅读更多...
单片机存储区域详解

单片机存储区域详解

目录 单片机内存区域划分 boot引脚启动介绍 1. boot引脚的三大启动区域介绍 1.用户闪存（User Flash） - 最常用模式 2. 系统存储区（System Memory） - 出厂预置Bootloader区 3. 内置SRAM启动（RAM Boot） - 特殊调试模式 2.用户闪存（User Flash）内存管理详解 一、用户闪存中…
阅读更多...
Go语言实战案例:简易JSON数据返回

Go语言实战案例:简易JSON数据返回

在现代 Web 应用中&#xff0c;JSON 已成为前后端通信的主流数据格式。Go 语言标准库内置对 JSON 的良好支持&#xff0c;只需少量代码就能返回结构化的 JSON 响应。本篇案例将手把手带你完成一个「返回 JSON 数据的 HTTP 接口」&#xff0c;帮助你理解如何用 Go 语言实现后端服…
阅读更多...
扣子Coze中的触发器实现流程自动化-实现每日新闻卡片式推送

扣子Coze中的触发器实现流程自动化-实现每日新闻卡片式推送

基础知识 什么是触发器/能做什么 Triggers 智能体设置触发器&#xff08;Triggers&#xff09;&#xff0c;使智能体在特定时间或接收到特定事件时自动执行任务。为什么需要触发器&#xff1f;实操步骤 第1步&#xff1a;打开一个智能体编辑页第2步&#xff1a;技能 - 触发器 -…
阅读更多...
GitCode 7月：小程序积分商城更名成长中心、「探索智能仓颉！Cangjie Magic 体验有奖征文活动」圆满收官、深度对话栏目持续热播

GitCode 7月：小程序积分商城更名成长中心、「探索智能仓颉！Cangjie Magic 体验有奖征文活动」圆满收官、深度对话栏目持续热播

运营情况总结 &#x1f389; 截至7月底&#xff0c;GitCode 这个热闹的开发者社区&#xff0c;已经聚集了 656 万位开发者小伙伴啦&#xff01; &#x1f4bb; 产品&#xff1a;小程序积分商城更名为成长中心啦&#xff0c;更多功能将陆续上线。 &#x1f31f; G-Star&#xff…
阅读更多...
机器学习之支持向量机(原理)

机器学习之支持向量机(原理)

目录 摘要 一、概述 二、SVM算法定义 1.超平⾯最⼤间隔介绍 2.硬间隔和软间隔 1.硬间隔分类 2. 软间隔分类 三、SVM算法原理 1 定义输⼊数据 2 线性可分⽀持向量机 3 SVM的计算过程与算法步骤 四、核函数 五、SVM算法api介绍 1. 核心参数说明 2. 主要方法 3. 重…
阅读更多...
【Unity3D实例-功能-跳跃】角色跳跃

【Unity3D实例-功能-跳跃】角色跳跃

今天&#xff0c;我们来聊聊 Unity 里最常打交道的动作之一——角色跳跃。无论是横版闯关还是 3D 跑酷&#xff0c;跳跃都是让角色“活”起来的核心操作。在 Unity 里&#xff0c;几行脚本就能让角色一蹬而起、稳稳落地。下面&#xff0c;就让我们一起把这个“弹跳感”亲手做出…
阅读更多...
最新文章

Copyright @ 2022~2023