树状数组

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog

一维树状数组

笔者眼中的一维树状数组

        一维树状数组,是一棵左偏树,他的每一个节点,维护的是一段区间的和,若该节点的 下标为i,那么他维护的区间就是(i&(i-1),i] ,熟悉位运算的人应该都知道,i&(i-1)与i的关系:i&(i-1)和i去掉i的二进制中的最低位的1后的值 相等。并且,树状数组就是做单点修改,前缀区间查询的数据结构。 为了利 于描述,下文暂时称一维树状数组为树状数组

树状数组询问操作

        原数组的前缀区间查询,根据定义,我们很容易知道,区间[1,x] 一定能够被树状数组的某些节点所表示的区间 并来表达,且唯一表达,且表达式最多lg(x)项,因为x的二进制中最多lg个1。于是任意前缀区间就能够在树状数组中查询得到。

树状数组更新操作

        原数组的点修改,我们必须找到所有包含了该点的树状数组节点,若要修改的点的下标为i,根据定义我们解不等式 (x&(x-1))+1<=i<=x,可以证明可以证明如果a是一个解,且存在另一个大于a的最小的解b,则b=a+a&-a。于是我们根据此操作 一步一步去更新树状数组节点即可,此节点数目lg级别

树状数组的用途

        根据定义,我们可以很容易的维护很多关于单点修改,前缀区间查询的操作,比如前缀最值、 前缀区间和。

区间加法与区间减法

        如果对于作用于区间[x,y]上的区间运算f(x,y)满足 若对于所有的a<b<=c可以根据f(a,b-1)和f(b,c)算出 f(a,c),则此运算满足区间加法
        如果对于作用于区间[x,y]上的区间运算f(x,y)满足 若对于所有的a<b<=c可以根据f(a,c)和f(b,c)算出 f(a,b-1),则此运算满足区间减法

让用途更广

        对于所有满足区间减法的操作,比如说:区间和,区间异或和。我们可以根据前缀区间 相减,得到任意区间的区间和与区间异或和。

差分操作

        如果我们要对一个区间进行修改,我们有这样一种做法,在区间起点加一个标记,在区间末尾 再加一个标记,于是我们就表面修改了此数组的一个区间,查询的话,查前缀和就可以了,由于本文重点不在此,简要 举个例子,对于一个数组,我们如果说要经常修改某些区间的值:整个区间的所有元素加上一个d,我们可以考虑这样做,让区间起点+d,区间末尾右边的元素-d, 当修改完之后,我们对此数组做一遍前缀和就能得到修改结果。我们称表面修改的数组为差分数组,差分数组的前缀和就是我们要的原数组。

再广一点

        考虑一个维护区间和的数组,如果要对随机区间修改,对单点查询怎么办呢?我们维护此数组 的差分数组,原数组的区间修改就是差分数组的点修改,原数组的点查询就是差分数组的前缀区间查询,于是我们解决了这个问题

还能更加广

        如果我们不仅仅满足与点查询,我们还要前缀和区间查询,也能办到,再来理一下,原数组的前缀 和区间查询等于差分数组的二阶前缀和区间查询,我们假定a为差分数组:
\sum_{i=1}^{N}\sum_{j=1}^{i} a_{j}=\sum_{j=1}^{N} (N+1-j)a_{j} =(N+1)\sum_{j=1}^{N} a_{j}-\sum_{j=1}^{N} ja_{j}
这里很明显了,我们维护一个原数组的差分数组ai和另一个数组i*ai的点修改区间查询即可。

二维树状数组

提升纬度

        我们定义,在二维数据结构中,让点(x,y)维护点(x&(x-1)+1,y&(y-1)+1)到(x,y)的矩阵的区间信息,根据 之前的推导,使用类似的方法,可以得出在每一维上最多lg个节点,故两维一起最多lg*lg个节点。类似的也可以得出更新的时候,节点依旧是lg*lg个。

二维的差分和任意区间维护此处不做细分析

        如果我们维护了二维前缀区间定义前缀区间为:(1,1)到(x,y) 的矩形区间。的信息,根据容斥原理,任意区间很容易算出来了,差分是一样的。

二维的区间修改,区间和查询

        一样的,是差分数组的二阶前缀和,化简公式如下:

于是我们维护四个普通树状数组即可
struct Binary_Indexed_Tree{
    //点更新区间查询,最大可用范围[1,N),实际使用[1,n]
    //初始化N,n,初始化tree[]为0
    //函数输入,函数返回值输出
    static const int N;
    int n,tree[N];

    void ini(int _n){
        n=_n;
        for(int i=1;i<=n;i++)tree[i]=0;
    };
    void add(int k,int d){for(int i=k;i<=n;i+=i&-i)tree[i]+=d;}
    int sigma(int k){
        int ret=0;
        for(int i=k;i;i-=i&-i)ret+=tree[i];
        return ret;
    }
    int sigma(int u,int v){return sigma(v)-sigma(u-1);}
};

struct Binary_Indexed_Tree{
    //区间更新点查询,最大可用范围[1,N),实际使用[1,n]
    //初始化N,n初始化tree[]为0
    //函数输入,函数返回值输出
    static const int N;
    int n,tree[N];

    void ini(int _n){
        n=_n;
        for(int i=1;i<=n;i++)tree[i]=0;
    };
    void add(int k,int d){for(int i=k;i<=n;i+=i&-i)tree[i]+=d;}
    void add(int u,int v,int d){
        add(u,d);
        add(v+1,-d);
    }
    int sigma(int k){
        int ret=0;
        for(int i=k;i;i-=i&-i)ret+=tree[i];
        return ret;
    }
};

struct Binary_Indexed_Tree{
    //区间更新区间查询,最大可用范围[1,N),实际使用[1,n]
    //初始化N,n初始化tree[]、tree2[]为0
    //函数输入,函数返回值输出
    static const int N;
    int n,tree[N],tree2[N];

    void ini(int _n){
        n=_n;
        for(int i=1;i<=n;i++)tree[i]=0;
    };
    void add(int k,int d){
        for(int i=k;i<=n;i+=i&-i)tree[i]+=d,tree2[i]+=k*d;
    }
    void add(int u,int v,int d){
        add(u,d);
        add(v+1,-d);
    }
    int sigma(int k){
        int ret=0;
        for(int i=k;i;i-=i&-i)ret+=(k+1)*tree[i]-tree2[i];
        return ret;
    }
    int sigma(int u,int v){
        return sigma(v)-sigma(u-1);
    }
};


struct Binary_Indexed_Tree{
    //二维点更新区间查询,最大可用范围[1,N)[1,N),实际使用[1,n]
    //初始化N,n初始化tree[][]为0
    //函数参数输入,函数返回值输出
    static const int N;
    int n, tree[N][N];
    void ini(int _n){
        n=_n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                tree[i][j]=0;
            }
        }
    }
    void add(int x,int y,int d){
        for(int i=x;i<=n;i+=i&-i)
            for(int j=y;j<=n;j+=j&-j)
                tree[i][j]+=d;
    }
    int sigma(int x,int y){
        int ret=0;
        for(int i=x;i;i-=i&-i)
            for(int j=y;j;j-=j&-j)
                ret+=tree[i][j];
        return ret;
    }
    int sigma(int x1,int y1,int x2,int y2){
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
        x1--;y1--;
        return sigma(x1,y1)+sigma(x2,y2)-sigma(x1,y2)-sigma(x2,y1);
    }
};

struct Binary_Indexed_Tree{
    //二维区间更新点查询,最大可用范围[1,N)[1,N),实际使用[1,n]
    //初始化N,n初始化tree[][]为0
    //函数参数输入,函数返回值输出
    static const int N;
    int n,tree[N][N];
    void ini(int _n){
        n=_n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                tree[i][j]=0;
            }
        }
    }
    void add(int x,int y,int d){
        for(int i=x;i<=n;i+=i&-i)
            for(int j=y;j<=n;j+=j&-j)
                tree[i][j]+=d;
    }
    void add(int x1,int y1,int x2,int y2,int d){
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
        add(x1,y1,d);
        add(x2+1,y2+1,d);
        add(x1,y2+1,-d);
        add(x2+1,y1,-d);
    }
    int sigma(int x,int y){
        int ret=0;
        for(int i=x;i;i-=i&-i)
            for(int j=y;j;j-=j&-j)
                ret+=tree[i][j];
        return ret;
    }
};

struct Binary_Indexed_Tree{
    //二维区间更新区间查询,最大可用范围[1,N)[1,N),实际使用[1,n]
    //初始化N,n初始化tree[][]、treeij[][]、treei[][]、treej[][]为0
    //函数参数输入,函数返回值输出
    static const int N;
    int n,tree[N][N],treeij[N][N],treei[N][N],treej[N][N];

    void ini(int _n){
        n=_n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                tree[i][j]=treei[i][j]=treej[i][j]=treeij[i][j]=0;
            }
        }
    }
    void add(int x,int y,int d){
        for(int i=x;i<=n;i+=i&-i)
            for(int j=y;j<=n;j+=j&-j){
                tree[i][j]+=d;
                treei[i][j]+=x*d;
                treej[i][j]+=y*d;
                treeij[i][j]+=x*y*d;
            }
    }
    void add(int x1,int y1,int x2,int y2,int d){
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
        x2++,y2++;
        add(x1,y1,d);
        add(x2,y2,d);
        add(x1,y2,-d);
        add(x2,y1,-d);
    }
    int sigma(int x,int y){
        int ret=0;
        for(int i=x;i;i-=i&-i)
            for(int j=y;j;j-=j&-j){
                ret+=(x+1)*(y+1)*tree[i][j]+treeij[i][j];
                ret-=(x+1)*treej[i][j]+(y+1)*treei[i][j];
            }
        return ret;
    }
    int sigma(int x1,int y1,int x2,int y2){
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
        x1--,y1--;
        return sigma(x1,y1)+sigma(x2,y2)-sigma(x2,y1)-sigma(x1,y2);
    }
};