二维树状数组

2022-03-16 算法

单点修改
前缀和查询

树状数组的用途是高效维护前缀和，既然如此，二维树状数组自然也可以高效维护二维前缀和。

经过前面的学习应该知道，树状数组两个基本操作是单点修改以及前缀和查询，二维树状数同样也是通过这两个操作来高效维护前缀和的。接下来的内容就是基于二维树状数组的这两种操作来说明二维树状数组的用法。

单点修改

先上代码

//将点(i,j)的值加上x。n为整个矩阵的行数，m为整个矩阵的列数
void add(int i, int j, int x, int n, int m)
{
    int t;
    while (i <= n)
    {
        t = j;
        while (t <= m)
        {
            bit[i][t] += x;
            t += lowbit(t);
        }
        i += lowbit(i);
    }
}

众所周知，树状数组的第i个元素bit[i]（或者说“第i个结点”）所存的值是它在原序列中，以它为结尾，长度为lowbit(i)的子段的所有元素的和；根据这个概念，二维树状数组的bit[i][j]所存的值就是在**原矩阵中，以(i, j)为右下角顶点，且一共有lowbit(i)行，lowbit(j)列的子矩阵中，所有元素之和。**结合之前一维树状数组单点修改地操作，就能比较清晰地知道上面的代码大致是什么意思了。

前缀和查询

参考一维的前缀和查询不难写出代码

//求右下角顶点为(i, j)，左上角顶点为(1, 1)的矩阵中所有元素之和。n为整个矩阵的行数，m为整个矩阵的列数
int sum(int i, int j, int n, int m)
{
    int ret = 0, t;
    while (i > 0)
    {
        t = j;
        while (t > 0)
        {
            ret += bit[i][t];
            t -= lowbit(t);
        }
        i -= lowbit(i);
    }
    return ret;
}

下面给出基于模板题的使用例

#include <bits/stdc++.h>
using namespace std;
int bit[1030][1030];
int lowbit(int x)
{
    return x & -x;
}
void add(int i, int j, int x, int n, int m)
{
    int t;
    while (i <= n)
    {
        t = j;
        while (t <= m)
        {
            bit[i][t] += x;
            t += lowbit(t);
        }
        i += lowbit(i);
    }
}
int sum(int i, int j, int n, int m)
{
    int ret = 0, t;
    while (i > 0)
    {
        t = j;
        while (t > 0)
        {
            ret += bit[i][t];
            t -= lowbit(t);
        }
        i -= lowbit(i);
    }
    return ret;
}
int main()
{
    int n, opr, i, j, x, x1, x2, y1, y2;
    while (scanf("%d", &opr))
    {
        if (opr == 3)
            return 0;
        if (opr == 0)
        {
            scanf("%d", &n);
            continue;
        }
        if (opr == 1)
        {
            scanf("%d%d%d", &i, &j, &x);
            //由于此题给出的坐标从0开始，因此要把坐标整体都加1，不然会TLE
            add(i + 1, j + 1, x, n, n);
            continue;
        }
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        //使用二维前缀和的值计算子矩阵的和
        printf("%d\n", sum(x2 + 1, y2 + 1, n, n) + sum(x1 - 1 + 1, y1 - 1 + 1, n, n) - sum(x1 - 1 + 1, y2 + 1, n, n) - sum(x2 + 1, y1 - 1 + 1, n, n));
    }
}