单点修改、区间查询BIT

首先当然是最基础的树状数组了，单点修改、区间查询的树状数组代码

//BIT - 单点增加，区间查询 - st
struct _BIT{
    int N,C[MAXN];
    int lowbit(int x){return x&(-x);}
    void init(int n) //初始化共有n个点
    {
        N=n;
        for(int i=1;i<=N;i++) C[i]=0;
    }
    void add(int pos,int val) //在pos点加上val
    {
        while(pos<=N)
        {
            C[pos]+=val;
            pos+=lowbit(pos);
        }
    }
    int ask(int pos) //查询1~pos点的和
    {
        int ret=0;
        while(pos>0)
        {
            ret+=C[pos];
            pos-=lowbit(pos);
        }
        return ret;
    }
}BIT;
//BIT - 单点增加，区间查询 - ed

原理

假设我们现在要维护的是a数组，我们实际存储的是c数组，他们两者的关系如图

（称a数组为原数组，而c数组是a数组的树状数组。）

有

C1 = A1
C2 = A1+A2
C3 = A3
C4 = A1+A2+A3+A4
C5 = A5
C6 = A5+A6
C7 = A7
C8 = A1+A2+A3+A4+A5+A6+A7+A8

c[i]不再是简单的存储a[i]，而是存储了a[i]+a[i-1]+…+a[k]，它存储了从a[i]往前若干个元素的和，那么如何确定k呢？这就关系到lowbit函数……

lowbit(x)函数返回的是什么？

不难看出，lowbit(x)返回的是若二进制下数字 $x$ 的尾部的零的个数为 k ，则lowbit(x) = $2^k$；

也就是说，c数组中，

若i为奇数，$c\left[i\right]=a\left[i\right]$；

若i为偶数，而其最多能整除k次2，$c\left[i\right]=a\left[i\right]+a\left[i-1\right]+\cdots +a\left[i-2^k+1\right]$；

这样一来，对于某个pos点的增加$x$，只要不断令pos+=lowbit(pos)，就相当于一直往父亲节点走，所以我们在每个父亲节点都要增加$x$。

---

区间修改、单点查询BIT

其实这个的原理就是通过差分把这个区间修改、单点查询的问题转化为①；

首先，假设我们要记录的数组是$a\left[1:n\right]$，那么我们假设有$d\left[i\right]=a\left[i\right]-a\left[i-1\right]$，且$d\left[1\right]=a\left[1\right]$，

显然，就有$a\left[i\right]=d\left[1\right]+d\left[2\right]+\cdots +d\left[i\right]$，

我们在BIT中实际存储的是数组$d\left[1:n\right]$（准确的说是d数组的树状数组）；

先说修改

我们目标是给$a\left[L:R\right]$全部加上$x$，那么我们不难发现，其实$d[L+1],d[L+2],\cdots ,d\left[R\right]$都没有变化，

而变化的只有$d\left[L\right]$增加了$x$，$d\left[R+1\right]$减少了$x$；

所以只需要add(L,x),add(R+1,-x)即可。

再说查询

我们要单点查询$a\left[pos\right]$，由上可知$a\left[pos\right]=d\left[1\right]+d\left[2\right]+\cdots +d\left[pos\right]$，

那么原来的sum(pos)函数不用修改，就正好能返回$a\left[pos\right]$的值。

代码

//BIT - 区间修改，单点查询 - st
struct _BIT{
    int N,C[MAXN];
    int lowbit(int x){return x&(-x);}
    void init(int n) //初始化共有n个点
    {
        N=n;
        for(int i=1;i<=N;i++) C[i]=0;
    }
    void add(int pos,int val)
    {
        while(pos<=N) C[pos]+=val,pos+=lowbit(pos);
    }
    void range_add(int l,int r,int x) //区间[l,r]加x
    {
        add(l,x);
        add(r+1,-x);
    }
    int ask(int pos) //查询pos点的值
    {
        int ret=0;
        while(pos>0)
        {
            ret+=C[pos];
            pos-=lowbit(pos);
        }
        return ret;
    }
}BIT;
//BIT - 区间修改，单点查询 - ed

---

区间修改，区间查询BIT

这个就很骚气了，这样的BIT可以很轻松地应付线段树模板题。

我们看到，由于我们目标记录的是数组$a\left[1:n\right]$，而实际存储的是$d\left[1:n\right]$，

那么已经实现了区间修改，如何完成区间查询呢？显然，区间查询的基础是快速求数组$a\left[1:n\right]$的前缀和，

显然数组$a\left[1:n\right]$的前缀和

$a\left[1\right]+a\left[2\right]+\cdots +a\left[i\right]=d\left[1\right]\times i+d\left[2\right]\times \left(i-1\right)+\cdots +d\left[i\right]\times 1$

不难发现右侧可以化成

$\begin{array}{l}d\left[1\right]\times i+d\left[2\right]\times \left(i-1\right)+\cdots +d\left[i\right]\times 1\\ =\left[d\left[1\right]\times \left(i+1\right)+d\left[2\right]\times \left(i+1\right)+\cdots +d\left[i\right]\times \left(i+1\right)\right]-\left[d\left[1\right]\times 1+d\left[2\right]\times 2+\cdots +d\left[i\right]\times i\right]\\ =\left(i+1\right)\times \left(d\left[1\right]+d\left[2\right]+\cdots +d\left[i\right]\right)-\left(d\left[1\right]\times 1+d\left[2\right]\times 2+\cdots +d\left[i\right]\times i\right)\end{array}$

这样一来，我们就可以想到，在原来的数组$C\left[i\right]$记录$d\left[i\right]$的基础上，

再搞一个数组$C2\left[i\right]$记录$d\left[i\right]\times i$即可。（当然，实际写代码的时候要明确，C数组和C2数组都是树状数组，不是原数组）

若维护序列 $a$ 的差分数组 $b$，此时我们对 $a$ 的一个前缀 $r$ 求和，即 $\sum _{i=1}^r{a}_i$，由差分数组定义得 $a_i=\sum _{j=1}^i{b}_j$

进行推导

$$\begin{array}{rl}& \sum _{i=1}^r{a}_i\\ =& \sum _{i=1}^r\sum _{j=1}^i{b}_j\\ =& \sum _{i=1}^r{b}_i\times (r-i+1)\\ =& \sum _{i=1}^r{b}_i\times (r+1)-\sum _{i=1}^r{b}_i\times i\end{array}$$

区间和可以用两个前缀和相减得到，因此只需要用两个树状数组分别维护 $\sum b_i$ 和 $\sum i\times b_i$，就能实现区间求和。

代码

//BIT - 区间修改，区间查询 - st
struct _BIT{
    int N;
    ll C[MAXN],C2[MAXN]; //分别记录d[i]和d[i]*i
    int lowbit(int x){return x&(-x);}
    void init(int n) //初始化共有n个点
    {
        N=n;
        memset(C,0,sizeof(C));
        memset(C2,0,sizeof(C2));
    }
    void add(int pos,ll val)
    {
        for(int i=pos;i<=N;i+=lowbit(i)) C[i]+=val,C2[i]+=val*pos;
    }
    void range_add(int l,int r,ll x) //区间[l,r]加上x
    {
        add(l,x);
        add(r+1,-x);
    }
    ll ask(int pos)
    {
        ll ret=0;
        for(int i=pos;i>0;i-=lowbit(i)) ret+=(pos+1)*C[i]-C2[i];
        return ret;
    }
    ll range_ask(int l,int r) //查询区间[l,r]的和
    {
        return ask(r)-ask(l-1);
    }
}BIT;
//BIT - 区间修改，区间查询 - ed

---

二维树状数组

在一维树状数组中，数组C[x]记录了的是右端点为x、长度为lowbit(x)的区间的区间和。

那么我们也可以类似地定义C[x][y]记录的是右下角为(x,y)，高为 lowbit(x)，宽为 lowbit(y) 的区间的区间和。

这就是二维树状数组最基本的原理。

单点修改、区间查询 二维树状数组

对于一维的树状数组稍加修改，就能得到

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1005;
const int maxm=1005;

struct BIT_2D
{
    int n,m;
    ll C[maxn][maxm];
    int lowbit(int x){return x&(-x);}
    void init(int n,int m) //初始化n行m列矩阵
    {
        this->n=n;
        this->m=m;
        memset(C,0,sizeof(C));
    }
    void add(int x,int y,ll val) //在点(x,y)加上val
    {
        for(int i=x;i<=n;i+=lowbit(i))
            for(int j=y;j<=m;j+=lowbit(j)) C[i][j]+=val;
    }
    ll ask(int x,int y) //求左上角为(1,1)右下角为(x,y)的矩阵和
    {
        ll ret=0;
        for(int i=x;i>0;i-=lowbit(i))
            for(int j=y;j>0;j-=lowbit(j)) ret+=C[i][j];
        return ret;
    }
}BIT;

int main()
{
    int n=10,m=10;
    BIT.init(n,m);

    BIT.add(1,1,2);
    BIT.add(3,6,7);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cout<<BIT.ask(i,j)<<"\t";
        cout<<endl;
    }
}

区间修改、单点查询 二维树状数组

和之前的一维树状数组一样，仿照②区间查询、单点修改树状数组的操作，同样用差分的方法，将本问题转化为④-①，

由于数组$a\left[i\right]\left[j\right]$的前缀和有这样的公式

$sum\left[i\right]\left[j\right]=\left(sum\left[i-1\right]\left[j\right]+sum\left[i\right]\left[j-1\right]-sum\left[i-1\right]\left[j-1\right]\right)+a\left[i\right]\left[j\right]$

套用求前缀和的形式，假设差分数组为$d\left[i\right]\left[j\right]$，可以有

$a\left[i\right]\left[j\right]=\left(a\left[i-1\right]\left[j\right]+a\left[i\right]\left[j-1\right]-a\left[i-1\right]\left[j-1\right]\right)+d\left[i\right]\left[j\right]$

就能得到

$d\left[i\right]\left[j\right]=a\left[i\right]\left[j\right]-\left(a\left[i-1\right]\left[j\right]+a\left[i\right]\left[j-1\right]-a\left[i-1\right]\left[j-1\right]\right)$

那么，同样先说修改

目标是给$\left(x_1,y_1\right)$到$\left(x_2,y_2\right)$的矩阵全部加上$x$，不难发现，差分数组变动的只有四个点

$d\left[x_1\right]\left[y_1\right]+=x,d\left[x_1\right]\left[y_2+1\right]-=x,d\left[x_2+1\right]\left[y_1\right]-=x,d\left[x_2+1\right]\left[y_2+1\right]+=x$

这个可以自己举个栗子验证一下。

再说查询

同一维树状数组一样，求左上角为$\left(1,1\right)$右下角为$\left(x,y\right)$的矩阵和就是d[x][y]的前缀和，正好就是要查询的a[x][y]。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1005;
const int maxm=1005;

struct BIT_2D
{
    int n,m;
    ll C[maxn][maxm];
    int lowbit(int x){return x&(-x);}
    void init(int n,int m) //初始化n行m列矩阵
    {
        this->n=n;
        this->m=m;
        memset(C,0,sizeof(C));
    }
    void add(int x,int y,ll val)
    {
        for(int i=x;i<=n;i+=lowbit(i))
            for(int j=y;j<=m;j+=lowbit(j)) C[i][j]+=val;
    }
    void range_add(int x1,int y1,int x2,int y2,ll x) //左上角为(x1,y1)右下角为(x2,y2)的矩阵全部加上x
    {
        add(x1,y1,x);
        add(x1,y2+1,-x);
        add(x2+1,y1,-x);
        add(x2+1,y2+1,x);
    }
    ll ask(int x,int y) //查询点(x,y)的值
    {
        ll ret=0;
        for(int i=x;i>0;i-=lowbit(i))
            for(int j=y;j>0;j-=lowbit(j)) ret+=C[i][j];
        return ret;
    }
}BIT;

int main()
{
    int n=10,m=10;
    BIT.init(n,m);

    BIT.range_add(2,2,4,4,1);
    BIT.range_add(5,6,8,8,2);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cout<<BIT.ask(i,j)<<"\t";
        cout<<endl;
    }
}

区间修改、区间查询 二维树状数组

又到了最亦可赛艇的部分了！依然仿照③区间查询、区间修改 树状数组的操作。

首先$sum\left[i\right]\left[j\right]=\sum _{x=1}^i\sum _{y=1}^{j}a\left[x\right]\left[y\right]$，

又由于$a\left[x\right]\left[y\right]=\sum _{u=1}^x\sum _{v=1}^{y}d\left[u\right]\left[v\right]$，

所以有

$sum\left[i\right]\left[j\right]=\sum _{x=1}^i\sum _{y=1}^j\left(\sum _{u=1}^x\sum _{v=1}^{y}d\left[u\right]\left[v\right]\right)$

可以说是非常复杂了……

但模仿③的操作，我们依然可以统计d[u][v]出现次数

不难想象，从$a\left[1\right]\left[1\right]$到$a\left[i\right]\left[j\right]$，$d\left[1\right]\left[1\right]$全部都要出现一次，所以有$i\times j$个$d\left[1\right]\left[1\right]$，即$d\left[1\right]\left[1\right]\times i\times j$

类似的，有$d\left[1\right]\left[2\right]\times i\times \left(j-1\right),d\left[2\right]\left[1\right]\times \left(i-1\right)\times j,d\left[2\right]\left[2\right]\times \left(i-1\right)\times \left(j-1\right)$ 等等等等……

所以我们不难把式子变成

$sum\left[i\right]\left[j\right]=\sum _{x=1}^i\sum _{y=1}^j\left[d\left[x\right]\left[y\right]\times \left(i+1-x\right)\times \left(j+1-y\right)\right]$

展开得到

$sum\left[i\right]\left[j\right]=\sum _{x=1}^i\sum _{y=1}^j\left[d\left[x\right]\left[y\right]\cdot \left(i+1\right)\left(j+1\right)-d\left[x\right]\left[y\right]\cdot x\left(j+1\right)-d\left[x\right]\left[y\right]\cdot \left(i+1\right)y+d\left[x\right]\left[y\right]\cdot xy\right]$

也就相当于把这个式子拆成了四个部分

$\begin{array}{l}\left(i+1\right)\left(j+1\right)\times \sum _{x=1}^i\sum _{y=1}^{j}d\left[x\right]\left[y\right]\\ -\left(j+1\right)\times \sum _{x=1}^i\sum _{y=1}^j\left(d\left[x\right]\left[y\right]\cdot x\right)\\ -\left(i+1\right)\times \sum _{x=1}^i\sum _{y=1}^j\left(d\left[x\right]\left[y\right]\cdot y\right)\\ \sum _{x=1}^i\sum _{y=1}^j\left(d\left[x\right]\left[y\right]\cdot xy\right)\end{array}$

所以我们需要在原来 $C1\left[i\right]\left[j\right]$ 记录 $d\left[i\right]\left[j\right]$ 的基础上，再添加三个树状数组

$C2\left[i\right]\left[j\right]$ 记录 $d\left[i\right]\left[j\right]\cdot i$

$C3\left[i\right]\left[j\right]$ 记录 $d\left[i\right]\left[j\right]\cdot j$

$C4\left[i\right]\left[j\right]$ 记录 $d\left[i\right]\left[j\right]\cdot ij$

这样一来，就能通过数组$a\left[i\right]\left[j\right]$的差分数组$d\left[i\right]\left[j\right]$来得到$a\left[i\right]\left[j\right]$的前缀和数组$sum\left[i\right]\left[j\right]$，

最后，易知$\left(x_1,y_1\right)$到$\left(x_2,y_2\right)$的矩阵和就等于$sum\left[x_2\right]\left[y_2\right]-sum\left[x_2\right]\left[y_1-1\right]-sum\left[x_1-1\right]\left[y_2\right]+sum\left[x_1-1\right]\left[y_1-1\right]$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1005;
const int maxm=1005;

struct BIT_2D
{
    int n,m;
    ll C1[maxn][maxm],C2[maxn][maxm],C3[maxn][maxm],C4[maxn][maxm];
    int lowbit(int x){return x&(-x);}
    void init(int n,int m) //初始化n行m列矩阵
    {
        this->n=n;
        this->m=m;
        memset(C1,0,sizeof(C1));
        memset(C2,0,sizeof(C2));
        memset(C3,0,sizeof(C3));
        memset(C4,0,sizeof(C4));
    }
    void add(int x,int y,ll val)
    {
        for(int i=x;i<=n;i+=lowbit(i))
        {
            for(int j=y;j<=m;j+=lowbit(j))
            {
                C1[i][j]+=val;
                C2[i][j]+=val*x;
                C3[i][j]+=val*y;
                C4[i][j]+=val*x*y;
            }
        }
    }
    void range_add(int x1,int y1,int x2,int y2,ll x) //左上角为(x1,y1)右下角为(x2,y2)的矩阵全部加上x
    {
        add(x1,y1,x);
        add(x1,y2+1,-x);
        add(x2+1,y1,-x);
        add(x2+1,y2+1,x);
    }
    ll ask(int x,int y) //查询左上角为(1,1)右下角为(x,y)的矩阵和
    {
        ll ret=0;
        for(int i=x;i>0;i-=lowbit(i))
        {
            for(int j=y;j>0;j-=lowbit(j))
            {
                ret+=(x+1)*(y+1)*C1[i][j];
                ret-=(y+1)*C2[i][j]+(x+1)*C3[i][j];
                ret+=C4[i][j];
            }
        }
        return ret;
    }
    ll range_ask(int x1,int y1,int x2,int y2) //查询左上角为(x1,y1)右下角为(x2,y2)的矩阵和
    {
        return ask(x2,y2)-ask(x1-1,y2)-ask(x2,y1-1)+ask(x1-1,y1-1);
    }
}BIT;

int main()
{
    int n=10,m=10;
    BIT.init(n,m);

    BIT.range_add(2,2,4,4,1);
    BIT.range_add(5,6,8,8,2);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cout<<BIT.range_ask(i,j,i,j)<<"\t";
        cout<<endl;
    }
    cout<<BIT.range_ask(2,2,4,4)<<endl;
    cout<<BIT.range_ask(5,6,8,8)<<endl;
    cout<<BIT.range_ask(2,2,8,8)<<endl;
}

---

本文主要参考https://www.cnblogs.com/RabbitHu/p/BIT.html