问题的提出
给定一个数组,执行两种操作:
- 1)修改一个元素的值,
- 2)查询一个区间的和。
直接暴力求解
直接用一个数组来实现。即:
- 修改:直接修改对应元素的值。复杂度为O(1)。
- 求和:遍历整个查询区间进行求和,复杂度为O(N)。
使用暴力的方法,修改的复杂度低,求和的时间复杂度高。
平均复杂度,取决于在所有操作中修改和求和所占的比例。
-
如果全部为修改,那么单次操作的平均复杂度为O(1);
-
如果全部为求和,那么单次操作的平均复杂度为O(N)。
-
如果我们假设修改和查询一样多,各占50%,那么平均复杂度仍然为O(N)。
前缀和求解
-
修改:修改第5个位置的数,则前缀和数组需要修改第 5 ~ n 个位置的数。(n 为数组长度)
即:假设修改的位置是 i,则需要修改前缀和数组的第 i 个位置 以及 第 i 个位置之后的所有数。复杂度为O(N)。
-
求和:假设数组前缀和数组是s。求 [l, r]区间的和,只需要计算 s[r] - s[l - 1] 即可 。
即:区间右端点对应的前缀和 减去 区间左端点对应的前缀和。复杂度为O(1)。
在前缀和方式之下,求和的时间开销很低,修改的时间开销很高。
- 如果全部为求和,那么单次操作的平均复杂度为O(1);
- 如果全部为修改,那么单次操作的平均复杂度为O(N)。
- 假设修改和查询一样多,各占50%,那么平均复杂度仍然为O(N)。
有没有折中的办法
操作存在修改和查询两种,时间复杂度取决于最慢操作。因此暴力求解和前缀和求解的时间复杂度都是0(n)。
有没有什么折中方法呢?让插入和求和的时间复杂度不要一个低,一个高。最好两个操作的时间复杂度都趋于相近?
想办法构造一种数据结构,具有以下特征:
- 执行修改操作的时候,时间复杂度小于O(n)。
- 执行求和操作的时候,时间复杂度也小于O(n) 。
有个大神想出了一种特殊的前缀和,使用这种前缀和,当修改元素组某个元素的时候,只会影响 log(n) 个他后面元素对应的前缀和。
一些约定
为了方便表述,我们做如下约定:
-
原数组用
a
来表示,下标从1
开始记。长度为N
的数组的元素是a[1]、a[2]、…、a[N]
。 -
( )
表示开区间,不包括端点。·[ ] ·表示闭区间,包括端点。
新的数据结构-线段树
新的数据结构的核心就在于高效的支持单点修改和求前缀和。
-
我们用数组
t
来存储新的数据结构。 -
t
的长度和a
相同,也是N
。 -
t
的下标也是从1
开始记。 -
t[i] 中记录的是:以a[i]为结尾、长度为lowbit(i)的区间的和,也就是(i-lowbit(i), i]这一区间的和。
为了方便表述,我们用s(i)表示这一区间,即s(i)=s(i-lowbit(i), i]。
例如:t[6] 中记录的是 以a[6] 为结果,长度为 lobit(6) = 2 的这一区间的所有元素和,也就是 a[5] + a[6]
以N=10
为例,下图给出了t
代表的全部10
个区间,并且按照大小的不同给区间分配了层级和颜色,越靠上的区间越大。
t[1]
表示a[1]
自身, = a[1] 。t[1]
覆盖了a[1]
t[2]
表示s[1, 2] = a[1] + a[2]
。t[2]
覆盖了a[1], a[2]
。- .....
t[8]
表示s[1, 8] = a[1] + ····· a[8]
。t[8]
覆盖了a[1], a[2]····a[8]
。
介绍下lowbit的计算:
lowbit(i) = i & -i
其中,&
是按位与。我们知道,计算机在保存一个负整数的时候,采用的是补码的方式,即 -i 的二进制表示等于 i
的二进制表示取反然后再加 1
。
这个 t
数组就是原数组 a
对应的新的数据结构,叫做树状数组
树状数组上的单点修改
在修改a
中的元素时,需要动态维护t
的值。
如果修改了 a[i]
,那么所有覆盖了 a[i]
的 t
值都应该被相应的更新,以保证其数据是最新的。
比如说,如果我们给a[3]
增加10
,那么所有覆盖a[3]
的t
中的元素都要增加10,从上图中可以看出,覆盖了a[3]
的区间包括 t[3]、t[4] 和 t[8]
,所以t[3]、t[4]、t[8]
也应当相应的增加10
。
如何根据被修改的元素下标 i
,找到所有覆盖a[i]
的区间呢?
-
首先我们知道,
t[i]
一定是覆盖a[i]
的,且t[i]
是覆盖a[i]
的所有元素中下标最小。t[i-1]
及它左的下标都小于i
,所以不可能覆盖a[i]
。因此,我们首先更新t[i]
的值。 -
下一个覆盖
a[i]
的区间是什么呢?先给出结论:如果i + lowbit(i) <= N
,那么t[i + lowbit(i)]
就是下一个覆盖 a[i] 的区间。证明还是去看y总视频吧。
经过上边的证明,我们已经知道,在 t[i]
之后下一个覆盖 a[i]
的区间是 t[i+lowbit(i)]
。
那么如何继续找到再下一个覆盖 a[i]
的t
呢?答案是:如果将 i+lowbit(i)
记为 j
,那么在 t[j]
之后,下一个覆盖 a[i]
的区间是 t[j+lowbit(j)]
。
如果我们把这里发现的区间覆盖关系当做是一种父子关系,把父子之间的边加入到线段的图示中的话,那么会得到这样一个图:
再把这张图的形式修改一下,把每个区间的长度取消掉,都用一个单元格来表示,并把t[i]
放在下标i对应的位置,就可以得到树状数组的一般图示了:
至此,我们就完整掌握了找到所有覆盖 a[i]
的t
的方法:
t[i]
一定覆盖a[i]
,且是所有覆盖a[i]
的区间里最靠左的。- 下一个覆盖
a[i]
的区间是t[i+lowbit(i)]
,如果i+lowbit(i) <= N
。 - 令
j = i + lowbit(i)
,那么再下一个覆盖a[i]
的区间是t[j + lowbit(j)]
,如果j + lowbit(j) <= N
。 - 按照2~3的思路一直递推下去,直至超出数组长度N。
找到所有覆盖a[i]
的区间之后,我们修改对应的t
就好了。用c++风格的伪代码描述单点修改的过程如下:
void add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i))
tr[i] += c;
}
由于每执行一次循环,i
的lowbit
值都会至少乘2,所以单点插入的复杂度是O(log N)的。
树状数组上的前缀求和
假设需要计算前缀(0, i]
的和。正整数 i
可以写成若干个不同的2的整数次幂之和
的形式,即 i= 2^p1 + 2^p2 + ... + 2^pk
,设p1<p2<…<pk。
以i=11
为例,11=2^0 + 2^1 + 2^3
,可以展示为:
显然,lowbit(i) = 2^p1
。根据树状数组的定义,t[i]
存储的是(i - 2^p1, i]
这一区间的和。因此,可知 s((0, i]) = s((0, i- 2^p1 ]) + s(( i- 2^p1,i])
=s((0,i - 2^p1 ]) + t[i]
。
i - 2^p1
= 2^p2 + 2^p3 + ... + 2^pk
,所以,lowbit(i - 2^p1 )
= 2^p2
,可知 t[i - 2^p1]
存储的是 (i - 2^p1 - 2^p2,
i - 2^p1]
这一段的和,s((0, i - 2^p1])
= s((0, i - 2^p1 - 2^p2]) + s((i - 2^p1 - 2^p2, i - 2^p1])
= s((0, i - 2^p1 - 2^p2]) + t[i - 2^p1]
。
沿着这一思路继续推导下去,我们最终可以得到:
那么,求前缀和的伪代码就非常好写了:
int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
求和操作的复杂度是O(k)
的,也就是O(log N
的。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200010;
int n;
int a[N];
int tr[N];
int Greater[N], lower[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ )
{
int y = a[i];
Greater[i] = sum(n) - sum(y);
lower[i] = sum(y - 1);
add(y, 1);
}
memset(tr, 0, sizeof tr);
LL res1 = 0, res2 = 0;
for (int i = n; i; i -- )
{
int y = a[i];
res1 += Greater[i] * (LL)(sum(n) - sum(y));
res2 += lower[i] * (LL)(sum(y - 1));
add(y, 1);
}
printf("%lld %lld\n", res1, res2);
return 0;
}
写得好
👍
#👍