可以代替线段树的树状数组?——树状数组进阶(1)

树状数组进阶（1）

• 前置知识：树状数组，如果没有学过请右转这篇文章：传送门，前缀和，差分。
• 本文代码均未经编译，如有错误请指出。
• QQ826755370

引入

大家学了线段树与树状数组后，一定会觉得树状数组比线段树好写（背）多了，常数也小多了（分析lowbit操作，每次操作中每个节点被访问的概率是1/2,所以常数是1/2）但是美中不足的是树状数组不能区间修改+区间查询啊。事实上，树状数组可以做到这些，还可以查询第k大（小）值。

1、最简单的单点修改+区间查询

这个就不要我讲了吧，直接上代码:

void add(int pos,int x){
    while(pos<=n) c[pos]+=x,pos+=lowbit(pos);
}
int getsum(int pos){
    int sum=0;
    while(pos) sum+=c[pos],pos-=lowbit(pos);
    return sum;
}

2、 稍微难一点点的区间修改+单点0查询

这里用的是差分的思想。

我们设原数组为a，则我们需要维护一个差分数组delta：delta[i]=a[i]-a[i-1]

那么我们可以得到：a[i]=\sum_{j=1}^idelta[j]

现在a[i]被表达成了一个数组内连续的几个元素的，这样我们就解决了查询的问题，那么我们该如何修改呢？

当我们需要将区间[l,r]上的每个数都加上x时，因为d数组是个差分数组，所以我们可以直接在树状数组上将delta[l]加上x，delta[r+1]减去x即可，代码如下：

void add(int pos,int x){
    while(pos<=n) delta[pos]+=x,pos+=lowbit(pos);
}
void modify(int l,int r,int x){
    add(l,x),add(r+1,-x);
}
int getsum(int pos){
    int sum=0;
    while(pos) sum+=delta[pos],pos-=lowbit(pos);
    return sum;
}

重点来了！

3、区间修改+区间查询

我们还是需要引入delta数组，这里的delta[i]表示区间a[i...j]都需要加上的值的和。那么当我们需要将区间[l,r]上的每个数都加上x时，我们还是可以直接在树状数组上将delta[l]加上x，delta[r+1]减去x。

那么问题来了，如何查询区间[l,r]的和？

我们设a[1...i]的和为sum[i]，根据delta数组的定义，则：

sum[i]=\sum_{j=1}^ia[j]+\sum_{j=1}^idelta[j]*(i-j+1) sum[i]=\sum_{j=1}^ia[j]+(i+1)*\sum_{j=1}^idelta[j]-\sum_{j=1}^idelta[j]*j

这样我们就不难看sum[i]是由哪三个部分组成的了。我们需要用一个asum数组维护a数组的前缀和，delta1与delta2两个树状数组，delta1维护delta数组的和，delta2维护delta[i]*i的和，代码如下：

void add(int *arr int pos,int x){
    while(pos<=n) arr[pos]+=x,pos+=lowbit(pos);
}
void modify(int l,int r,int x){
    add(d1,l,x),add(d1,r+1,-x),add(d2,l,x*l),add(d2,r+1,-x*(r+1));
}
int getsum(int *arr,int pos){
    int sum=0;
    while(pos) sum+=arr[pos],pos-=lowbit(pos);
    return sum;
}
int query(int l,int r){
    return asum[r]+r*getsum(d1,r)-getsum(d2,r)-(asum[l-1]+l*getsum(d1,l-1)-getsum(d2,l-1));
}

等等……线段树不是还能查最大最小值吗，事实上树状数组也能查。

4、区间最值

哦，我知道了，我来建树：

void build(){
    for(int i=1;i<=n;i++){
        cin>>a[i];int pos=i;
        while(pos<=n) c[pos]=max(c[pos],a[i]),pos+=lowbit(pos);
    }
}

如果你是这么写的，那么恭喜你……写错了。

以下内容有些难理解，先放一张图：

我们回想一下，当初刚学树状数组时为什么很多人总会说树状数组不能用来求最值。那是因为树状数组可以看作是一种前缀和，求和时可以用ans=ans[r]-ans[l-1]的性质，但是求最值无法满足这种减法的性质。分析一下我们刚才的代码，这么写也不是不对，而是每次查询前都必须初始化，时间复杂度难以接受，让我们换一种写法试一试：

void build(int n){
     for(int i=1;i<=n;i++){
          c[i]=a[i],int t=lowbit(i);
          for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]);
    }
}

现在更新完某个数，之前的元素的值都是正确的了，显而易见，建树的时间复杂度是O(nlogn)的。

那么我们该如何修改呢？当然不能在父亲节点上直接修改啦（手动滑稽），换了一种建树的方式就是为了维护c数组的正确性，修改同样也要保证c数组的正确性，那么在更新父亲节点时，我们就需要查询它所有的儿子节点，代码如下：

void add(int pos,int x){
    a[pos]=x;
    while(pos<=n){
        c[pos]=a[pos];int t=lowbit(i); 
        for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]);
        pos+=lowbit(pos);
    }
}

不难发现，每层循环都是lowbit操作，时间复杂度为O（王逸松）O（log(n)*log(n)),其实也没多慢，当n=1e5时，logn约等于16,就把一个logn当成常数看，线段树常数也挺大的啊，树状数组代码量还这么少。

修改是修改完了，那么问题来了，我们该如何查询？

假设当前查询的区间是[l,r]，那么我们从r到l对每一个c数组的元素所控制的叶子节点进行判断。假设现在进行到了第i项，那么显然易得（看图）：该数控制的a数组的元素是 [i-lowbit(i)+1,i]。设L=i-lowbit(i)+1,R=i。如果l<=L<=r那么就将c[L]加入最值的判断中，接着L--……，否则的话就只对第R个元素加入，然后R--……，代码如下：

int query(int l,int r){
    int ans=a[r];
    while(1){
        ans=max(ans,num[r]); if(r==l) break; r--;
        while(r-l>=lowbit(r)) ans=max(ans,c[r]),r-=lowbit(r);
        //while条件里面的 r-l怎么不写成r-l+1？这才是元素个数啊。
        //写r-l+1可能会跳到0，某位大佬试了一下，电脑蓝屏了。
        //我也没有试，刨根问底（想要作死）的同学可以自己试一下 
    }
    return ans;
}

显然，时间复杂度是O(logn*logn)的。

完整代码如下：

void build(int n){
     for(int i=1;i<=n;i++){
          c[i]=a[i],int t=lowbit(i);
          for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]);
    }
}
void add(int pos,int x){
    a[pos]=x;
    while(pos<=n){
        c[pos]=a[pos];int t=lowbit(i); 
        for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]);
        pos+=lowbit(pos);
    }
}
int query(int l,int r){
    int ans=a[r];
    while(1){
        ans=max(ans,num[r]); if(r==l) break; r--;
          while(r-l>=lowbit(r)) ans=max(ans,c[r]),r-=lowbit(r);
    }
    return ans;
}

5、二维情况下的树状数组

• 单点修改+区间查询 这个我并不想讲，唯一需要注意的点写在注释里了，直接上代码：

  void add(int x,int y,int z){
  int t=y;//注意这里需要使用一个变量保存y的值 
  while(x<=n){
      y=t;
      while(y<=n) c[x][y]+=z,y+=lowbit(y);
      x+=lowbit(x); 
  }
  }
  int getsum(int x,int y){
  int ans=0,t=y;
  while(x){
      y=t;
      while(y) ans+=c[x][y],y-=lowbit(y);
      x-=lowbit(x);
  }
  return ans;
  }

• 区间修改+单点查询 在开始之前，我们先回想一下二维的前缀和如何求和：
  
  这个应该没什么问题吧？

  sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]

  那么我们和一维情形一样，开一个差分数组delta。

  delta[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]

  思路到此结束，希望大家可以自己写代码。

• 区间修改+区间查询 这里只给出一句话思路，希望大家自己思考，写出代码。

  \sum_{i=1}^x\sum_{j=1}^ya[i][j]=\sum_{i=1}^x\sum_{j=1}^y\sum_{k=1}^i\sum_{l=1}^jdelta[k][l]

  思路：将以上式子变形成类似一维情形下最终得到的式子。

• 区间最值 有这么毒瘤的题目吗……

完结撒花！★,°:.☆(￣▽￣)/$:.°★ 。

我的下一篇文章：可以代替平衡树的树状数组?——树状数组进阶(2)