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);
    }
};