首页 > 其他分享 >树状数组

树状数组

时间:2023-05-17 21:12:08浏览次数:29  
标签:数列 树状 int lowbit tree 数组

树状数组

树状数组(Binary Indexed Tree Fenwick Tree)是一种用于维护数列前缀和、区间和以及支持单点更新的数据结构。它能够在 \(O(\log n)\) 的时间复杂度内完成这些操作,比传统的前缀和算法更具有实用价值。树状数组也常常被用于解决数据结构中的某些问题,例如求逆序对、求数列中某一个数在排序后的排名等等。

基本思想

树状数组的核心思想是将原数列分解成若干个部分,对每一部分求出它们的和,并将这些和保存在一个数组中。数组中下标 \(i\) 保存的是数列以第 \(i\) 个元素结尾的、长度为 \(lowbit(i)\) 的区间和(其中 \(lowbit(i)\) 表示 \(i\) 的最末尾的一个1所代表的数值)。这样,我们只需要利用这个数组就可以很方便地计算数列任意前缀和以及区间和了。

实现细节

初始化

构造树状数组需要两个步骤:

  1. 定义一个数组 \(tree\),用于保存树状数组的节点值。
  2. 将原始输入数组中的每个数加入到树状数组中。
void init(int arr[], int tree[], int n) {
    for (int i = 1; i <= n; i++) {
        tree[i] += arr[i-1];
        int j = i + lowbit(i);
        if (j <= n) {
            tree[j] += tree[i];
        }
    }
}

lowbit操作

在树状数组的实现中,需要用到一个函数 \(lowbit(i)\),它表示 \(i\) 的最末尾的一个1所代表的数值。这个函数的实现方法比较简单,代码如下:

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

单点查询

单点查询函数的实现比较简单,只需要将查询的位置不断地向前跳转,即反复减去当前位置的 lowbit 值,直到位置为0为止。代码如下:

int query(int tree[], int i) {
    int res = 0;
    while (i > 0) {
        res += tree[i];
        i -= lowbit(i);
    }
    return res;
}

区间查询

区间查询函数是树状数组最重要的操作。通过利用前缀和计算公式 \(sum_{i,j} = sum_j - sum_{i-1}\),我们可以很容易地计算出数列 \([1,j]\) 和数列 \([1,i-1]\) 的前缀和,从而计算出数列 \([i,j]\) 的区间和。

int queryRange(int tree[], int l, int r) {
    return query(tree, r) - query(tree, l-1);
}

单点修改

单点修改操作需要将对应的节点值更新之后重新计算对应的每个节点的值,具体代码如下:

void update(int tree[], int i, int add, int n) {
    while (i <= n) {
        tree[i] += add;
        i += lowbit(i);
    }
}

总结

树状数组是一种非常实用的数据结构,它可以在 \(O(\log n)\) 的时间复杂度内完成数列前缀和、区间和以及支持单点更新等操作。

标签:数列,树状,int,lowbit,tree,数组
From: https://www.cnblogs.com/EraYes/p/17410284.html

相关文章

  • 2654. 使数组所有元素变成 1 的最少操作次数(c++,gcd性质)
    题目链接:2654.使数组所有元素变成1的最少操作次数方法一:计算最短的gcd为1的子数组解题思路本题目标:使得所有的数组元素都变为\(1\),通过求相邻元素\(gcd\)将其赋值给一方的方式;思路:若想操作数最少,那么就是不为\(1\)的数\(x\)和1求\(gcd\),即\(x=gcd(x,1)\),......
  • 正确使用PHP开发系列:数组转字符串后,给每一项加上单引号
     $arr=array('a','b','c');echo"'".implode("','",$arr)."'";//outputs'a','b','c' 需要注意的是,implode的第一个参数,加上的双引号,如果是用在sql查询里,会自动加上转义符,即:......
  • JavaScript 使用一个数组对另一个对象数组进行过滤
    JavaScript使用一个数组对另一个对象数组进行过滤假设我们有一个对象数组objs,其中每个对象都有一个name属性,我们希望使用一个数组names对objs数组进行过滤,只保留那些name属性在names数组中的对象。我们可以使用filter()方法来实现这个功能。constobjs=[{id......
  • 通过数组查询最大值
    #include<iostream>intmain(){floatarr[10];inti;floatmax;intmaxindex;for(i=0;i<=9;i++){scanf_s("%f/n",&arr[i]);}max=arr[0];for(i=1;i,10;i++){if(max<ar......
  • js 查找数组中倒数第二最大值
    constarr=[1,5,3,7,9,21,33,18,12,44,43,22,55,66,65]constresult=arr=>{//存储最小值letminMax=0//存储最大值letmax=0arr.forEach(item=>{if(item>max){if(minMax<max){minMax=max......
  • 10.二级指针,指针的动态存储,常量与指针的结合、指针与数组的结合及指针函数
    二级指针的语法指针的动态存储常量指针和指针常量指针数组和数组指针指针和函数的结合二级指针的语法语法:数据类型**变量名 数据类型*变量名[常量]inta=10;int*p=&a;int**dp=&p;cout<<p<<""<<*dp<<""<<**dp;输出结果......
  • 2023-05-16:给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。 请你找到这个数
    2023-05-16:给你一个严格升序排列的正整数数组arr和一个整数k。请你找到这个数组里第k个缺失的正整数。输入:arr=[2,3,4,7,11],k=5。输出:9。答案2023-05-16:大体步骤如下:1.初始化左指针l为0,右指针r为数组长度减一,定义中间指针m和find(找到第k个正整数前的下标位置),......
  • 23-5-16--数组--猜帽子游戏
    L1-5猜帽子游戏分数 15作者 陈越单位 浙江大学宝宝们在一起玩一个猜帽子游戏。每人头上被扣了一顶帽子,有的是黑色的,有的是黄色的。每个人可以看到别人头上的帽子,但是看不到自己的。游戏开始后,每个人可以猜自己头上的帽子是什么颜色,或者可以弃权不猜。如......
  • 16进制转字节数组为负数问题
    举例:B9转换成字节数组为-73或者185为什么如果是-73字节数组再转回为16进制为:0xFFFFFFB9,与原来的B9相差解析:在java里面B9 转换成二进制为:00000000000000000000000010110101Int转换为Byte的过程,也是将Int里32个bit的前24个“砍掉”,只留下最后8个bit的过程即为......
  • P3919 【模板】可持久化线段树 1(可持久化数组) 题解
    一、题目描述:维护这样的一个长度为$n$的数组,支持以下两种操作$1$:在某个历史版本上修改某一个位置上的值$2$:访问某个历史版本上的某一位置的值每进行一次操作,就会生成一个新的版本(对于操作2,生成的就是一个完全一样的版本)。版本编号即为当前操作......