树状数组

任务1：区查单改

模板：洛谷P3374

已知一个数列，你需要进行下面两种操作：

1.将某一个数加上x

2.求出某区间每一个数的和

初看此题，我们很容易想到暴力和前缀和。但暴力询问时间太长，前缀和修改时间太长，两者时间复杂度均为$O(nm)$，不能满足需求。

于是，一个$O(mlogn)$的算法横空出世...

树状数组的详解网上一大堆，我只谈谈我对树状数组的理解。

1.lowbit(x)的证明

$lowbit(x)$=$x$&$(-x)$

e.g:$lowbit(148) = 148$ & $(-148) = $10010100 & 01101100 $ = $ 00000100 $= 4$

$lowbit(x)$的值即一个二进制数中从低位到高位数的第一个1所表示的十进制值。

但是，为什么呢？

网上题解很少提及这个函数的证明，因为它确实特别玄学。

我的证明如下：

（下文中的“原来”或“之前”指原数，“现在”指取反~后）

我们知道，一个负数表示为二进制就是它的补码，补码就是该负数的绝对值表示为二进制后按位取反 +1 的值 (~|x|+1)

e.g:$-148 = -($10010100$) = $~10010100$ + $1$ = $01101011 $+$ 1 $=$ 01101100

生成补码后

一种情况是不发生任何进位，即原来为1，现在为0 的最低位 +1 后变成了1，其他位只有取反操作。

再对原数和负数的补码按位与&，

由于取反，除最低位的所有位运算的情况不是0&1=0，就是1&0=0，

只有最低位原来是1，取反后+1还是1，1&1=1

所以这种情况下$lowbit(x)$恒为00000001，也就是1

e.g:

$lowbit(149)$

$= 149$ & $(-149)$

$= $10010101 & 01101011

$= $ 00000001

$= 1$

另一种情况则进位，而且可能连锁反应进很多次位。

最低位原来为0，现在为1 ，+1后变为2，需向上进位，然后自身变回0，

如果上一位之前为0，现在为1 ，收到了前一位的进位 +1 后变为2，又需要向上进位，然后自身变为0...

如此反复，直到遇到之前为1，现在为0 的位，收到前一位进位后+1变成1，停止连锁反应。

我们把这一个位设为a，则补码出现了这样的情况：

比x高的位因为没有受到进位的影响，是原数取反的结果；

x由于取反后为0，又收到上一位进位，所以一定为1；

比x低的位由于取反后为1，又收到上一位进位，所以一定为0。

然后我们把原数和负数补码按位与&，

比x高的位的情况不是0&1=0，就是1&0=0；

x则为1&1=1；

比x低的位则全为0，所以结果一定为0。

所以答案为0...010...0 ，1所在的位置便是x位，也是原数中从低位数第一个1。

e.g:

$lowbit(148)$
$=148$ & $(-148)$
$=$ 10010100 & $-($10010100$)$
$=$ 10010100 & $(~$10010100$ + $1$)$
$=$ 10010100 & 01101100
$=$ 00000100

综上所述，$lowbit(x)$后只剩下一位有1，而它所在的位即x，也是就从低位数到高位的第一个1。

（我自己都感觉写的太复杂了）╮(╯▽╰)╭

2.lowbit(x)的运用

既然$lowbit(x)$的值即一个二进制数中从低位数到高位的第一个1所表示的十进制值，也是节点x所管辖的节点个数。那么拿$x+lowbit(x)$必定发生一次最小的进位，$x-lowbit(x)$必定让从低位数到高位的第一个1变成0。而观察树状数组，发现一旦进位就多出一层包含关系，一旦变0就会退出一层所在的包含关系，那么就可以方便的通过$x+lowbit(x)$找到当前节点的父节点，通过$x-lowbit(x)$找到前面未包含的节点。

上代码：

一维：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<ctime>
using namespace std;
const int MXN=1000000,INF=999999999;

struct BIT{
    int lowbit(int x){return x&(-x);}
    int tr[MXN],n;
    void Init(int myn){n=myn;for(int i=0;i<=n;i++) tr[i]=0;}
    void Modify(int x,int val){
        for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=val;
    }
    int GetSum(int x){
        int ans=0;if(x==0) return 0;
        for(int i=x;i>=1;i-=lowbit(i)) ans+=tr[i];
        return ans;
    }
    int Query(int l,int r){
        return GetSum(r)-GetSum(l-1);
    }
}bit;
//这里以单点加值，区间查询为例
int n,qn;
int main(){
    cin>>n>>qn;
    bit.Init(n);
    for(int i=1;i<=n;i++){
        int t;scanf("%d",&t);
        bit.Modify(i,t);
    }
    for(int i=1;i<=qn;i++){
        int type,x,y;
        scanf("%d%d%d",&type,&x,&y);
        switch(type){
            case 1:
                bit.Modify(x,y);
                break;
            case 2:
                printf("%d
",bit.Query(x,y));
                break;
        }
    }
    return 0;
}

View Code（new）

二维：

其实就是多了一层循环...然后变更和查询的方式也变了，稍微想想就能够明白

没找到模板，就直接上代码了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<queue>
//#include<windows.h>
using namespace std;

long long lowbit(long long val){
    return val&(-val);
}
struct BIT{
    long long sizex,sizey;
    long long tree[2005][2005];
    
    void init(long long mysx,long long mysy){
        sizex=mysx;
        sizey=mysy;
        for(long long i=0;i<2005;i++) 
            for(long long j=0;j<2005;j++)
                tree[i][j]=0;
    }
    void change(long long idx,long long idy,long long val){
        for(long long i=idx;i<=sizex;i+=lowbit(i))
            for(long long j=idy;j<=sizey;j+=lowbit(j))
                tree[i][j]+=val;
    }
    long long getsum(long long idx,long long idy){
        if(idx==0||idy==0) return 0;
        long long ans=0;
        for(long long i=idx;i>=1;i-=lowbit(i))
            for(long long j=idy;j>=1;j-=lowbit(j))
                ans+=tree[i][j];
        return ans;
    }
    long long ask(long long x1,long long y1,long long x2,long long y2){
        return getsum(x2,y2)-getsum(x1-1,y2)-getsum(x2,y1-1)+getsum(x1-1,y1-1);
    }
}bit;

int main(){
    return 0;
}

View Code

任务2：区改单查

模板：洛谷P3368

已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数数加上x

2.输出某一位置上的数

用到了差分的思想。

比如原数列a[]={1,5,4,2,3}

加一个数组b[]，使b[i]=a[i]-a[i-1]，即{1,4,-1,-2,1}

然后进行区间加值操作，如把下标2到下标5的数+3。

a[]变为{1,8,7,5,3}，b[]变为{1,7,-1,-2,-2}

有没有发现只有b[2]和b[5]变了？

b[]只需一头一尾变化，因为区间内所有的数都加上了同样的值，差值不变。

所以把b[]这个差分数组用树状数组维护前缀和。

为什么维护前缀和？因为a[i]就等于b[1]+b[2]+...+b[i]

完美解决

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

long long n,con;
long long e[500005]= {0};

long long lowbit(long long num) {
    return (-num)&num;
}

void change(int pos,long long val) {
    int now=pos;
    for(; now<=n; now+=lowbit(now)) {
        e[now]+=val;
    }
}
long long getans(int pos) {
    if(pos==0) {
        return 0;
    }
    long long sum=0;
    int now=pos;
    for(; now>=1; now-=lowbit(now)) {
        sum+=e[now];
    }
    return sum;
}

int main() {
    cin>>n>>con;
    int t1,t2=0;
    for(int i=1; i<=n; i++) {
        scanf("%lld",&t1);
        change(i,t1-t2);
        t2=t1;
    }
    for(int i=1; i<=con; i++) {
        long long type,x,y,z;
        scanf("%lld",&type);
        if(type==1) { //更改
            scanf("%lld%lld%lld",&x,&y,&z);
            change(x,z);
            change(y+1,-z);
        } else if(type==2) { //询问
            scanf("%lld",&x);
            printf("%lld
",getans(x));//差分数组前缀和即为答案 
        }
    }
    return 0;
}

View Code

任务3：区查区改

模板：洛谷P3372 线段树1

除非题目卡常，不推荐使用。好好的线段树不写为什么要用这个奇怪的玩意儿，（虽然常数小那么一点）

这用到了一些数学的推导

接着任务2的进度，我们把a[]差分到b[]后，只需要维护b[]的前缀和就可以搞到a[]中对应数的值

现在我们想求$a[1]$~$a[x]$的和，转化一下，就变成了

$a[1]+a[2]+...+a[x]$

$=b[1]$

$+b[1]+b[2]$

$+b[1]+b[2]+b[3]$

$+...$

$+b[1]+b[2]+...+b[x]$

再转化，

原式$=b[1]*x+b[2]*(x-1)+b[3]*(x-2)+...+b[x-1]*2+b[x]$

也就是

$large ∑(b[i]*(x+1-i))$

提取其中的不变量，得

$large ∑(b[i]*(x+1-i))=(x+1)*∑b[i] - ∑(b[i]*i)$

好了，我们开2个树状数组，一个维护$b[i]$，另一个维护$b[i]*i$，完事

注意：两个维护b[i]的树状数组并不是差分维护的，它们每次只是修改了b[]里的2个值，b[]是a[]的差分数组

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<queue>
//#include<windows.h>
using namespace std;

long long lowbit(long long val){
    return val&(-val);
}
struct BIT{
    long long size;
    long long tree[1000005];
    
    void init(long long mysize){
        size=mysize;
        for(long long i=0;i<1000005;i++) tree[i]=0;
    }
    void change(long long id,long long val){
        for(long long i=id;i<=size;i+=lowbit(i))
            tree[i]+=val;
    }
    long long getsum(long long id){
        if(id==0) return 0;
        long long ans=0;
        for(long long i=id;i>=1;i-=lowbit(i))
            ans+=tree[i];
        return ans;
    }
    long long ask(long long l,long long r){
        return getsum(r)-getsum(l-1);
    }
}bitC,bitD;

long long n,qn;

void Change(long long l,long long r,long long val){
    bitC.change(l,val);
    bitC.change(r+1,-val);
    bitD.change(l,val*l);
    bitD.change(r+1,-val*(r+1));
}
long long Getsum(long long id){
    return (id+1)*bitC.getsum(id)-bitD.getsum(id);
}
long long Ask(long long l,long long r){
    return Getsum(r)-Getsum(l-1);
}

int main(){
    cin>>n>>qn;
    bitC.init(n);bitD.init(n);
    for(long long i=1;i<=n;i++){
        long long t;scanf("%lld",&t);
        Change(i,i,t);
    }
    for(long long i=1;i<=qn;i++){
        char type[2];
        long long l,r,val;
        scanf("%s",type);
        switch(type[0]){
            case '2':{
                scanf("%lld%lld",&l,&r);
                printf("%lld
",Ask(l,r));
                break;
            }
            case '1':{
                scanf("%lld%lld%lld",&l,&r,&val);
                Change(l,r,val);
                break;
            }
        }
    }
    return 0;
}

View Code

任务4：

模版：洛谷P1531 （I Hate It）

（树状数组求最值）

已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数数变为x

2.询问某一区间的最大值

这个和普通的求和又不一样了。随便举几个例子我们发现，存储区间最值的tree[i]不能直接$O(1)$修改。所以更新的话需要把tree[i]的所有直接子节点全部遍历一道（其实某种意义上，求和是一种不需要遍历的特殊用法）。这里有一个玄学的规律，假设我们需要更新tree[i]，那么它的直接子节点就是tree[i-1]，tree[i-2]，tree[i-4]，...也就是tree[i-2^k]，直到编号超出tree[i]所管辖的范围。又因为tree[i]的管辖点的个数为$lowbit(i)$，所以只需要判断$2^k<lowbit(i)$就好了。处理完本个需要更新的节点后，i+=lowbit(i)更新下一个节点。时间复杂度$O((logn)^2)$

更新没问题了，但显然区间最值没办法用前缀和那样的思想求解。那么如何处理询问呢？可以把要求的区间拆分成众多小区间来计算。首先还是像求和那样不停的减lowbit(i)，如果发现这个这个区间超出了要求的区间（比较要求的左端点和本区间左端点），显然我们不能把这个区间纳入计算范围。所以我们把i减1，让i进入更小的区间去搜寻。最后，当i==l时，结束搜寻，输出结果。时间复杂度O(logn)

（代码里询问部分用r替代了i）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<queue>
//#include<windows.h>
using namespace std;

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

struct BIT{
    int size;
    int data[500005];
    int tree[500005];
    
    void init(int mysize){
        size=mysize;
        for(int i=0;i<500005;i++){
            tree[i]=0;data[i]=0;
        }
    }
    void change(int id,int val){
        data[id]=val;
        for(int i=id;i<=size;i+=lowbit(i)){
            tree[i]=data[i];
            for(int j=1;j<lowbit(i);j<<=1){
                tree[i]=max(tree[i],tree[i-j]);
            }
        }
    }
    int ask(int l,int r){
        int ans=0;
        for(;l<=r;){
            ans=max(ans,data[r]);
            r--;
            for(;r-lowbit(r)>=l;r-=lowbit(r)){
                ans=max(ans,tree[r]);
            }
        }
        return ans;
    }
}a;

int n,m;

int main(){//单点修改，区间查询最大值 
    cin>>n>>m;
    a.init(n);
    for(int i=1;i<=n;i++){
        int t1;
        scanf("%d",&t1);
        a.change(i,t1);
    }
    
    for(int i=1;i<=m;i++){
        int t1,t2,t3;
        scanf("%d",&t1);
        if(t1==1){
            scanf("%d%d",&t2,&t3);
            a.change(t2,t3);
        }else if(t1==2){
            scanf("%d%d",&t2,&t3);
            printf("%d
",a.ask(t2,t3));
        }
    }
    return 0;
}

View Code

参考：

（lowbit证明）http://www.mamicode.com/info-detail-1270028.html
（任务1题解）https://pks-loving.blog.luogu.org/senior-data-structure-gao-ji-shuo-ju-jie-gou-chu-bu-yang-xie-fen-kuai

（任务1二维题解）https://blog.csdn.net/xf_zhen/article/details/52439808

（任务2简单思路）https://www.luogu.org/blog/user33857/solution-p3368

（任务3）https://www.cnblogs.com/RabbitHu/p/BIT.html

（任务4）https://www.cnblogs.com/mypride/p/5002556.html

（任务4）https://blog.csdn.net/yu121380/article/details/81431480