树状数组:单点修改,区间最值查询

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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 对应树状数组 vecidx), 更新 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