至尊技术网

登录

标签搜索

搜索到 2 篇与的结果

C++实现位图（Bitmap）数据结构：位运算与空间优化的高效实践

C++实现位图（Bitmap）数据结构：位运算与空间优化的高效实践

在处理海量数据时，我们常常需要记录某些元素是否存在或是否被访问过。如果使用传统的布尔数组（bool[]），每个元素将占用至少1字节（8位），即使它的值只是true或false。当数据规模达到百万甚至亿级时，这种存储方式会带来巨大的内存开销。这时，位图（Bitmap）就成为一种极具优势的数据结构——它利用每一个比特（bit）来表示一个状态，从而将空间消耗降低为原来的1/8。位图的核心思想是：用一个二进制位表示一个整数的存在与否。例如，若想表示数字i是否出现过，只需将第i位设置为1。由于C++中没有直接按位寻址的语法，我们需要借助位运算和字节数组来手动实现这一机制。首先定义位图的基本结构：cpp class Bitmap { private: unsigned char* data; // 存储位图的字节数组 sizet numbits; // 总位数 sizet numbytes; // 所需字节数（向上取整）public: explicit Bitmap(sizet n) : numbits(n) { num_...

2025年12月01日

1 阅读

0 评论

主席树：可持久化线段树深度解析

主席树：可持久化线段树深度解析

主席树的核心概念主席树基于一个关键观察：当对线段树进行单点更新时，只有从根到该叶子节点的路径上的节点会被修改。这意味着每次更新只会影响O(log n)个节点，其他节点可以直接复用。"想象主席树就像一棵不断生长的树，"一位算法竞赛选手这样描述，"每次修改不是重新种一棵树，而是在原有树枝上添加新的分支。"可持久化实现原理主席树的可持久化通过以下步骤实现：节点复制：每次修改时，只复制需要改变的节点路径共享结构：未修改的子树直接指向原树的对应节点版本管理：每个版本维护一个独立的根节点指针 cpp struct Node { int l, r; // 左右子节点编号 int sum; // 区间统计值 } tree[MAXN * 20]; // 通常需要较大空间int roots[MAXN]; // 各版本的根节点 int node_cnt = 0; // 节点计数器主席树的典型应用1. 静态区间第k小查询这是主席树的经典应用场景。通过建立前缀权值线段树，可以在O(log n)时间内查询任意区间[l, r]的第k小元素。构建过程： 1. 离散化原...

2025年08月26日

51 阅读

0 评论

悠悠楠杉

34,382 文章数

92 评论量

人生倒计时

今日已经过去小时

这周已经过去天

本月已经过去天

今年已经过去个月

最新回复

强强强
2025-04-07

强的一批
jesse
2025-01-16

有whmcs接口吗？
sowxkkxwwk
2024-11-20

博主太厉害了！
zpzscldkea
2024-11-20

博主太厉害了！
bruvoaaiju
2024-11-14

博主太厉害了！

标签云

强的一批
有whmcs接口吗？
博主太厉害了！
博主太厉害了！
博主太厉害了！
怎么收藏这篇文章？
怎么收藏这篇文章？
想想你的文章写的特别好
想想你的文章写的特别好
不错不错，我喜欢看