深入理解lowbit算法

小蓝 • 2024-12-05 10:21 • 编程

一、lowbit算法

lowbit算法，也叫做lowbit函数，是一种运用位运算快速计算数列中二进制末尾0个数的算法。它可以应用于树状数组、二叉树等数据结构中。

二、lowbit函数的作用

lowbit函数可以返回一个数二进制表示下最后一个1的位置到结尾有多少个0，即返回x的二进制表示中最后一个1对应的值。

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

比如说：对于6（110），lowbit(6)返回的是2（010）

三、与lowbit函数相关的应用

1、树状数组

树状数组，又称为二叉索引树，是一种可以动态维护数组前缀和的数据结构，由于其高效的查询和修改效率，在竞赛和数据结构中得到广泛应用。

使用树状数组实现前缀和用到了lowbit函数，对于一个数组a，其对应的树状数组是树的节点代表区间的和，节点编号对应区间的结束位置。

int n;
int c[N], a[N];
int lowbit(int x) { return x & (-x); } //lowbit函数

void update(int x, int k)//更新操作
{
    for(; x <= n; x += lowbit(x))
        c[x] += k;
}

int getSum(int x)//求区间和操作
{
    int res = 0;
    for(; x; x -= lowbit(x))
        res += c[x];
    return res;
}

2、二叉树

用树的形式来存储有层级关系的数据结构，即树形结构。lowbit算法可以用于计算二叉树中节点的数量、前k小的节点等问题。

例如：在二叉树中查询第k小的节点，可以先用lowbit函数计算该节点所处的层级，然后利用树的深度优先遍历或广度优先遍历统计每一层的节点数量。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int countNodes(TreeNode* root) {
    if (!root) return 0;
    int leftDepth = 0, rightDepth = 0;
    TreeNode* leftNode = root->left, *rightNode = root->right;
    while (leftNode) leftDepth++, leftNode = leftNode->left;//统计左子树的深度
    while (rightNode) rightDepth++, rightNode = rightNode->right;//统计右子树的深度
    if (leftDepth == rightDepth) return pow(2, leftDepth) - 1;//如果左右子树深度相等，说明是满二叉树，直接返回节点数量
    return countNodes(root->left) + countNodes(root->right) + 1;//否则递归计算左右子树的节点数
}

3、离散化

离散化指的是将一个数列中的数映射到另一个值域内的过程，常用于解决范围较大，数值较多的排序问题。

而在离散化时，lowbit函数主要用于计算数字的二进制末尾0的个数，用于压缩表格，以便于优化表格的存储和查询效率。

const int N = 100010;
int n;
int a[N], tr[N];//tr数组存放树状数组

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

void add(int x, int c)//在x位置加c
{
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x)//求前x项的和
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int find(int x)//找到第k个元素
{
    int l = 1, r = n;
    while (l > 1;
        if(sum(mid) >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) add(i, a[i]);
    int k = find(5);//找到第5个元素
    printf("%d", k);//输出6
    return 0;
}

四、总结

lowbit算法是一种运用位运算快速计算数列中二进制末尾0个数的算法，可以应用于树状数组、二叉树等数据结构中。本文从lowbit算法的定义和作用入手，讲述了lowbit函数的具体实现方法，以及在树状数组、二叉树、离散化等场景中的应用。通过学习本文，相信读者对lowbit算法有了更深刻的理解，能够更好地应用于实际编程中。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/199381.html