算法数据结构

二维树状数组：单点修改，矩阵和查询

字数统计: 1.2k字   |   阅读时长: 6分
, ,

摘要: 二维树状数组，单点修改与矩阵查询，原理与实现

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文通以 308. 二维区域和检索 - 可变 作为模板题来看一下二维树状数组的原理与实现。

本文的树状数组支持单点修改和矩阵查询这一套需求。

模板题 308. 二维区域和检索 - 可变

给你一个二维矩阵 matrix ，处理以下类型的多个查询:

  1. 更新 matrix 中单元格的值。
  2. 计算由 左上角 (row1, col1) 和 右下角 (row2, col2) 定义的 matrix 内矩阵元素的 和。

实现 NumMatrix 类：

  • NumMatrix(int[][] matrix) 用整数矩阵 matrix 初始化对象。
  • void update(int row, int col, int val) 更新 matrix[row][col] 的值到 val 。
  • int sumRegion(int row1, int col1, int row2, int col2) 返回矩阵 matrix 中指定矩形区域元素的 和 ，该区域由 左上角 (row1, col1) 和 右下角 (row2, col2) 界定。

提示：

1
2
3
4
5
6
7
8
9
10
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-1e5 <= matrix[i][j] <= 1e5
0 <= row < m
0 <= col < n
-1e5 <= val <= 1e5
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用1e4 次 sumRegion 和 update 方法

示例 1：
输入
[“NumMatrix”, “sumRegion”, “update”, “sumRegion”]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [3, 2, 2], [2, 1, 4, 3]]
输出
[null, 8, null, 10]
解释
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // 返回 8 (即, 左侧红色矩形的和)
numMatrix.update(3, 2, 2); // 矩阵从左图变为右图
numMatrix.sumRegion(2, 1, 4, 3); // 返回 10 (即，右侧红色矩形的和)

算法：二维树状数组

回顾一维的情况

例如一个长度为 8 的数组 a ，用树状数组 b 表示的前缀和结构如下图：

树状数组中的值与原数组值的关系如下：

b[1] = a[1]
b[2] = a[1] + a[2]
b[3] = a[3]
b[4] = a[1] + a[2] + a[3] + a[4]
b[5] = a[5]
b[6] = a[5] + a[6]
b[7] = a[7]
b[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]

对 b[index] 更新(增加delta)后，会有比 index 大的某些位置也会受影响，例如更新 b[5] 之后，会依次影响到 b[6] 和 b[8]，参考图里画的树。下一个受影响的的位置是 index 加上它最低位的 1 表示的数。最低位的1表示的数，实现方法是 x & (-x)。

1
2
3
4
int _lowbit(int x)
{
    return x & (-x);
}
  • 单点查询
1
2
3
4
5
6
7
8
9
10
int query(int i)
{
    int sum = 0;
    while(i > 0)
    {
        sum += sums[i];
        i -= _lowbit(i);
    }
    return sum;
}
  • 区间查询可以通过两次单点查询得到
1
query(j + 1) - query(i);
  • 单点更新

index 上的值增加 delta 后，依次把后续受影响的位置也加上 delta。

1
2
3
4
5
6
7
8
9
void update(int index, int delta)
{
    int n = sums.size();
    while(index < n)
    {
        sums[index] += delta;
        index += _lowbit(index);
    }
}

二维树状数组的定义

在二维情况下: 数组 A 的树状数组定义为：

其中：

<1> 单点修改

1
2
3
4
5
6
7
void update(int i, int j, int delta)
{
    int n = sums.size();
    for(int x = i; x < n; x += lowbit(x))
        for(int y = j; y < n; y += lowbit(y))
            sums[x][y] += delta;
}

<2> 矩阵查询

  • 二维情况的单点查询
1
2
3
4
5
6
7
8
9
10
11
12
int query(int i, int j)
{
    int sum = 0;
    for(int x = i; x > 0 ; x -= lowbit(x))
    {
        for(int y = j; y > 0; y -= lowbit(y))
        {
            sum += sums[x][y];
        }
    }
    return sum;
}
  • 二维情况下的矩阵查询
1
query(i2 + 1, j2 + 1) - query(i1, j2 + 1) - query(i2 + 1, j1) + query(i1, j1);

代码 (C++，模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class BIT2d {
public:
    BIT2d(){}
    BIT2d(int n, int m):sums(n + 1, vector<int>(m + 1)){}

    void update(int i, int j, int delta)
    {
        int n = sums.size(), m = sums.size();
        for(int x = i; x < n; x += _lowbit(x))
            for(int y = j; y < m; y += _lowbit(y))
                sums[x][y] += delta;
    }

    int query(int i, int j)
    {
        int sum = 0;
        for(int x = i; x > 0; x -= _lowbit(x))
            for(int y = j; y > 0; y -= _lowbit(y))
                sum += sums[x][y];
        return sum;
    }

private:
    vector<vector<int> > sums;

    int _lowbit(int x)
    {
        return x & (-x);
    }
};


class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix):vec(matrix) {
        int n = matrix.size(), m = matrix[0].size();
        bit2d = BIT2d(n, m);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                bit2d.update(i + 1, j + 1, vec[i][j]);
    }

    void update(int row, int col, int val) {
        bit2d.update(row + 1, col + 1, val - vec[row][col]);
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return bit2d.query(row2 + 1, col2 + 1) - bit2d.query(row2 + 1, col1) - bit2d.query(row1, col2 + 1) + bit2d.query(row1, col1);
    }

private:
    vector<vector<int>> vec;
    BIT2d bit2d;
};
Share