如何高效实现二维树状数组

小蓝 • 2024-12-12 12:22 • 编程

一、树状数组的介绍

树状数组，又叫二叉索引树，是一种数据结构，用于高效地进行单点更新和区间查询。树状数组主要用于处理静态或动态数组的前缀和，即快速求出一个数组前缀中所有元素的和。

树状数组可以将普通数组中的前缀和转化为数据结构中的前缀和，这样就可以快速查询区间和，并且支持快速单点修改操作。树状数组的优点在于其空间复杂度低，实现简单，而且复杂度都是 O(log n) 级别，因此广泛应用于各类问题的求解。

二、二维树状数组的原理

对于二维的情况，可以将树状数组中的一维数组再当成树状数组处理，建立起二维树状数组，用于处理二维数组的前缀和，即可以快速查询二维数组中矩形区间的和等问题。二维树状数组的建立和查询都与一维树状数组类似，只是需要对于两个维度分别进行处理。具体实现时，可以将二维数组中的行和列都进行处理，分别建立两个一维树状数组。这样，在进行矩形区间查询时，则可以将其转化为四个一维区间查询问题。

三、如何高效实现二维树状数组

1. 初始化和更新操作

int lowbit(int x) {
    return x & -x; // 求 x 的二进制中最低位的 1 所对应的值
}

void update2D(int x, int y, int k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        for (int j = y; j <= m; j += lowbit(j)) {
            c[i][j] += k;
        }
    }
}

对于二维树状数组的初始化和更新操作，同样需要使用 lowbit 函数来区分每一个区间。在此，我们定义 lowbit 函数为求一个二进制数中末尾 1 的位置，得到的结果即为取余时当前区间的长度。

2. 查询操作

int query2D(int x, int y) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        for (int j = y; j > 0; j -= lowbit(j)) {
            res += c[i][j];
        }
    }
    return res;
}

int query2DRange(int x1, int y1, int x2, int y2) {
    return query2D(x2, y2) - query2D(x2, y1 - 1) - query2D(x1 - 1, y2) + query2D(x1 - 1, y1 - 1);
}

对于二维树状数组的查询操作，需要进行一个四个区间的操作。在此，我们需要两个一维树状数组 c1 和 c2 分别维护行和列方向的前缀和，然后可以通过对四个点的坐标进行四个区间的加减计算得到对应的矩阵区间和。

四、总结

二维树状数组是一种十分实用的数据结构，可以方便地处理二维数组的前缀和和矩形区间查询等问题。在实现时，需要注意横纵坐标的区分，以及维护两个一维树状数组分别用于维护行和列的前缀和，然后再进行四个区间的加减汇总操作。在实际应用中，二维树状数组能够较为高效地解决一些问题，因此在需要处理二维数组的前缀和等问题时，可以考虑使用二维树状数组。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/240753.html