算法数据结构

分块查找表：区间修改，区间最值查询

字数统计: 2.6k字   |   阅读时长: 11分
, ,

摘要: 分块查找表，原理与实现，解决带修改的区间最值查询问题

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

分块查找表的主要思路是对于数据数组 nums[0..n-1], 共 n 个元素，每 $\sqrt{n}$ 个元素分在一个桶内进行维护。对区间的操作可以从 $O(N)$ 降到 $O(\sqrt{N})$。桶里面的数据如何维护需要看需要实现的功能来定。

分块算法可以维护一些线段树维护不了的东西，例如单调队列等，线段树能维护的东西必须能够进行信息合并，而分块则不需要。

本文以区间最值查询问题为例，看看分块查找表的原理与实现，并形成代码模板。最后解决 699. 掉落的方块。

区间最值问题

RMQ 问题：给定一个数组，其中有 $N$ 个数字，对于一次查询，给定区间 [l ，r]，返回在这个区间内的最值为多少，一共有 $Q$ 次查询。

算法：分块查找表

对于 RMQ 问题，原始数据为 nums, 长度为 n，令 block_size = floor(sqrt{n})，将 nums 中的元素每 block_size 个一桶，并维护桶的最小值。

共有 bn = n / block_size + 1 个桶，最后一个桶的元素个数可能为 [0, block_size - 1]。原始数据与需要维护的信息组织成数据结构如下：

1
2
3
4
5
vector<int> nums;
vector<int> maxx; // maxx[block_id] := 桶的最大值
vector<int> lazy; // lazy[block_id] := 桶的懒标记
vector<bool> has_lazy; // has_lazy[block_l] := 桶的懒标记是否有效
int block_size, bn, n;

其中 maxx[0..bn], lazy[0..bn], has_lazy[0..bn] 均为块的信息。nums 中的数据直接按照下标分成各个桶，nums[i] 所属的桶 id 为 block_id = i / block_size。

然后 maxx[block_id], lazy[block_id], has_lazy[block_id] 即可访问到块的信息。这中数据组织的方式称为块状数组。

区间查询 query(i, j)

[i, j] 范围会跨若干个桶，其中：

  1. 中间有一些桶完全把区间覆盖住了，对这些桶，直接返回桶维护的最值，共 $\sqrt{N}$ 个桶。
  2. 左右两边各自可能会有一个桶与 [i, j] 重叠但是只包含了一部分区间，成其为半桶，对左右这两个半桶，如果懒标记有效，可以直接将桶维护的最值返回；如果懒标记无效，需要逐个遍历取得最值返回，一个桶共 $\sqrt{N}$ 个元素。
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
int range_query(int l, int r)
{
    int bucket_l = l / block_size, bucket_r = r / block_size;
    int result = nums[l];

    // 左半桶
    if(has_lazy[bucket_l])
        result = maxx[bucket_l];
    else
        for(int i = l; i <= min((bucket_l + 1) * block_size - 1, r); ++i)
            result = max(result, nums[i]);
    // 右半桶
    if(bucket_l != bucket_r)
    {
        if(has_lazy[bucket_r])
            result = max(result, maxx[bucket_r]);
        else
            for(int i = bucket_r * block_size; i <= r; ++i)
                result = max(result, nums[i]);
    }
    // 中间的桶
    for(int bucket_id = bucket_l + 1; bucket_id < bucket_r; ++bucket_id)
        result = max(result, maxx[bucket_id]);
    return result;
}

区间更新 update(i, j, x)

与区间查询同样，会在 [i, j] 范围内面对若干个桶，其中：

  1. 对于中间若干个把区间完全覆盖住的桶，将 x 更新到桶的懒标记 lazy, 以及桶的最大值 maxx, 并将 has_lazy 置为 true，而不对原数组修改，共 $\sqrt{N}$ 个桶。
  2. 对于左右两边各自可能会出现的半桶，如果懒标记有效，则先逐个遍历将懒标记下传，下传完成后将 has_lazy 置为 false，然后逐个遍历并直接在原数组上将值改为 x，一个桶共 $\sqrt{N}$ 个元素。
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
void range_update(int l, int r, int x)
{
    int block_l = l / block_size, block_r = r / block_size;
    // 左半桶
    if(has_lazy[block_l])
    {
        for(int i = block_l * block_size; i < min((block_l + 1) * block_size, n); ++i)
            nums[i] = lazy[block_l];
        has_lazy[block_l] = false;
    }
    for(int i = l; i <= min((block_l + 1) * block_size - 1, r); ++i)
        nums[i] = x;
    maxx[block_l] = max(maxx[block_l], x);
    // 右半桶
    if(block_l != block_r)
    {
        if(has_lazy[block_r])
        {
            for(int i = block_r * block_size; i < min((block_r + 1) * block_size, n); ++i)
                nums[i] = lazy[block_r];
            has_lazy[block_r] = false;
        }
        for(int i = block_r * block_size; i <= r; ++i)
            nums[i] = x;
        maxx[block_r] = max(maxx[block_r], x);
    }
    // 中间的桶
    for(int block_id = block_l + 1; block_id < block_r; ++block_id)
    {
        lazy[block_id] = x;
        has_lazy[block_id] = true;
        maxx[block_id] = x;
    }
}

单点更新

先将对应块的标记 lazy[i] 下传，再暴力更新被修改块的状态。时间复杂度 O(\sqrt(N))。

1
2
3
4
5
6
7
8
9
10
11
12
13
void point_update(int idx, int x)
{
    // 先将对应块的标记 `lazy[i]` 下传，再暴力更新被修改块的状态。时间复杂度 O(\sqrt(N))
    int block_id = idx / block_size;
    if(has_lazy[block_id])
    {
        for(int i = block_id * block_size; i < min((block_id + 1) * block_size, n); ++i)
            nums[i] = lazy[block_id];
        has_lazy[block_id] = false;
    }
    nums[idx] = x;
    maxx[block_id] = max(maxx[block_id], x);
}

代码 (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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
class Block
{
public:
    Block(){}

    void build(const vector<int>& arr)
    {
        nums = arr;
        n = nums.size();
        block_size = floor(sqrt(n)); // 8 -> 2, 9 -> 3, 10 -> 3, 11 -> 3, ..., 15 -> 3, 16 -> 4
        bn = n / block_size + 1; // 最后一个桶的元素个数可能为 [0, block_size - 1]
        lazy = vector<int>(bn, 0);
        maxx = vector<int>(bn, 0);
        has_lazy = vector<bool>(bn, false);
        for(int i = 0; i < n; ++i)
        {
            int block_id = i / block_size;
            maxx[block_id] = max(maxx[block_id], nums[i]);
        }
    }

    void point_update(int idx, int x)
    {
        // 先将对应块的标记 `lazy[i]` 下传，再暴力更新被修改块的状态。时间复杂度 O(\sqrt(N))
        int block_id = idx / block_size;
        if(has_lazy[block_id])
        {
            for(int i = block_id * block_size; i < min((block_id + 1) * block_size, n); ++i)
                nums[i] = lazy[block_id];
            has_lazy[block_id] = false;
        }
        nums[idx] = x;
        maxx[block_id] = max(maxx[block_id], x);
    }

    void range_update(int l, int r, int x)
    {
        // 对左右半桶，若懒标记有效，则先将懒标记 `lazy[block_l], lazy[block_r]` 下传，再暴力更新被修改块的状态。时间复杂度 O(\sqrt(N))
        int block_l = l / block_size, block_r = r / block_size;
        // 左半桶
        if(has_lazy[block_l])
        {
            for(int i = block_l * block_size; i < min((block_l + 1) * block_size, n); ++i)
                nums[i] = lazy[block_l];
            has_lazy[block_l] = false;
        }
        for(int i = l; i <= min((block_l + 1) * block_size - 1, r); ++i)
            nums[i] = x;
        maxx[block_l] = max(maxx[block_l], x);
        // 右半桶
        if(block_l != block_r)
        {
            if(has_lazy[block_r])
            {
                for(int i = block_r * block_size; i < min((block_r + 1) * block_size, n); ++i)
                    nums[i] = lazy[block_r];
                has_lazy[block_r] = false;
            }
            for(int i = block_r * block_size; i <= r; ++i)
                nums[i] = x;
            maxx[block_r] = max(maxx[block_r], x);
        }
        // 中间的桶
        for(int block_id = block_l + 1; block_id < block_r; ++block_id)
        {
            lazy[block_id] = x;
            has_lazy[block_id] = true;
            maxx[block_id] = x;
        }
    }

    int range_query(int l, int r)
    {
        // 对于中间跨过的整块，直接利用块保存的信息统计答案，两端剩余部分任然可以暴力扫描统计。
        int block_l = l / block_size, block_r = r / block_size;
        int result = nums[l];

        // 左半桶
        if(has_lazy[block_l])
            result = maxx[block_l];
        else
            for(int i = l; i <= min((block_l + 1) * block_size - 1, r); ++i)
                result = max(result, nums[i]);
        // 右半桶
        if(block_l != block_r)
        {
            if(has_lazy[block_r])
                result = max(result, maxx[block_r]);
            else
                for(int i = block_r * block_size; i <= r; ++i)
                    result = max(result, nums[i]);
        }
        // 中间的桶
        for(int block_id = block_l + 1; block_id < block_r; ++block_id)
            result = max(result, maxx[block_id]);
        return result;
    }

    vector<int> nums;
    vector<int> maxx;
    vector<int> lazy;
    vector<bool> has_lazy;
    int block_size, bn, n;
};

题目：699. 掉落的方块

在二维平面上的 x 轴上，放置着一些方块。

给你一个二维整数数组 positions ，其中 positions[i] = [lefti, sideLengthi] 表示：第 i 个方块边长为 sideLengthi ，其左侧边与 x 轴上坐标点 lefti 对齐。

每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。

在每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度 。

返回一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度。

提示：

1
2
3
1 <= positions.length <= 1000
1 <= lefti <= 1e8
1 <= sideLengthi <= 1e6

示例 1：

输入：positions = [[1,2],[2,3],[6,1]]
输出：[2,5,5]
解释：
第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 2 。
第 2 个方块掉落后，最高的堆叠由方块 1 和 2 组成，堆叠的最高高度为 5 。
第 3 个方块掉落后，最高的堆叠仍然由方块 1 和 2 组成，堆叠的最高高度为 5 。
因此，返回 [2, 5, 5] 作为答案。

示例 2：
输入：positions = [[100,100],[200,100]]
输出：[100,100]
解释：
第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 100 。
第 2 个方块掉落后，最高的堆叠可以由方块 1 组成也可以由方块 2 组成，堆叠的最高高度为 100 。
因此，返回 [100, 100] 作为答案。
注意，方块 2 擦过方块 1 的右侧边，但不会算作在方块 1 上着陆。

算法：分块查找表

共有 $N$ 个方块落下，当第 $i$ 个方块落下时，下面已经堆叠了一些方块。

第 $i$ 个方块的左端点为 pos[i][0] 边长为 pos[i][1]，因此区间为 [start, end] = [pos[i][0], pos[i][0] + pos[i][1] - 1]，我们要知道的是在已经落稳的方块中，[start, end] 这个范围的最大值是多少，这是一步区间最值查询，结果为 maxx。

然后第 $i$ 个方块落稳后，[start, end] 范围的高度更新为 maxx + pos[i][1]。更新后，查询 [0, n-1] 范围内的最值，写入 result[i] 中。

代码 (C++)

算法与代码与 线段树：区间修改(更改为定值)、区间最值查询 几乎一样，唯一区别在于维护 RMQ 的数据结构从 sttree 改为了 block。

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
class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        // 离散化
        vector<int> x;
        for(const vector<int>& pos: positions)
        {
            x.push_back(pos[0]);
            x.push_back(pos[0] + pos[1] - 1);
        }
        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end());

        int n = x.size();
        Block block;
        vector<int> arr(n);
        block.build(arr);
        vector<int> result;
        // sttree.traverse();
        for(const vector<int>& pos: positions)
        {
            int start = _find(pos[0], x);
            int end = _find(pos[0] + pos[1] - 1, x);
            int v = pos[1];
            int maxx = block.range_query(start, end);
            block.range_update(start, end, maxx + v);
            result.push_back(block.range_query(0, n - 1));
        }
        return result;
    }

private:
    int _find(int v, const vector<int>& x)
    {
        return lower_bound(x.begin(), x.end(), v) - x.begin();
    }
};
Share