二维树状数组

说明

c[]为二维树状数组

n为数组的下标最大值

使用方法

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

Tips

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

模版

int N;
int c[maxn][maxn];
inline int lowbit(int t)
{
    return t&(-t);
}
void update(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 query(int x,int y)
{
    int s=0;
    for (int i=x; i>0; i-=lowbit(i))
        for (int j=y; j>0; j-=lowbit(j))
            s+=c[i][j];
    return s;
}
int sum(int x,int y,int xx,int yy)
{
    x--,y--;
    return query(xx,yy)-query(xx,y)-query(x,yy)+query(x,y);
}

results matching ""

    No results matching ""