登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 业界 ›深入理解权值线段树

深入理解权值线段树

敛饺乖 前天 21:50
在上一篇探讨线段树的文章中 https://www.cnblogs.com/ofnoname/p/18625369，我们已经掌握了如何利用线段树高效处理数组区间查询与更新问题。这种经典线段树以数组下标为构建基础，完美解决了诸如区间求和、最值查询等典型场景。
而线段树结构还有另外一个用处：想象这样一个场景：我们需要实时统计当前集合中数值在[L,R]范围内的元素个数，或者快速查询第K大的数值。此时，权值线段树（Weight Segment Tree）便闪亮登场——它巧妙的维护基础从"数组下标"转换为"值域空间"，开辟了线段树应用的新维度。
与常规线段树不同，权值线段树面临两个独特挑战：首先，值域范围可能非常庞大（如[1,1e9]），使得传统的数组存储方式变得不切实际；其次，值域分布往往极其稀疏（仅有少量离散点被使用）。这促使我们放弃静态的数组表示法，转而采用动态节点生成的指针表示法，只在必要时创建节点，从而大幅节省空间。
权值线段树的基本原理

从下标维护到值域维护

传统线段树维护的是数组下标区间的信息，例如：

  • 区间和：\(\text{sum}(l, r) = \sum_{i=l}^{r} a_i\)
  • 区间最大值：\(\max(l, r) = \max(a_l, a_{l+1}, \dots, a_r)\)
而权值线段树（也称为值域线段树）维护的是数值的值域区间，例如：

  • 数值在 \([L, R]\) 范围内的出现次数
  • 整个集合中第 \(K\) 小的数
二叉树的表示方法

线段树是一个二叉树。由于权值线段树的值域可能非常大（如 \([1, 10^9]\)），甚至稀疏（仅有少量数值被插入），我们无法像传统线段树那样使用固定数组存储，而必须采用动态节点生成的指针表示法：
数组表示法（静态存储）


  • 适用于紧凑且值域较小的情况（如 \([1, N]\)，\(N \leq 10^6\)）
  • 类似堆式存储，节点 \(i\) 的左儿子是 \(2i\)，右儿子是 \(2i+1\)
  • 缺点：如果值域很大（如 \([1, 10^9]\)），空间爆炸
指针表示法（动态开点）


  • 仅在实际插入数值时才创建对应的节点
  • 每个节点存储：

    • 值域区间 \([l, r]\)
    • 统计信息（如出现次数 \(cnt\)，区间和 \(sum\)）
    • 左儿子 left 和右儿子 right 指针

  • 优点：节省空间，仅 \(O(M \log N)\)，其中 \(M\) 是操作次数，\(N\) 是值域范围
关键点：

  • 只有被访问过的区间才会生成节点
  • 父节点的信息由其子节点汇总（如 cnt = left->cnt + right->cnt）
1.png

权值线段树的实现细节

节点结构设计

我们采用面向对象的方式定义权值线段树的节点结构：
  1. struct Node {
  2.     int l, r;       // 值域区间[l,r]
  3.     int cnt;        // 该值域内数字出现次数
  4.     int sum;        // 该值域内数字的和（可选）
  5.     Node *left, *right; // 左右子节点指针
  7.     Node(int _l, int _r) : l(_l), r(_r), cnt(0), sum(0), left(nullptr), right(nullptr) {}
  8. };
复制代码
核心操作：插入数值

每次插入一个数x时，我们从根节点开始递归更新线段树：

  • 如果当前节点的值域区间[l,r]不包含x，直接返回
  • 如果当前节点是叶子节点（l==r），更新统计信息
  • 否则递归处理左右子树，并动态创建不存在的子节点
  1. void insert(Node* root, int x) {
  2.     if (x < root->l || x > root->r) return;
  3.    
  4.     if (root->l == root->r) {
  5.         root->cnt++;
  6.         root->sum += x;
  7.         return;
  8.     }
  9.    
  10.     int mid = root->l + (root->r - root->l) / 2;
  11.     if (x <= mid) {
  12.         if (!root->left) root->left = new Node(root->l, mid);
  13.         insert(root->left, x);
  14.     } else {
  15.         if (!root->right) root->right = new Node(mid + 1, root->r);
  16.         insert(root->right, x);
  17.     }
  18.    
  19.     // 更新父节点统计信息
  20.     root->cnt = (root->left ? root->left->cnt : 0)
  21.               + (root->right ? root->right->cnt : 0);
  22.     root->sum = (root->left ? root->left->sum : 0)
  23.               + (root->right ? root->right->sum : 0);
  24. }
复制代码
查询值域统计

查询值域\([L,R]\)内的数字个数（类似地可以查询和、最大值等）：
  1. int query(Node* root, int L, int R) {
  2.     if (!root || R < root->l || L > root->r) return 0;
  3.     if (L <= root->l && root->r <= R) return root->cnt;
  4.     return query(root->left, L, R) + query(root->right, L, R);
  5. }
复制代码
2.png

查询第K小的数

利用权值线段树可以高效查询第K小的数：
  1. int kth(Node* root, int k) {
  2.     if (root->l == root->r) return root->l;
  3.    
  4.     int left_cnt = root->left ? root->left->cnt : 0;
  5.     if (k <= left_cnt) return kth(root->left, k);
  6.     return kth(root->right, k - left_cnt);
  7. }
复制代码
内存管理

由于采用动态开点，需要手动管理内存以避免泄漏：
  1. void clear(Node* root) {
  2.     if (!root) return;
  3.     clear(root->left);
  4.     clear(root->right);
  5.     delete root;
  6. }
复制代码
复杂度分析

时间复杂度分析

权值线段树的所有核心操作都遵循二叉树搜索模式，其时间复杂度主要取决于树的高度。设值域范围为\([1, N]\)：

  • 插入操作：每次插入需要从根节点递归到叶子节点，时间复杂度为\(O(\log N)\)
  • 查询操作：

    • 区间统计查询：\(O(\log N)\)
    • 第K小查询：\(O(\log N)\)

  • 删除操作（实现类似插入）：\(O(\log N)\)
值得注意的是，这里的 \(N\) 是值域范围，而非元素个数。当值域极大时（如 \([1,10^{18}]\)），可以通过离散化预处理将\(N\)降至元素数量级。
空间复杂度分析

权值线段树的空间消耗主要来自动态创建的节点：

  • 最坏情况：每个操作都访问全新的路径，需要创建\(O(\log N)\)个新节点
  • M次操作的空间消耗：\(O(M \log N)\)
  • 优化技巧：

    • 惰性删除：标记删除而非立即回收节点
    • 内存池预分配：减少动态内存分配开销

下表对比了不同情况下的空间使用：
场景空间复杂度说明静态数组实现\(O(N)\)值域较大时不可行动态开点（最坏）\(O(M \log N)\)每次操作都访问新路径动态开点（平均）\(O(K \log N)\)K为一个小于 M 的数与离散化的配合使用

对于极大值域但数据较为稀疏，若允许离线，可以先进行离散化处理：
  1. vector<int> nums = {5, 3, 7, 1e9}; // 原始数据
  2. sort(nums.begin(), nums.end());
  3. nums.erase(unique(nums.begin(), nums.end()), nums.end());
  5. // 建立值到排名的映射
  6. unordered_map<int, int> val2rank;
  7. for (int i = 0; i < nums.size(); ++i) {
  8.     val2rank[nums[i]] = i + 1; // 排名从1开始
  9. }
  11. // 此时权值线段树的值域可设为[1, nums.size()]
  12. WeightSegmentTree tree(1, nums.size());
复制代码
离散化后的优势：

  • 值域\(N\)从原始范围降至实际数据规模，此时可以改用区间线段树的四倍数组写法了。
  • 保持数值间的大小关系不变
  • 查询时需要先将查询边界值离散化
权值线段树 vs 平衡树

权值线段树和平衡树（如AVL树、红黑树）都可以解决以下常见问题：

  • 动态插入/删除数值
  • 查询第K小的数
  • 统计值域区间内的元素个数
  • 查询前驱/后继
但它们在实现方式和扩展性上存在本质差异：
功能实现方式对比
功能权值线段树实现方式平衡树实现方式插入/删除递归更新值域区间统计量通过旋转操作维持平衡第K小查询利用子树节点数二分搜索中序遍历或维护子树大小前驱/后继查询转化为值域边界查询直接查找相邻节点区间统计天然支持区间求和/最值需要额外维护统计信息优先选择权值线段树当：

  • 需要频繁查询第K小或区间统计
  • 值域范围可离散化处理
  • 需要可持久化或高维扩展
  • 数据离线处理（预先知道值域）
优先选择平衡树当：

  • 需要频繁插入/删除动态数据
  • 需要有序遍历或范围迭代
  • 处理非数值型数据或自定义比较
  • 内存限制严格

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
相关推荐
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
敛饺乖
前天 21:50

0

粉丝关注

9

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫