算法数据结构

树状数组：单点修改，区间最值查询

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

摘要: 线段树和树状数组，单点修改与区间查询，原理与实现

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

考虑以下需求：给定一个数组 a，支持区间和的查询, 其中 a 中的元素可变，每次变化 a 中的 1 个元素。

这个需求用带单点修改和区间查询的线段树或树状数组都可以解决，其中用树状数组的代码量少很多。

如果 a 不变，则是前缀和解决的问题。而对于 a 可变的情况，区间和查询是树状数组解决的最基本的问题，它在力扣上有对应的题目：

现在需求变一下，把支持区间和的查询改成支持区间最大值的查询。

如果 a 不变，则常见解法是用基于倍增优化 DP 的稀疏表。如果 a 可变，有几种主流的方案: 线段树，树状数组，分块。

树状数组做带单点修改的区间最值的查询也是可做的，只是比区间和的需求复杂一些。

回顾：用树状数组解决区间和

更新

更新的接口：update(int idx, int delta), 数组元素 a[idx - 1] 的值加上 delta，然后更新树状数组 vec 的值(数组 a 的元素 idx - 1 对应树状数组 vec 的 idx), 更新 vec 中与 idx 相关的节点的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
for(int i = idx; i < n; i += lowbit(i))
{
    // n 是树状数组 vec 的长度
    vec[i] += delta;
}

// 或者 while 循环
while(idx < n) 
{
    vec[idx] += delta;
    idx += lowbit(idx);
}

查询

查询的接口：query(idx), 返回前缀 [0..idx-1] 的和, 如果要求求区间 [l, r] 的和，可以求两次前缀的和再相减: query(r + 1) - query(l), 汇总与 idx 相关的节点值的代码：

1
2
3
4
5
6
7
8
9
for(int i = idx; i > 0; i -= lowbit(i))
    sum += vec[i];

// 或者 while 循环
while(i > 0)
{
    sum += vec[i];
    i -= lowbit(i);
}

用树状数组解决区间最值

更新

更新的接口：update(int idx, int val), 数组元素 a[idx - 1] 的值改为 val。

改了 a[idx - 1] 之后，与区间和的情况相同，也是要修改所有与 vec[idx] 相关的节点的值。

树状数组的节点 vec[idx] 负责的是区间 [idx - lowbit(idx) + 1, idx]，vec[idx] 修改之后，会对 idx 的所有父节点有影响，这点与区间和的情况一样。

在区间和中，通过 idx += lowbit(idx) 找到所有父节点之后，直接将节点值加上 delta 就可以了，但是区间最值不行。

以最大值为例，某次修改将 a[idx - 1] 变了，待修改节点是 vec[idx] 以及其父亲链上的节点，但是 a[idx - 1] 不一定会影响到这些节点值。

对于任意一个待修改节点 i, 其所有子节点的值，以及 i 对应的数据 a[i - 1] 本身的值共同决定了最大值 vec[i]。因此要考察其所有子节点，记录最大值。

1
2
3
// 当前待修改节点为 i, i - 2^k 是其各个子节点(2^k < lowbit(i))
for(int j = 1; j < lowbit(i); j <<= 1)
    vec[i] = max(vec[i], vec[i - j])

因此完整的更新过程如下, 总时间复杂度 $O(\log^{2}N)$： 

1
2
3
for(int i = idx; i < n; i += lowbit(i))
    for(int j = 1; j < lowbit(i); j <<= 1)
        vec[i] = max(vec[i], vec[i - j]);

例如若要更新 vec[8], 需要查看 vec[7](负责区间$[7,7]$)，vec[6](负责区间$[5,6]$), vec[4](负责区间$[1,4]$)。

查询

查询的接口: query(int l, int r), 查询时，直接对区间 [l, r] 统计答案，而不是分别求两次前缀的答案再做差，这一点与区间和的情况区别较大。

vec[r] 表示的是区间 [r - lowbit(r) + 1, r] 的最大值，记 i = r - lowbit(r) + 1：

  • (1) 如果 i = l, 则可以返回 vec[r], 即为当前 [l, r] 的最大值。
  • (2) 如果 i < l, 则 vec[r] 记录的 [i, r] 的最值可能来自 [i..l-1] 这一部分(对应 a[i-1..l])，因此只能从原数据 a 中取出对应值 a[r - 1] 并统计答案(这里要用到原数组，而区间和的需求不需要), 然后 —r 之后继续统计。
  • (3) 如果 i > l, 则 vec[r] 记录的 [i, r] 的最值完整地影响待查询区间，因此直接统计答案即可，之后 r -= lowbit(r) 更新 r 到所负责区间左端点的前一个点，继续统计

完整过程如下：

1
2
3
4
5
6
7
8
9
int ans = a[r - 1];
while(true)
{
    ans = max(ans, a[r - 1]); // (2)
    if(l == r) break; // (1)
    --r;
    for(; l <= r - lowbit(r); r -= lowbit(r))
        ans = max(ans, vec[r]) // (3)
}

以下代码更直观，但比较冗长：

1
2
3
4
5
6
7
8
9
10
11
12
while(true)
{
    for(; r - _lowbit(r) + 1 > l; r -= _lowbit(r)) // (3)
        ans = max(ans, vec[r]);
    if(r - _lowbit(r) + 1 == l) // (1)
    {
        ans = max(ans, vec[r]);
        break;
    }
    ans = max(ans, a[r - 1]); // (2)
    --r;
}

将以上分析过程综合起来，就得到用带单点修改的树状数组做区间最值查询的代码。

代码 (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
class BIT_RMQ
{
public:
    BIT_RMQ():vec(1,0),a(1,0){}
    BIT_RMQ(int n):vec(n + 1, 0),a(n,0){}

    void update(int idx, int x)
    {
        // vec[idx] 管的是 [idx-lowbit[idx] + 1..idx] 这个区间
        // a[idx -  1] 改为 x
        // vec[idx]
        a[idx - 1] = x;
        vec[idx] = x;
        int n = a.size();
        for(int i = idx; i <= n; i += _lowbit(i))
        {
            for(int j = 1; j < _lowbit(i); j <<= 1)
            {
                // j < _lowbit(i) <= j - i < _lowbit(i) - i <= i - j > i - _lowbit(i)
                // i = 8，即改 vec[8]
                // 要看 vec[7] = i - 1
                //      vec[6] = i - 2
                //      vec[4] = i - 4
                vec[i] = max(vec[i], vec[i - j]);
            }
        }
    }

    int query(int l, int r)
    {
        // 直接看 vec[r] 不行
        // vec[r] 对应 [r - lowbit[r] + 1, r]
        int ans = a[r - 1];
        while(true)
        {
            ans = max(ans, a[r - 1]);
            if(l == r)
                break;
            --r;
            for(; r - _lowbit(r) >= l; r -= _lowbit(r))
                ans = max(ans, vec[r]);
        }
        return ans;
    }

    void view()
    {
        int n = a.size();
        for(int i = 0; i < n; ++i)
            cout << a[i] << " ";
        cout << endl;
        for(int i = 1; i <= n; ++i)
            cout << vec[i] << " ";
        cout << endl;
    }

private:
    vector<int> vec;
    vector<int> a;

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

模板题

求最大值

给出一个序列，你的任务是求每次操作之后序列中 (a[j]-a[i])/(j-i)，1<=i<j<=n 的最大值。

操作次数有 Q 次，每次操作需要将位子 p 处的数字变成 y.

1
2
3
4
5
6
7
8
9
10
11
12
数据范围：
3<=n<=2e5
1<=Q<=2e5
-1e9<=a[i]<=1e9

输入描述:
本题包含多组输入，每组输入第一行一个数字 n，表示序列的长度。
然后接下来一行输入 n 个数，表示原先序列的样子。
再接下来一行一个数字 Q，表示需要进行的操作的次数。
最后 Q 行每行两个元素 p，y，表示本操作需要将位子p处的数字变成.y.
输出描述:
每组数据输出Q行，每行输出一个浮点数，保留两位小数，表示所求的最大值。

示例1
输入
5
2 4 6 8 10
2
2 5
4 9
输出
3.00
3.00
说明
第一次操作之后的序列变成：2 5 6 8 10
第二次操作之后的序列变成：2 5 6 9 10

算法：树状数组

本题要求最大的斜率 $\frac{a[j] - a[i]}{j-i}$。首先我们证明最大斜率一定出现在 $i,j$ 相邻的两个点之间。也就是说一定存在某个相邻点 $j = i + 1$，它们之间的斜率可以取到最大值，最大值为 $a[i+1] - a[i]$。

反证：

假设相邻的两个点之间一定取不到最大斜率。记最大斜率出现在不相邻的两个点 $i_{0}, j_{0}$ 之间，$k_{0} = \frac{a[j_{0}] - a[i_{0}]}{j_{0} - i_{0}}$，$j_{0} > i_{0} + 1$。

记 $c = i_{0} + 1$，考察 $a[i_{0}]$ 和 $a[c]$ 之间的斜率 $k_{1} = \frac{a[c] - a[i_{0}]}{c - i_{0}}$，以及 $a[c]$ 和 $a[j_{0}]$ 之间的斜率 $k2 = \frac{a[j_{0}] - a[c]}{j_{0} - c}$。

于是我们有 $k_{0} > k_{1}$，$k_{0} \geq k_{2}$、代入，展开，然后将两个不等式相加，得到：

化简后为 $0 > 0$，矛盾。$\Box$

因此我只需要取 $a[i+1] - a[i]$ 的最大值即为答案。记 $diff[i] = a[i+1] - a[i]$。

每次修改 $a[p] = y$ 之后，修改受到影响的 $diff[p] = a[p+1] - a[p]$，以及 $diff[p-1] = a[p] - a[p-1]$。然后输出一次 $diff$ 整个区间上的最大值。

这个过程是单点修改，区间查询最值的问题。可以用树状数组解决。

代码 (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
#include <iostream>
#include <vector>
#include<iomanip>
#include <iostream>

using namespace std;

int main()
{
    int n;
    while(cin >> n && n > 0)
    {
        vector<int> a(n);
        for(int i = 0; i < n; ++i)
            cin >> a[i];
        BIT_RMQ bit_rmq(n);
        for(int i = 0; i < n - 1; ++i)
        {
            bit_rmq.update(i + 1, a[i + 1] - a[i]);
        }
        int Q;
        cin >> Q;
        for(int i = 0; i < Q; ++i)
        {
            int p, y;
            cin >> p >> y;
            p--;
            a[p] = y;
            if(p > 0)
                bit_rmq.update(p, a[p] - a[p-1]);
            if(p < n - 1)
                bit_rmq.update(p + 1, a[p + 1] - a[p]);
            cout << fixed << setprecision(2) << (double)bit_rmq.query(1, n - 1) << endl;
        }
    }
}
Share