树状数组全讲

Lowbit

我们定义$\operatorname{lowbit}(x)$表示 x 的二进制最低位的 1 及其后面的 0 构成的数，或者用位运算可以表示为

$$\operatorname{lowbit}(x)=x\wedge (-x)=x-x\wedge(x-1)$$

其中$x\wedge (-x)$利用了补码的性质。

树状数组

树状数组$c_1,\ldots,c_n$是基于一个序列$a_1,\ldots, a_n$建立的：

$$c_i=\sum_{j=i-\operatorname{lowbit}(i)+1}^ia_j$$

即从$j$往前数$\operatorname{lowbit}(i)$个数的和。

树状数组用于维护前缀和。广义地说，树状数组可以维护可减信息（或者不涉及到减法的信息）。

单点修改与单点查询

修改：容易想到，把包含这个点的值都更新一遍：

void add(int p,int v){
    for(int i=p;i<=n;i+=lowbit(i))c[i]+=v;
}

查询：把前缀的$\operatorname{lowbit}$段都加起来：

int pre(int p){
    int res=0;
    for(int i=p;i>0;i-=lowbit(i))res+=c[i];
    return res;
}

区间修改与单点查询

区间加上一个数，我们可以维护差分数组$d_i=a_i-a_{i-1},d_1=a_1$。于是区间修改可以转化为差分数组上两个单点修改，单点查询就转化为差分数组上前缀和查询：

/*
 * add(int,int), pre(int) 即上文所定义
 */
void add(int l,int r,int v){
    add(l,v),add(r+1,-v);
}
void query(int p){
    return pre(p);
}

区间修改与区间查询

区间查询可以转化为两个前缀和查询。则我们考虑差分数组上的前缀和查询。我们约定记号$F(\left\langle A_i\right\rangle,x)$表示在序列$\left\langle A_i\right\rangle _{i=1}^n$上的前$x$个数的和（前缀和），则可以推一推得到：

$$\begin{aligned} F(a,x)&=\sum_{i=1}^xa_i=\sum_{i=1}^x\sum_{j=1}^id_j\\ &=\sum_{j=1}^xd_j(x-j+1)\\ &=(x+1)\sum_{j=1}^xd_j-\sum_{j=1}^xd_j\cdot j\\ &=(x+1)F(\left\langle d_i\right\rangle,x)-F(\left\langle d_i\cdot i\right\rangle,x) \end{aligned}$$

于是我们维护两个数组的前缀和即可。区间修改则转化为单点修改，在两个数组上都做一遍即可。

树状数组上二分

更准确地说，是在树状数组上倍增。例如，求$\sum_{j=1}^i a_j \le T$的最大的$i$。根据树状数组的结构，我我们判断一下是否跳过下一子树，或者进入下一子树：

int find(int T){
  int cur = 0, curA = 0;
  for(int j=20; j>=0; j--){
    int nex = (1<<j) + cur;
    if(nex >= N)continue;
    int nexA = curA + A[nex];
    if(nexA <= T) cur = nex, curA = nexA:
  }
  return cur;
}

二维树状数组

推广得到，对于矩阵$[a_{ij}]_{1\le i\le n,\,1\le j\le m}$建立二维树状数组（矩阵）$[c_{ij}]$：

$$c_{ij}=\sum_{x=i-\operatorname{lowbit}(i)+1}^i\sum_{y=j-\operatorname{lowbit}(j)+1}^ja_{xy}$$

单点修改与单点查询

修改：同理：

void add(int x,int y,int v){
    for(int i=x;i<=n;i+=lowbit(i)){
        for(int j=y;j<=n;j+=lowbit(j)){
            c[i][j]+=v;
        }
    }
}

查询：同理：

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

区间修改与单点查询

这里的区间修改指修改一个子矩阵。类似的，我们也定义一个二维上的差分数组。即

$$a_{ij}=\sum_{x=1}^i\sum_{y=1}^jd_{xy}$$

而注意到

$$a_{ij-1}+a_{i-1j}-a_{i-1j-1}+d_{ij}=a_{ij}$$

于是我们得到了$d_{ij}$的公式：

$$d_{ij}=a_{ij}-a_{ij-1}-a_{i-1j}+a_{i-1j-1}$$

而区间修改，则可以转化为差分数组上 4 个单点的修改，于是有

/*
 * add(int,int,int), pre(int,int) 即上文所定义
 */
void add(int rL,int rR,int cL,int cR,int v){
    add(rL,cL,v);
    add(rL,cR+1,-v);
    add(rR+1,cL,-v);
    add(rR+1,cR+1,v);
}
void query(int x,int y){
    return pre(x,y);
}

区间修改与区间查询

我们约定记号$F([A_{ij}],x,y)$表示在矩阵$[A_{ij}]_{1\le i\le n,\,1\le j\le m}$上的$\sum_{1\le i\le x,\,1\le j\le y}A_{ij}$的和（二维前缀和）：

$$\begin{aligned} F([a_{ij}],x,y)=&\sum_{i=1}^x\sum_{j=1}^ya_{ij} =\sum_{i=1}^x\sum_{j=1}^y\sum_{p=1}^i\sum_{q=1}^jd_{pq}\\ =&\sum_{p=1}^x\sum_{q=1}^yd_{pq}(x-p+1)(y-q+1)\\ =&\sum_{p=1}^x\sum_{q=1}^yd_{pq}\left((x+1)(y+1)-(x+1)q-p(y+1)+pq\right)\\ =&(x+1)(y+1)F([d_{ij}],x,y)-(x+1)F([d_{ij}\cdot j],x,y)\\ &-(y+1)F([d_{ij}\cdot i],x,y)+F([d_{ij}\cdot i\cdot j],x,y) \end{aligned}$$

于是维护 4 个树状数组即可。单点修改的时候给 4 个都改一下。

模板

ZROI1011

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
#define lowbit(x) (x&(-x))
int n,P,q,op,las;
short s[8010][8010][4];
void add(const int & r,const int & c,const int & val){
  int a[4]={val%P,val*c%P,val*r%P,val*r*c%P};
  for(int x=r;x<=n;x+=lowbit(x))
    for(int y=c;y<=n;y+=lowbit(y))
      for(int i=0;i<4;++i)
        s[x][y][i]=((int)s[x][y][i]+a[i])%P;
}
int query(const int & r,const int & c){
  int a[4]={0,0,0,0};
  for(int x=r;x>0;x-=lowbit(x))
    for(int y=c;y>0;y-=lowbit(y))
      for(int i=0;i<4;++i)
        a[i]=(a[i]+s[x][y][i])%P;
  return ((r+1)*(c+1)%P*a[0]-(r+1)*a[1]-(c+1)*a[2]+a[3])%P;
}
int main(){
  scanf("%d%d%d",&n,&q,&P);
  while(q--){
    int rL,rR,cL,cR;
    scanf("%d%d%d%d%d",&op,&rL,&rR,&cL,&cR);
    rL=(rL+las)%n+1;
    rR=(rR+las)%n+1;
    cL=(cL+las)%n+1;
    cR=(cR+las)%n+1;
    if(rL>rR)swap(rL,rR);
    if(cL>cR)swap(cL,cR);
    if(op==1){
      add(rL,cL,1);
      add(rL,cR+1,-1);
      add(rR+1,cL,-1);
      add(rR+1,cR+1,1);
    } else {
      int ans=(query(rR,cR)-query(rL-1,cR)-query(rR,cL-1)+query(rL-1,cL-1))%P;
      ans=(ans+P)%P;
      printf("%d\n",ans),las=(las+ans)%n;
    }
  }
  return 0;
}