Fenwick
树状数组( Fenwick ), 又称二叉索引树( BIT )
针对反复修改区间以及求区间和的这类问题看到一个总结: https://leetcode-cn.com/problems/range-sum-query-mutable/solution/guan-yu-ge-lei-qu-jian-he-wen-ti-ru-he-x-41hv/
- 数组确定, 求区间和: 前缀和
- 多次修改一个数(单点修改), 求区间和: 树状数组
- 多次对区间进行增减, 求单个结果(单点查询): 差分数组
- 多次对区间进行增减, 求区间和: 树状数组, 线段树; 树状数组优先做对区间统一增减
- 多次修改区间为同一个数, 求区间和: 线段树, 树状数组; 线段树优先做对区间统一值
总之线段树是万能方法, 但很显然和高中那个什么万能公式一样, 能不用就别用写着累.
OI wiki上写得应该不是我这种凡人看的, 写作风格颇有一种我是大佬, 你照着我的思路来一遍肯定懂了的意思, 就权当这种写作风格是一种看这类资料的门槛好了…
a是原数组, 图上没画全, 一共有8个. c 是维护的和, 也没画全, 一共也有8个. 这个图是 OI wiki 上的. 实际上这个图所展示的都是数组 c (原数组和), 实际结构中下方多了一行8个原数组.
注意这里数组从1开始, 而不是0. 下列代码举例的时候也应当心. 其实从1开始是一个防止下标越界的 trick, 在线段树中使用到了
预备知识
差分数组
利用前缀和思想, 通过记录差分从而能够快速对原数组一个区间进行修改, 最终能通过差分数组还原为原数组的一种方法
常用于对某个区间同时增减的情况(因此树状数组中也用到了这个)
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
// 构造差分数组
vector<int> constructDiff(vector<int> &nums)
{
vector<int> diff(nums.size(), 0);
diff[0] = nums[0];
for(int idx = 1; idx < nums.size(); ++idx)
diff[idx] = nums[idx] - nums[idx - 1];
return diff;
}/
// 还原为原数组
vector<int> retOriginArray(vector<int> &diff)
{
vector<int> res(diff.size());
res[0] = diff[0];
for(int idx = 1; idx < diff.size(); ++idx)
res[idx] = res[idx - 1] + diff[idx];
return res;
}
// 区间 [left, right] 的值都增加 val
void add(int left, int right, int val, vector<int> &diff)
{
diff[left] += val;
if(right + 1 < diff.size())
diff[right + 1] -= val;
}
lowbit(最低位的1对应的值)
一个借助位运算快速找到一个数二进制表示最低位1对应的值
1
2
3
4
5
6
7
// e.g. lowbit(0b10110000) -> 10000, 即16
// e.g. lowbit(0b11100010) -> 10, 即2
int lowbit(int x)
{
// -x 的二进制为 x 取反+1
return x & -x;
}
能用到的地方有点多, 在树状数组中有, 如单点修改(改一个数组里的一个数)
1
2
3
4
5
6
7
8
9
10
11
12
// 自底向上的更新
void add(int idx, int val)
{
// length 是对应的原数组长度, 防止越界
while(idx <= length)
{
// 区间和增加 val
array[idx] += val;
// 向上扩散, 逐步更改更大的区间和
idx += lowbit(idx);
}
}
如前缀求和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// [1, right] 求和
/*
一份可能需要的更详细解释
首先 array[right] 代表 [mid1, right] 这个区间和( mid1 多大不重要), mid1 = 0b...1...0...1
下一步向左扩散, 一定能找到 [mid2, mid1 - 1] 这个区间和, mid2 = 0b...1...0...1
*/
int sum(int right)
{
int res = 0;
while(right >= 1)
{
res += array[right];
// 向左扩散, 以找到覆盖之前序列的区间和
right -= lowbit(right);
}
return res;
}
总的来说还是一个确定数据遍历方向的方法, 不过为什么这样更新可以得到最终结果?
总体思想还是分治, 能将一个大区间和转换为多个小区间和. 有点类似快速版二分搜索, 二分搜索每次都将区间二进制右移一位, 而此处每次都右移最低零个数那么多位
原生 Fenwick 模板
根据上述信息应该就能写出树状数组的模板了
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
#include <vector>
class Fenwick
{
private:
std::vector<int> nums;
std::vector<int> oriNums;
int lowbit(int x)
{
return x & -x;
}
int prefix(int pos)
{
int res = 0;
while (pos > 0)
{
res += nums[pos];
pos -= lowbit(pos);
}
return res;
}
void add(int x, int pos)
{
while (pos < nums.size())
{
nums[pos] += x;
pos += lowbit(pos);
}
}
public:
int intervalSum(int leftPos, int rightPos)
{
return this->prefix(rightPos) - this->prefix(leftPos - 1);
}
// 从零开始的原数组索引
void update(int val, int idx)
{
this->add(val - oriNums[idx], idx + 1);
this->oriNums[idx] = val;
}
// 原始区间修改
void intervalUpdate(int leftIdx, int rightIdx, int val)
{
for(int idx = leftIdx; idx <= rightIdx; ++idx)
this->update(val, idx);
}
Fenwick(std::vector<int> &initNums) : oriNums(initNums)
{
this->nums.resize(initNums.size() + 1);
for (int idx = 1; idx <= initNums.size(); ++idx)
this->add(initNums[idx - 1], idx);
}
~Fenwick() {}
};
双前缀优化 Fenwick
本小节主要参考文献为 OI WIKI
很显然, 原生版本的区间修改时间复杂度是 $O(M\log{N})$, 需要对区间内的每个点逐个调用单点修改, 一共调用区间长度 $M$ 那么多次
1
2
3
4
5
6
// 原始区间修改
void intervalUpdate(int leftIdx, int rightIdx, int val)
{
for(int idx = leftIdx; idx <= rightIdx; ++idx)
this->update(val, idx);
}
而使用差分数组, 能够只调用 $O(1)$ 次修改, 完成一整个区间的修改, 因此我们试图构造差分数组进行优化.
为了进行优化, 我们需要进行一些”简单的”数学推导, 针对所求的前缀和 $\Sigma_{i=1}^{r}a_i$, 若我们已经维护了数组 $a$ 的差分数组, 即 $a_i = \Sigma_{j=1}^{i}b_j$, 有以下:
\[\Sigma_{i=1}^{r}a_i = \Sigma_{i=1}^{r}\Sigma_{j=1}^{i}b_j \\ = \Sigma_{i=1}^{r}b_i\times(r - i + 1) \\ = \Sigma_{i=1}^{r}b_i\times(r + 1) - \Sigma_{i=1}^{r}b_i\times i\]上述推导, 使得我们能够将一个原数组前缀和问题, 转换为两个差分数组*前缀和问题, 从而通过两个维护差分数组的树状数组, 来快速实现区间修改
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
class doublePrefixFenwick
{
private:
std::vector<int> diffNums;
std::vector<int> diffPosWeightedNums;
int length;
int lowbit(int x)
{
return x & -x;
}
int prefix(int pos, bool isWeighted)
{
std::vector<int> &nums = isWeighted ? diffPosWeightedNums : diffNums;
int res = 0;
while (pos > 0)
{
res += nums[pos];
pos -= lowbit(pos);
}
return res;
}
int add(int x, int pos)
{
int weightX = pos * x;
while (pos < length)
{
diffNums[pos] += x, diffPosWeightedNums[pos] += weightX;
pos += lowbit(pos);
}
}
public:
// 有差分数组, 就能快速进行区间统一加了
void intervalAdd(int leftPos, int rightPos, int val)
{
this->add(leftPos, val);
this->add(rightPos + 1, -val);
}
// 利用前面推导的数学公式, 使用两个前缀和的差求原始前缀和
int intervalSum(int leftPos, int rightPos)
{
return ((rightPos + 1) * this->prefix(rightPos, false) - leftPos * this->prefix(leftPos - 1, false)) - ((rightPos + 1) * this->prefix(rightPos, true) - leftPos * this->prefix(leftPos - 1, true));
}
doublePrefixFenwick(std::vector<int> &oriNums) : length(oriNums.size())
{
// 构建原始差分数组
this->diffNums.resize(length + 1, 0);
this->diffPosWeightedNums.resize(length + 1, 0);
std::vector<int> initDiffNums(length + 1, 0);
diffNums[1] = oriNums[0];
for (int idx = 2; idx <= length; ++idx)
initDiffNums[idx] = oriNums[idx - 1] - oriNums[idx - 2];
// 构建差分数组的树状数组
for (int idx = 1; idx <= length; ++idx)
this->add(initDiffNums[idx - 1], idx);
}
~doublePrefixFenwick() {}
};
$O(N)$ 建树技巧
首先我们观察上述模板的构造函数
1
2
3
4
5
6
7
8
doublePrefixFenwick(std::vector<int> &oriNums) : length(oriNums.size())
{
// 构建原始差分数组
...
// 构建差分数组的树状数组
for (int idx = 1; idx <= length; ++idx)
this->add(initDiffNums[idx - 1], idx);
}
很显然, 构造树状数组时的时间复杂度是 $O(N\log{N})$, 是由于每次调用 add, 我们都自底向上全部更新了结点信息, 而在这里, 我们可以借助线段树中的懒人标记思想, 只更新本结点与直连的父结点, 至于更远的祖宗结点, 等到我们下一次更新时再改变
1
2
3
4
5
6
7
8
9
10
11
12
13
doublePrefixFenwick(std::vector<int> &oriNums) : length(oriNums.size())
{
// 构建原始差分数组
...
// 构建差分数组的树状数组
for (int idx = 1; idx <= length; ++idx)
{
diffNums[idx] += initDiffNums[idx], diffPosWeightedNums[idx] += idx * initDiffNums[idx];
int nextPos = idx + lowbit(idx);
if (nextPos <= length)
diffNums[nextPos] += diffNums[idx], diffPosWeightedNums[nextPos] += diffPosWeightedNums[idx];
}
}
总结
总而言之, 树状数组可以实现$O(\log{N})$修改区间(单点也一样)以及求区间和; 与原始数组都是$O(N)$和前缀和, 即修改$O(N)$, 求和$O(1)$对比, 平衡了修改以及查询的时间. 当然后续还有很多 trick 以及拓展没有涉及到, 但是以我目前的认知水平, 认为到这里就差不多了, 以下附上整个模板代码
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
105
106
107
108
109
110
111
112
113
#include <vector>
class Fenwick
{
private:
std::vector<int> nums;
std::vector<int> oriNums;
int lowbit(int x)
{
return x & -x;
}
int prefix(int idx)
{
int res = 0;
while (idx > 0)
{
res += nums[idx];
idx -= lowbit(idx);
}
return res;
}
void add(int x, int idx)
{
while (idx < nums.size())
{
nums[idx] += x;
idx += lowbit(idx);
}
}
public:
int intervalSum(int left, int right)
{
return this->prefix(right) - this->prefix(left - 1);
}
// 从零开始的原数组索引
void update(int val, int idx)
{
this->add(val - oriNums[idx], idx + 1);
this->oriNums[idx] = val;
}
Fenwick(std::vector<int> &initNums) : oriNums(initNums)
{
this->nums.resize(initNums.size() + 1);
for (int idx = 1; idx <= initNums.size(); ++idx)
this->add(initNums[idx - 1], idx);
}
~Fenwick() {}
};
class doublePrefixFenwick
{
private:
std::vector<int> diffNums;
std::vector<int> diffPosWeightedNums;
int length;
int lowbit(int x)
{
return x & -x;
}
int prefix(int pos, bool isWeighted)
{
std::vector<int> &nums = isWeighted ? diffPosWeightedNums : diffNums;
int res = 0;
while (pos > 0)
{
res += nums[pos];
pos -= lowbit(pos);
}
return res;
}
int add(int x, int pos)
{
int weightX = pos * x;
while (pos < length)
{
diffNums[pos] += x, diffPosWeightedNums[pos] += weightX;
pos += lowbit(pos);
}
}
public:
// 有差分数组, 就能快速进行区间统一加了
void intervalAdd(int leftPos, int rightPos, int val)
{
this->add(leftPos, val);
this->add(rightPos + 1, -val);
}
// 利用前面推导的数学公式, 使用两个前缀和的差求原始前缀和
int intervalSum(int leftPos, int rightPos)
{
return ((rightPos + 1) * this->prefix(rightPos, false) - leftPos * this->prefix(leftPos - 1, false)) - ((rightPos + 1) * this->prefix(rightPos, true) - leftPos * this->prefix(leftPos - 1, true));
}
doublePrefixFenwick(std::vector<int> &oriNums) : length(oriNums.size())
{
// 构建原始差分数组
this->diffNums.resize(length + 1, 0);
this->diffPosWeightedNums.resize(length + 1, 0);
std::vector<int> initDiffNums(length + 1, 0);
diffNums[1] = oriNums[0];
for (int idx = 2; idx <= length; ++idx)
initDiffNums[idx] = oriNums[idx - 1] - oriNums[idx - 2];
// 构建差分数组的树状数组
for (int idx = 1; idx <= length; ++idx)
{
diffNums[idx] += initDiffNums[idx], diffPosWeightedNums[idx] += idx * initDiffNums[idx];
int nextPos = idx + lowbit(idx);
if (nextPos <= length)
diffNums[nextPos] += diffNums[idx], diffPosWeightedNums[nextPos] += diffPosWeightedNums[idx];
}
}
~doublePrefixFenwick() {}
};
This post is licensed under CC BY 4.0 by the author.