https://blog.csdn.net/qq_33375598/article/details/104492685

1 lowbit计算

lowbit其实是二进制的一个应用，lowbit(x) = x & (-x);
在这里插入图片描述
一般，整数在计算机中，都是以补码的形式存储，把补码表示的整数x变成-x，就是把x的每位都取反，然后末尾加1。而这等价于把x最右边1的左边每一位都取反。
如上图所示，lowbit(x) = x & (-x)就是取二进制最右边的1和它右边所有的0。如对于x=6(110)2来说，x&(-x)=（010)2 =2.
==显然，lowbit也可以理解为能整除x的最大2的幂次。==

2 树状数组（单点更新、区间查询）

2.1 问题描述

给出一个整数序列A，元素个数为N( $N\leq10^{5}$ ),接下来查询K次（ $K\leq10^{5}$ ），每次查询将给出一个整数x（ $x\leq N$ ），求前x个整数的和。

例如对于5个整数2、4、1、5、3来说，如果查询前3个整数之和，就需要输出7，查询前5个整数之和就需要输出15。

对于这个问题，一般做法就是开一个sum数组，其中sum[i]表示前i个整数之和（数组下标从1开始），这样sum数组就可以在输入N个整数时就预处理出来。接着每次查询前x个整数之和，输出sum[x]即可。显然每次查询的复杂度为O(1),因此总的时间复杂度为O(K)。

现在对问题进行升级，假设在查询的过程中随时给第x个整数加上一个整数v，要求在查询中能实时输出前x个整数之和（更新操作和查询操作的总次数之和为x）。

例如，依然对整数2、4、1、5、3来说，一开始查询前3个整数之和，将出货7、接着把第二个整数增加3，此时序列变成2、7、1、5、3；之后又进行一次查询，要求查询前4个整数之和，此时应该输出15而不是12.

如果还是之前的做法，单词查询的时间复杂度还是O(1)，但是进行更新时却需要给sum[x]、sum[x+1]...、sum[N]都加上整数V，这使得更新的复杂度变为O(N),那么如果K次操作中大部分都是更新操作，操作的总复杂度就会是O(KN),显然是无法承受的。

如果不设sum数组，直接对原数组进行更新和查询，虽然单词更新的时间复杂度为1，但是查询的时间复杂度确实O(N)。

于是树状数组就可以解决这个问题。

2.2 思想

树状数组(Binary Indexed Tree,BIT):一个用来记录和的数组（和sum类似，存放的却不是前i个整数和），而是在i号位之前（含i号位，下同）lowbit(i)个整数的和。
在这里插入图片描述
如上图所示，数组A是原始数组，A[1]~A[16]共16个元素；
==数组C是树状数组，其中C[i]存放数组A中i号位之前lowbit(i)个元素之和==。显然，C[i]覆盖的长度为lowbit(i),它是2的幂次，即1、2、4、8等。
数组数组仍然是平坦的数组，画成树形是更方便观察。
在这里插入图片描述
如上图所示，
C[1] =A[1] (长度为lowbit(1) = 1)【能整数1的是2^0^,即1】
C[2] =A[1]+A[2] (长度为lowbit(2) = 2)【能整数2的是2^1^,即2】
C[3] =A[3] (长度为lowbit(3) = 1)【能整数3的是2^0^,即1】
C[4] =A[1]+A[2]+A[3]+A[4] (长度为lowbit(4) = 4)【能整数4的是2^2^,即4】
C[5] =A[5] (长度为lowbit(5) = 1)【能整数5的是2^0^,即1】
C[6] =A[5]+A[6] (长度为lowbit(6) = 2)【能整数6的是2^1^,即2】
C[7] =A[7] (长度为lowbit(5) = 1)【能整数7的是2^0^,即1】
C[8] =A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8] (长度为lowbit(8) = 8)【能整数8的是2^3^,即8】

强调树状定义非常重要（前lowbit(i)个数之和（包括i）），特别是“C[i]的覆盖长度是lowbit(i)”；树状数组的下标必须从1开始。

2.3 实现

2.3.1设计函数getSum(x)

2.3.1.1 思路

函数getSum(x):返回前x个数之和A[1]+A[2]+...+A[x]
在这里插入图片描述
由上图观察可得，
A[1]+..A[14]=C[8]+C[12]+C[14];
A[1]+...+A[11]=C[8]+C[10]+C[11]。
怎么知道A[1]+...A[x]对应那些树状数组呢？

记SUM(1,x) =A[1]+...+A[x],由于C[x] = A[x-lowbit(x)+1]+...A[x],
于是得到 $SUM(1,x) =A[1]+...+A[x]\\ =A[1]+..+A[x-lowbit(x)]+A[x-lowbit(x)+1]+...+A[x]\\ =SUM(1,x-lowbit(x))+C[x]$
如下图所示：
在这里插入图片描述

2.3.1.2 实现代码

//返回前x整数和
int getSum(int x){
    int sum = 0;
    for (int i = x; i > 0 ; i-= lowbit(i))//注意i>0，因为没有c[0]
    {
        sum += c[i];//累计c[i],然后把问题缩小到SM(1,i-lowbit(i))
    }
    return sum;//返回求和
}

代码解析：
lowbit(i)是定位i最右边的1，因此i-= lowbit(i)就是把最右边的1不断置零，因此getSum的时间复杂度为O(logN)（一个数x转换为二进制，有x/2^n^位）（从另一个角度理解，“树”高位log(N)）。
在这里插入图片描述
如果求数组下标在区间[x,y]内的和，即A[x]+...+A[y],可以转换成getSum(y)-getSum(x-1)来求解。

2.3.2 设计函数update(x)

2.3.2.1 思路

update(x,v):实现将第x数上加v，即A[x]+=v。
在这里插入图片描述
由上图可得，让A[6]加上一个v，就要寻找树状数组能覆盖A[6]的元素，让它们都加上v。也就是如果让A[6]加上v，实际上就是让C[6]，C[8],C[16]都加上v；同样的如果让A[9]加上v，就是让C[9]、C[10]、C[12]、C[16]都加上v。

问题如果想要给A[x]加上v，该寻找那些树状数组对应项？

如上图所示，如果要寻找让A[x]加上一个v，就要寻找树状数组能覆盖A[x]的元素，让它们都加上v。
也就是总是要寻找离当前的C[x]最近的能覆盖C[x]的C[y]。显然,lowbit(b)必须要大于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）。
于是设计思路就是，让x不断的加上lowbit(x),同时让每步的C[x]都加上v，直到x超过给定的数据范围为止（在不给定范围的情况下，更新操作无上限）。

2.3.2.2 实现代码

//将第x个整数加上v
void update(int x, int v){
    for (int i = x; i <= N; i+= lowbit(i))//i必须能取到N
    {
        c[i] += v;//让c[i]加上v，然后让c[i+lowbit(i)]加上v
    }
}

在这里插入图片描述
由上图可知，update函数的过程是沿一条不断右上的路径进行。由于“树”高log(N),因此update的总时间复杂度也是O(logN)。

2.4 应用

2.4.1 问题描述（统计序列中在元素x左边比小的元素个数）

给定一个由N个整数的序列A( $N\leq 10^{5}, A[i] \leq 10^{5}$ ),对序列中的每个数，求出序列中它左边比他小的数的个数。

如对序列{2,5,1,3,5,4},A[1]等于2，它左边比它小的数由0个；A[2]等于5，它左边比它小的数有1个，即2；依次类推，A[5]等于4，它左边比它小的数有3个，即2、1、3。

一般用hash数组的做法，其中hash数组记录整数x当前出现的次数。接着，从左到右遍历序列A，假设当前访问的是A[i],那么就令A[i]加1，表示当前A[i]出现的次数增加了1次；同时，序列中在A[i]左边比A[i]小的数的个数等于hash[1]+hash[2]+....+hash[A[i]-1],这个和需要输出。

但是显然这两个工作可以由update(A[i],1)和getSum(A[i]-1)来解决。

2.4.2 实现代码

实际上，不用真建一个hash数组，它只存在于解法的逻辑逻辑中。
这是树状数组最经典的应用，即统计序列中在元素x左边比小的元素个数

#include <cstdio>
#include <cstring>

const int MAXN = 100010;
#define lowbit(i) ((i) & (-i))
int c[MAXN];

void update(int x, int v){
    for (int i = x; i < MAXN; i += lowbit(i))
    {
        c[i] += v;
    }
}

int getSum(int x){
    int sum = 0;
    for (int i = x; i > 0 ; i -= lowbit(i))
    {
        sum += c[i];
    }
    return sum;
}

int main(int argc, char const *argv[])
{
    int n, x;
    scanf("%d", &n);
    memset(c, 0, sizeof(c));//数组数组初始位0
    for (int i = 0; i < n; ++i)
        {
            scanf("%d", &x);//输入序列元素
            update(x, 1); //x的出现次数加1
            printf("%d\n", getSum(x-1));//查询当前小于x的数的个数
        }    
    return 0;
}

2.4.3 扩展一——离散化（统计序列中在元素x左边比x大（右边比x小（或大））的元素个数）

2.4.3.1 问题描述

统计序列中在元素x左边比大的元素个数，这问题等价于统计hash[A[i]+1]+……+hash[N],于是getSum(N)- getSum(A[i])就是答案。

至于统计在元素x右边比小（或大）的元素个数，只要把原始数组从有往左遍历就可以。

现在出现了问题，如果 $A[i]\leq N$ 不成立（例如 $A[i] \leq 10^{9}$ ），看起来树状数组开不了那么大。

解决办法就是，只考虑它们的之间的大小关系，
如序列{11,111,1,11}于序列{2,4,1,2}是等价的（当然只考虑大小关系，与{2,3,1,2}也是等价的）。

因此可以把A[i]与1～N对应起来，而这与“给定N个学生的分数，给他们进行排名，分数相同的则排名相同”显然是同一个问题。

一般来说，设置一个临时数据结构数组，用以存放输入的序列元素的值以及原始序号，而在输入完毕后将数组按val从小到排序，排序完后再按找“计算机排名”的方式将“排名”根据原始序号pos存入一个新的数组即可。
==由于这种方法可以把任何不在合适区间的整数或者非整数都转换为不超过元素个数大小的整数，因此一般把这种技巧称为离散化。==

2.4.3.2 实现代码

这里给出“统计序列中在元素走遍都比该元素小的元素个数”问题使用离散化的代码：

#include <cstdio>
#include <cstring>
#include <algorithm>

using std::sort;

const int MAXN = 10010;
#define lowbit(i) ((i) &(-i))

struct Node
{
    int val;//序列元素的值
    int pos;//原始序号
}temp[MAXN];
int A[MAXN];//离散后的原始数组
int c[MAXN];//树状数组

void update(int x, int v){
    for (int i = x; i < MAXN; i += lowbit(i))
    {
        c[i] += v;
    }
}

int getSum(int x){
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i))
    {
        sum += c[i];
    }
    return sum;
}

bool cmp(Node a, Node b){
    return a.val < b.val;
}

int main(int argc, char const *argv[])
{
    int n, x;
    scanf("%d", &n);
    memset(c, 0, sizeof(c));

    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &temp[i].val);
        temp[i].pos = i;
    }

    //离散化
    sort(temp, temp + n, cmp);//按val的顺序从小到大排序
    for (int i = 0; i < n; ++i)
    {
        //与上一个元素不同，赋值为元素个数
        if(i == 0 || temp[i].val != temp[i-1].val){
            A[temp[i].pos] = i + 1;//这里必须从1开始
        }else{//遇上一个元素相同，直接继承
            A[temp[i].pos] = A[temp[i-1].pos];
        }
    }

    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &x);//输入序列元素
        update(A[i], 1);//A[i]出现的次数加1
        printf("%d\n", getSum(A[i] - 1));//查询当前小于A[i]的数的个数
    }
    return 0;
}

一般离散化只适合离线查询，因为只有知道所有出现的元素之后，才方便进行离散化。

但是对于在线查询，也可以先把所有操作都记录下来，然后对其中出现的数据进行离散化，然后再按记录下来的操作顺序正常进行“在线”查询即可。

2.4.4 扩展二 ——求序列第K大的数

2.4.4.1

对于这个问题，之前是用分块思想来解决的,现在尝试用树状数组来解决。

对于一个序列，如果用hash数组记录每个元素出现的个数，那么序列第K大，就是在求最小的i，使得 $hash[1]+...+hash[i] \leq K$ 成立。也就是说，如果用树状数组来解决hash数组求和的问题，那么这个问题就等价于寻找第一个满足条件的" $getSum(i) \leq K$ "的i。

由于hash数组的前缀和是递增的，可以令i=1、r=MAXN，然后在[l,r]范围内进行二分，对当前的mid，判断 $getSum(mid) \ge K$ 是否成立，

如果成立，说明所求位置不超过mid，因此令r=mid；
如果不成立，说明所求位置大于mid，因此令l=mid+1.
显然二分的时间复杂度为O(logn),求和的时间复杂度为O(logn),因此总时间复杂度是O(log^2^n)

2.4.4.2 实现代码

int findKthElement(int K){
    int l = 1, r = MAXN, mid;//初始区间为[1,MAXN]
    while(l < r){//循环，直到[l,r]能锁定单一元素
        mid = (l +r) / 2;
        if(getSum(mid) >= K){//所求位置不超过mid
            r = mid;
        }else{//所求位置大于mid
            a = mid +1;
        }
    }
    return l;//返回二分夹出来的元素
}

2.4.5 扩展三 ——二维树状数组(函数getSum, updtae)

如果想求A[a][b]~A[x][y]这个子矩阵的元素和，只需计算getSum(x,y) - getSum(x-1,y) - getSum(x, y-1)+getSum(x-1,y-1)即可。
更高维只需把for循环改为相应的重数即可。

int c[MAXN][MAXN];//二维树状数组
void update(int x, int y, int v){
    for (int i = x; i < MAXN; i += lowbit(i))
    {
        for (int j = y; j < MAXN; j += lowbit(j))
        {
            c[i][j] += v;
        }
    }
}

int getSum(int x, int y){
    int sum = 0;
    for (int i = x; i > 0 ; i -= lowbit(i))
    {
        for (int j = x; j > 0; j -= lowbit(j))
        {
            sum += c[i][j];
        }
    }
    return sum;
}

3 树状数组（区间更新、单点查询）

3.1 设计getSum函数

3.1.1 思想

如果按照原先树状数组的定义，update函数（update(x,v)：将A[1]~~A[x]的每个数都加上x），只有通过遍历A[1]\~~A[x]来达到目的，因此不管怎么样都无法达到O(logN)的复杂度。因此为了能让update函数依然保持O(logn)的时间复杂度，需要对树状数组的定义进行修改。

树状数组C中每个“矩形”C[i]依然保持和之前一样的长度，即lowbit(i),但是C[i]不再表示这段区间的元素之和，而是表示这段区间每个数应当前被加了多少。
在这里插入图片描述
如上图所示，C[16]= 0表示A[1]~~A[16]都加了0，C[8]=5表示A[1]\~~A[8]都被加了5，C[6]= 3表示A[5]~A[6]都被加了3，C[5]表示A[5]被加了6。
显然对于A[5]来说，它被C[5]加6，被C[6]加了3，被C[8]加了5，因此时间的A[5]的值应当是C[5]+C[6]+C[8] = 14。

显然,A[x]的值实际上就是覆盖了它的若干“矩形”C[i]的值之和，而显然是之前“单点更新，区间查询”问题中update函数的做法。

因此，可以之和把原先的update函数作为这里的getSum函数：

3.1.2 实现代码

//返回第x整数的值
int getSum(int x){
    int sum = 0;//记录和
    for (int i = x; i < maxn; i += lowbit(i))//沿i增大方向
    {
        sum += c[i];
    }
    return sum;//返回求和
}

3.2 设计update函数

3.2.1 思想

由于是区间更新，此处的update需要把A[1]~A[x]的每个数都加上v，
因此可以使用之前"单点更新，区间查询"问题中的getSum函数的做法。

也就是说UPDATE(1,x)表示A[1]~A[x]的每个都加上v，那等价于让C[x]+v,然后执行UPDATE(1,x - lowbit(x))

在这里插入图片描述
如上图所示，先让A[1]~~A[14]每个数加上6，等于让C[8]、C[12]、C[14]加上6；接着让A[1]\~~A[10]的每个数都加上3，等价于让C[8]、C[10]加上3，于是C[8]此时已经为6+3=9,表示A[1]~A[8]的每个数都被加上了9。

如果此时查询A[6]的值，就会得到A[6] = C[6]+C[8]+C[16] = 0 + 9 + 0 = 9;如果查询A[9]的值，就会得到A[9] = C[9]+C[10] + C[12] = 0 + 3 + 6 + 0 = 9。

于是就可以直接把原先的getSum函数作为这里的update函数：

3.2.2 实现代码

//将前x个整数都加上v
void update(int x, int v){
    for (int i = x; i > 0; i -= lowbit(x))//沿着i减小的路径
    {
        c[i] += v;//让c[i]加上v
    }
}

显然，如果要让A[x]~~A[y]都加上v，只要先让A[1]\~~A[y]的每个数都加上v，然后再让A[1]~A[x-1]的每个数都加上-v，即先执行update(y,v),然后执行update(x-1, -v)。

树状数组(单点更新、区间查询/区间更新、单点查询)（update和getSum函数）————附完整代码以及示例和示例代码