三维树状数组

说明

c[]为三维树状数组

n为数组的下标最大值

使用方法

  1. memset(c, 0, sizeof(c));
  2. N赋值
  3. update(posx, posy. posz, val); 给数组中下标为[posx][posy][posz]的位置更新val
  4. sum(x, y, z, xx, yy, zz); 求数组中下标为(x, y, z)(xx, yy, zz)为对角线顶点的区域元素之和

Tips

  • 树状数组无法更新下标为0的数
  • 分清树状数组的操作是更新、修改、取最大/最小值等
  • 用树状数组时经常需要离散化

模版

int N;
long long c[130][130][130]= {};
inline int lowbit(int t)
{
    return t&(-t);
}
void update(int x,int y,int z,long long v)
{
    for (int i=x; i<=N; i+=lowbit(i))
        for (int j=y; j<=N; j+=lowbit(j))
            for (int k=z; k<=N; k+=lowbit(k))
                c[i][j][k]+=v;
}
long long query(int x,int y,int z)
{
    long long s=0;
    for (int i=x; i>0; i-=lowbit(i))
        for (int j=y; j>0; j-=lowbit(j))
            for (int k=z; k>0; k-=lowbit(k))
                s+=c[i][j][k];
    return s;
}
long long sum(int x,int y,int z,int xx,int yy,int zz)
{
    x--,y--,z--;
    return query(xx,yy,zz)
    -query(x,yy,zz)-query(xx,y,zz)-query(xx,yy,z)
    +query(x,y,zz)+query(xx,y,z)+query(x,yy,z)
    -query(x,y,z);
}

results matching ""

    No results matching ""