专题扩展(2) - 树状数组(BIT)

2023-04-11 3737 words 8 minutes

Contents

lowbit 运算

$lowbit(x) = x & (-x)$ 整数在计算机中一般采用的是补码存储，并且把一个补码表示的整数 x变成其相反数-x的过程相当于把x的二进制的每一位都取反，然后末位加 1。而这等价于直接把X的二进制最右边的1左边的每一位都取反. 对$x=(0000001101001100)_2$来说，最右边的 1 是在 2号位，因此把它左边的所有位全部取反，于是有$(-x=1111110010110100)_2$。通过它可以很容易推得$lowbit(x)=x&(-x)$就是取的二进制最右边的1和它右边所有 0，因此它一定是 2 的幂次，即 1、2、4、8 等。例如对上面的例子(0000001101001100)来说，x&(-x)=(0000000000000100)=4;而对x=6=(110)来说，x&(-x)=(010)=2。显然，lowbit(x)也可以理解为能整除X的最大2的幂次。

树状数组及其应用

先来看一个问题:给出一个整数序列A，元素个数为N(N<=10^5)，接下来查询K次(K<=10^5)，每次查询将给出一个正整数x(x<=N)，求前x个整数之和。

例如对5个整数2、4、1、5、3 来说，如果查询前3 个整数之和，就需要输出7如果查询前 5 个整数之和，就需要输出15。一般的做法是开一个 sum 数组，其中sum[i]表示前个整数之和(数组下标从1开始)，这样sum数组就可以在输入个整数时就预处理出来接着每次查询前X个整数之和时，输出 sum[x]即可。显然每次查询的复杂度是 O(1)，因此查询的总复杂度是 O(K).

现在升级一下这个问题，假设在查询的过程中可能随时给第x个整数加上一个整数V. 要求在查询中能实时输出前 x 个整数之和(更新操作和查询操作的次数总和为 K次)。如果还是之前的做法，虽然单次查询的时间复杂度仍然是 O(1)，但在进行更新时却需要给sum[x]、sum[x+1]、···、sum[N]都加上整数v，这使得单次更新的时间复杂度为 O(N)，那么如果 K 次操作中大部分都是更新操作，操作的总复杂度就会是 O(KN)，显然无法承受

那如果不设置sum数组，直接对原数组进行更新和查询呢?很显然，虽然单次更新的时间复杂度变成了O(1)，但是单次查询的时间复杂度却变为了 O(N)。

树状数组(BinaryIndexedTree，BIT)。它其实仍然是一个数组，并且与sum数组类似,是一个用来记录和的数组，只不过它存放的不是前i个整数之和，而是在i号位之前(含i号位，下同)lowbit(i)个整数之和。下标从1开始

此时, 就有以下两个基本操作:

设计函数 getSum(x)，返回前x个数之和A[1]+..·+A ;
设计函数 update(x,v)，实现将第x个数加上一个数的功能，即A +=v

getSum(x)

记SUM(1,x)=A[1]+...+A[x]，由于 C[x]的覆盖长度是 lowbit(x)，因此 C[x]=A[x-lowbit(x)+1]+···A[x] 于是马上可以得到:

SUM(1x) = A[1]+...+A[x]
        = A[1]+...+A[x-lowbit(x)]+A[x -lowbit(x)+1]+...+ A[x]
        = SUM(1,x-lowbit(x)) + C[x]

显然，由于lowbit()的作用是定位i的二进制中最右边的1，因此i=i-lowbit(i)事实上是不断把i的二进制中最右边的1置为0的过程。所以getSum函数的 for 循环执行次数为的二进制中1的个数. 也就是说，getSum函数的时间复杂度为 O(ogN)。

update(x,v)

假如要让 A[6]加上一个数，那么就要寻找树状数组C中能覆盖了 A[6]的元素，让它们都加上 V。也就是说，如果要让 A[6]加上v，实际上是要让C[6]、C[8]、C[16]都加上v. 那么，如何找到距离当前的C[x]最近的能覆盖C[x]的 C[y]呢?首先，可以得到一个显然的结论:lowbit(y)必须大于 lowbit(x)(不然怎么覆盖呢……)。于是问题等价于求一个尽可能小的整数a，使得 lowbit(x+a)>lowbit(x)。显然，由于lowbit(x)是取x的二进制最右边的1的位置，因此如果lowbit(a)< lowbit(x)，lowbit(x +a)就会小于lowbit(x)。为此lowbit(a)必须不小于lowbit(x)。接着发现，当a取lowbit(x)时，由于x和a的二进制最右边的1的位置相同因此x+a会在这个1的位置上产生进位，使得进位过程中的所有连续的1变成0，直到把它们左边第一个0置为1时结束。于是lowbit(x +a)>lowbit(x)显然成立最小的a就是lowbit(x)。

求序列中左边比它小的数

给定一个有N个正整数的序列A(N105，A105)，对序列中的每个数，求出序列中它左边比它小的数的个数 例如对序列{2,5,1,3,4，A1}: A[1]等于2，在A[1]左边比A[1]小的数有0个; A[2]等于 5，在 A[2]左边比A[2]小的数有1个即2; A[3]等于1因此在 A[3]左边比A[3]小的数有0个; A[4]等于3，因此在A[4]左边比A[4]小的数有2个即2、1; A[5]等于4，在A[5]左边比A[5]小的数有3个，即2、1、3。

先来看使用 hash 数组的做法，其中 hash[x] 记录整数x当前出现的次数。接着，从左到遍历序列A，假设当前访问的是 A[i]，那么就令 hash[A[i]] 加1，表示当前整数A[i]的出现数增加了一次;同时，序列中在 A[i] 左边比 A小的数的个数等于 hash[1] + hash[2] +...hash[A[i]-1]，这个和需要输出。但是很显然，这两个工作可以通过树状数组的 update(A[i],1) 和 getSum(A[i]-1) 来解决。使用树状数组时，不必真的建一个 hash 数组，因为它只存在于解法的逻辑中，并不需要真的用到，只需用一个树状数组来代替它即可。代码如下:

// @FileName:     baseline.cpp
// @CreateTime:   2023/04/11 11:10:54
// @Author:       Rainbow River

#include <iostream>
using namespace std;
#define lowbit(i) ((i)&(-i))
const int maxn = 100010;
int c[maxn];    // 树状数组, i号元素 记录着 原始序列A 指定片段(i-lowbit(i), i]的和

// update(x, v) x 为序列元素编号, 该函数表示 将A[x]加上v后 树状数组的更新规则
void update(int x, int v){
    for(int i=x; i<maxn; i+=lowbit(i))
        c[i] += v;
}
// get_sum(x) 返回前x个整数的和
int get_sum(int x){
    int sum = 0;
    for(int i=x; i>0; i-=lowbit(i)) // 下标从 1 开始
        sum += c[i];
    return sum;
}

int main(){
    int n;   // 数组元素个数 n, 要查询的 元素序号 x
    cin >> n;
    for (int i=0; i<n; i++){
        int v;
        cin >> v;
        update(v, 1);   // 此时 A[] 逻辑上是一个哈希数组, A[v] 记录着 元素v 的出现次数
        cout << get_sum(v-1) << endl;   // 函数返回值意义: A[1]+A[2]+ ...+A[i] 表示小于v的元素 出现次数
    }
    return 0;
}
/*
17 8
27 10 15 13 12 32 28 43 12 17 22 77 56 30 20 25 16
*/

这就是树状数组最经典的应用，即统计序列中在元素左边比该元素小的元素个数，其中“小”的定义根据题目而定，并不一定必须是数值的大小。那么，如何统计序列中在元素左边比该元素大的元素个数呢?事实上这等价于计算hash[A[i] + 1]+…+ hash[N]，于是 getSum(N)- getSum(A[i])就是答案。至于统计序列中在元素右边比该元素小(或大)的元素个数，只需要把原始数组从右往左遍历就好了。

但是现在还有问题没有解决:如果 AN 不成立(例如 $10^9$)，看起来状数组开不了那么大，是不是就没办法了呢?当然不是。举个例子，现在给定一个序列 A 为 {520, 999999999, 18, 666, 88888} 如果只需要考虑它们之间大小的关系，那么这个序列实际上和2.5,1,3,4是等价的。同样的，序列11,111,1,113与24.1,2也是等价的(当然只考虑大小关系的话与2,3,1,2等价也是可以的)因此要做的就是把 A[] 与 1-N 对应起来. 而这与“给定N个学生的分数，给他们进行排名，分数相同则排名相同”显然是同一个问题。一般来说可以设置一个临时的结构体数组，用以存放输入的序列元素的值以及原始序号，而在输入完毕后将数组按 val 从小到大进行排序，排序完再按照“计算排名”的方式将“排名”根据原始序号 pos 存入一个新的数组即可。由于这种做法可以把任何不在合适区间的整数或者非整数都转换为不超过元素个数大小的整数，因此一般把这种技巧称为离散化。

// @FileName:     difussed.cpp
// @CreateTime:   2023/04/11 15:00:56
// @Author:       Rainbow River

#include<iostream>
#include<algorithm>
#define lowbit(x) (x&(-x))
using namespace std;
// 由于 哈希限制, 这里需要将原始序列映射到 [0, N)
const int maxn = 10010;
struct idval{
    int tid, tval;  // 序号-值
}temper[maxn];
int A[maxn];    // 原始序列 映射至 [0, N) 后的序列
int c[maxn];    // 树状数组
bool cmp(idval a, idval b){
    return a.tval < b.tval;
}

// hash[x] += v --> update c[]
void update(int x, int v){
    for(int i=x; i<maxn; i+=lowbit(i))
        c[i] += v;
}

// get the sum of hash[1 ... x]
int get_sum(int x){
    int s = 0;
    for(int i=x; i>0; i-=lowbit(i))
        s += c[i];
    return s;
}

int main(){
    // 1. input elements: store to temper with ids
    int n, v;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> v;
        temper[i].tid = i;
        temper[i].tval = v;
    }
    // 2. reflect vals to id
    sort(temper, temper+n, cmp);    // first, we sort ascending by vals
    for(int i=0; i<n; i++){         // then we reflect to A[]
        if(i==0 || temper[i].tval != temper[i-1].tval){
            A[temper[i].tid] = i+1;
        }else{
            A[temper[i].tid] = A[temper[i-1].tid];
        }
    }
    // 3. finally, we can make choice
    for(int i=0; i<n; i++){
        update(A[i], 1);    // A[i] 代表的原始元素数量加一
        cout << get_sum(A[i]-1) << endl;
    }
    return 0;
}

对一个序列来说，如果用 hash数组记录每个元素出现的个数，那么序列第K大就是在求最小的i,使得ash/11+…+hashliK 成立。也就是说，如果用树状数组来解决 hash 数组的求和问题那么这个问题就等价于寻找第一个满足条件“getSum(i)K”的i。针对这个问题,由于hash数组的前缀和是递增的,根据4.5.1节可以1=1=MAXN然后在[l, r]范围内进行二分，对当前的 mid，判断getSum(mid)>是否成立:如果成立，说明所求位置不超过mid，因此令r=mid;如果不成立说明所求位置大于mid，因此令1=mid+ 1。如此二分，直到l<r不成立为止。显然二分的时间复杂度是 O(logn)，求和的时间复杂度也是O(logn)，因此总复杂度是$O(\log n^2)$。

int findKthElement(int K){
    int l = 1, r = maxn, mid;
    while(l<r){
        mid=(1+r)/2;
        if(getSum(mid)>=k) r=mid;
        else l=mid+1;
    }
    return l;
}