前置知识
学习树状数组之前,最好先了解下面这些内容:
前缀和与差分;
二进制与位运算;
树状数组的代码非常短,核心操作甚至只有几行。不过代码短不代表它很好理解,特别是第一次看到x += x & -x 和x -= x & -x 时,很容易产生一种“它为什么能这样跳”的疑问。
所以这篇文章不会只给出一个模板,而是从树状数组到底解决了什么问题开始,把lowbit 、节点所维护的区间、修改和查询的方向一步一步说明白,然后再继续学习差分树状数组、双树状数组、离散化、逆序对和动态第k k k 小。
为什么需要树状数组?
先考虑一个很普通的问题:给定一个长度为n n n 的数组,需要进行下面两种操作。
将第x x x 个数增加k k k ;
查询区间[ l , r ] [l,r] [ l , r ] 的元素和。
如果直接使用普通数组,那么修改一次只需要O ( 1 ) O(1) O ( 1 ) ,但是查询区间和需要从l l l 一直加到r r r ,复杂度为O ( n ) O(n) O ( n ) 。
如果使用前缀和数组:
s i = ∑ j = 1 i a j s_i=\sum_{j=1}^{i}a_j
s i = j = 1 ∑ i a j
查询区间和确实只需要:
∑ i = l r a i = s r − s l − 1 \sum_{i=l}^{r}a_i=s_r-s_{l-1}
i = l ∑ r a i = s r − s l − 1
复杂度降到了O ( 1 ) O(1) O ( 1 ) 。但是修改a x a_x a x 以后,s x , s x + 1 , … , s n s_x,s_{x+1},\dots,s_n s x , s x + 1 , … , s n 都要跟着改变,一次修改又变成了O ( n ) O(n) O ( n ) 。
方法
单点修改
区间求和
普通数组
O ( 1 ) O(1) O ( 1 )
O ( n ) O(n) O ( n )
前缀和
O ( n ) O(n) O ( n )
O ( 1 ) O(1) O ( 1 )
树状数组
O ( log n ) O(\log n) O ( log n )
O ( log n ) O(\log n) O ( log n )
普通数组把时间全花在查询上,前缀和把时间全花在修改上。树状数组选择了一个折中的办法:它不保存所有前缀和,而是保存许多段长度不同的区间和,因此修改和查询都可以在O ( log n ) O(\log n) O ( log n ) 内完成。
lowbit
树状数组最核心的函数叫lowbit :
1 int lowbit (int x) { return x & -x; }
lowbit(x) 函数 表示x x x 的二进制表示中,最低位的1 1 1 以及它后面的所有0 0 0 所组成的数,也就是x x x 能够整除的最大二的幂。
例如:
x x x
二进制
lowbit(x)
十进制结果
6 6 6
0110 0110 0110
0010 0010 0010
2 2 2
8 8 8
1000 1000 1000
1000 1000 1000
8 8 8
10 10 10
1010 1010 1010
0010 0010 0010
2 2 2
12 12 12
1100 1100 1100
0100 0100 0100
4 4 4
为什么x & -x 能够取出最低位的1 1 1 ?
计算机使用补码表示负数,− x -x − x 可以看作对x x x 按位取反后再加1 1 1 。这个过程中,x x x 最低位的1 1 1 右边全部都是0 0 0 ,取反加一以后,这一位及其右边会与原数保持可以相交的形式;而更高位全部无法同时为1 1 1 。两者按位与以后,最后只剩下最低位的1 1 1 。
以x = 12 x=12 x = 12 为例:
1 2 3 x = 0000 1100 -x = 1111 0100 & = 0000 0100
所以lowbit(12)=4 。
如果现在感觉补码这一部分稍微有点绕,也不影响后面使用。先记住:
lowbit(x) 的结果 就是x x x 在树状数组中所管理区间的长度。
树状数组中每个位置存了什么?
设原数组为a a a ,树状数组为t r e e tree t r ee 。tree[x] 节点 并不是简单地保存a x a_x a x ,它保存的是下面这段区间的和:
t r e e [ x ] = ∑ i = x − lowbit ( x ) + 1 x a i tree[x]=\sum_{i=x-\operatorname{lowbit}(x)+1}^{x}a_i
t r ee [ x ] = i = x − lowbit ( x ) + 1 ∑ x a i
换句话说,tree[x] 节点 维护的区间为:
[ x − lowbit ( x ) + 1 , x ] [x-\operatorname{lowbit}(x)+1,x]
[ x − lowbit ( x ) + 1 , x ]
当n = 8 n=8 n = 8 时,各节点管理的范围如下:
节点
lowbit
管理区间
保存的内容
tree[1]
1 1 1
[ 1 , 1 ] [1,1] [ 1 , 1 ]
a 1 a_1 a 1
tree[2]
2 2 2
[ 1 , 2 ] [1,2] [ 1 , 2 ]
a 1 + a 2 a_1+a_2 a 1 + a 2
tree[3]
1 1 1
[ 3 , 3 ] [3,3] [ 3 , 3 ]
a 3 a_3 a 3
tree[4]
4 4 4
[ 1 , 4 ] [1,4] [ 1 , 4 ]
a 1 + a 2 + a 3 + a 4 a_1+a_2+a_3+a_4 a 1 + a 2 + a 3 + a 4
tree[5]
1 1 1
[ 5 , 5 ] [5,5] [ 5 , 5 ]
a 5 a_5 a 5
tree[6]
2 2 2
[ 5 , 6 ] [5,6] [ 5 , 6 ]
a 5 + a 6 a_5+a_6 a 5 + a 6
tree[7]
1 1 1
[ 7 , 7 ] [7,7] [ 7 , 7 ]
a 7 a_7 a 7
tree[8]
8 8 8
[ 1 , 8 ] [1,8] [ 1 , 8 ]
a 1 + ⋯ + a 8 a_1+\cdots+a_8 a 1 + ⋯ + a 8
虽然它叫“树状数组”,代码中却不需要真的建立一棵树。父子关系和每个节点管理的范围都已经隐藏在下标的二进制结构中,我们只需要一个数组就能存下整棵树。
图片占位 2:长度为 8 的树状数组节点管辖区间图
单点修改
假设我们要让a 3 a_3 a 3 增加k k k 。
首先,tree[3] 节点 维护[ 3 , 3 ] [3,3] [ 3 , 3 ] ,其中包含a 3 a_3 a 3 ,所以需要修改这个节点。
接着,tree[4] 节点 维护[ 1 , 4 ] [1,4] [ 1 , 4 ] ,其中也包含a 3 a_3 a 3 ,所以同样需要修改。
最后,tree[8] 节点 维护[ 1 , 8 ] [1,8] [ 1 , 8 ] ,仍然包含a 3 a_3 a 3 ,所以也需要修改。
整个修改路径为:
3 → 4 → 8 3\rightarrow4\rightarrow8
3 → 4 → 8
从当前节点跳到下一个需要修改的节点,只需要:
所以单点增加的代码如下:
1 void add (int x, i64 k) { for (; x <= n; x += lowbit (x)) tree[x] += k; }
每次跳转都会让下标的某个二进制位发生变化,所管理的区间越来越大。最多跳O ( log n ) O(\log n) O ( log n ) 次,就会超过n n n ,因此单点修改的时间复杂度为O ( log n ) O(\log n) O ( log n ) 。
图片占位 3:修改位置 3 时的向上更新路径
前缀和查询
接着考虑如何查询a 1 + a 2 + ⋯ + a 7 a_1+a_2+\cdots+a_7 a 1 + a 2 + ⋯ + a 7 。
tree[7] 节点 管理[ 7 , 7 ] [7,7] [ 7 , 7 ] ,先把它加入答案。剩下需要查询[ 1 , 6 ] [1,6] [ 1 , 6 ] 。
tree[6] 节点 管理[ 5 , 6 ] [5,6] [ 5 , 6 ] ,再把它加入答案。剩下需要查询[ 1 , 4 ] [1,4] [ 1 , 4 ] 。
tree[4] 节点 刚好管理[ 1 , 4 ] [1,4] [ 1 , 4 ] ,加入答案以后查询结束。
于是:
∑ i = 1 7 a i = t r e e [ 7 ] + t r e e [ 6 ] + t r e e [ 4 ] \sum_{i=1}^{7}a_i=tree[7]+tree[6]+tree[4]
i = 1 ∑ 7 a i = t r ee [ 7 ] + t r ee [ 6 ] + t r ee [ 4 ]
查询路径为:
7 → 6 → 4 → 0 7\rightarrow6\rightarrow4\rightarrow0
7 → 6 → 4 → 0
从当前右端点删去已经统计的区间,只需要:
完整代码如下:
1 i64 prefix (int x) { i64 ans = 0 ; for (; x; x -= lowbit (x)) ans += tree[x]; return ans; }
同样,前缀和查询的时间复杂度为O ( log n ) O(\log n) O ( log n ) 。
得到了前缀和以后,区间[ l , r ] [l,r] [ l , r ] 的和就是:
1 i64 query (int l, int r) { return prefix (r) - prefix (l - 1 ); }
图片占位 4:查询前缀 7 时的区间拆分图
基础模板
把上面的内容合在一起,就是最基础的树状数组模板。代码头仍然保留固定宽度整数别名,不过普通下标、循环变量和操作编号直接使用int ;只有可能溢出的元素和、修改量与答案才使用i64 。
1 2 3 4 5 6 7 8 9 10 using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;constexpr int MAXN = 5e5 + 7 ;int n;i64 tree[MAXN]; int lowbit (int x) { return x & -x; }void add (int x, i64 k) { for (; x <= n; x += lowbit (x)) tree[x] += k; }i64 prefix (int x) { i64 ans = 0 ; for (; x; x -= lowbit (x)) ans += tree[x]; return ans; }i64 query (int l, int r) { return prefix (r) - prefix (l - 1 ); }
这里需要特别注意:树状数组的下标必须从1 1 1 开始。
如果对下标0 0 0 执行修改,那么lowbit(0)=0 ,执行x += lowbit(x) 这一步 以后,x x x 仍然等于0 0 0 ,程序会直接陷入死循环。这也是树状数组最常见、同时也最好排查的错误之一。
例题与典型应用
只看模板很容易产生“好像会了”的错觉。下面把五道题放在同一个章节里,从普通树状数组一路走到差分、双树状数组、逆序对和第k k k 小,正好串起最常见的几种用法。
例题一:AtCoder Practice2 B - Fenwick Tree
题目链接:AtCoder Practice2 B - Fenwick Tree
题目要求维护一个长度为n n n 的数组,支持下面两种操作:
0 p x :令a p ← a p + x a_p\gets a_p+x a p ← a p + x ;
1 l r :查询∑ i = l r − 1 a i \sum_{i=l}^{r-1}a_i ∑ i = l r − 1 a i 。
这就是标准的“单点增加、区间求和”。唯一需要注意的是,题目的数组下标从0 0 0 开始,而我们写的树状数组从1 1 1 开始。
因此原数组的a p a_p a p 应当放进树状数组的p + 1 p+1 p + 1 位置。
题目查询的是左闭右开区间[ l , r ) [l,r) [ l , r ) 。其中包含原数组的前r r r 个数,减去前l l l 个数,所以答案为:
而不是常见的prefix(r)-prefix(l-1) 这种写法 。这里并不是前缀和公式变了,而是题目使用了从0 0 0 开始的下标和左闭右开区间。
点击展开完整代码 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 <bits/stdc++.h> using namespace std;using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;constexpr int MAXN = 500005 ;int n, q;i64 tree[MAXN]; int lowbit (int x) { return x & -x; }void add (int x, i64 k) { for (; x <= n; x += lowbit (x)) tree[x] += k; }i64 prefix (int x) { i64 ans = 0 ; for (; x; x -= lowbit (x)) ans += tree[x]; return ans; }int32_t main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); cin >> n >> q; for (int i = 0 ; i < n; i++) { i64 x; cin >> x; add (i + 1 , x); } while (q--) { int op; cin >> op; if (op == 0 ) { int p; i64 x; cin >> p >> x; add (p + 1 , x); } else { int l, r; cin >> l >> r; cout << prefix (r) - prefix (l) << '\n' ; } } return 0 ; }
O ( n ) O(n) O ( n ) 建树
上面的代码通过n n n 次add 完成初始化,复杂度为O ( n log n ) O(n\log n) O ( n log n ) 。树状数组也可以在线性时间内建树。
先把a i a_i a i 加入tree[i] 节点 ,再把这个节点的值整体交给它的直接父节点:
1 2 3 4 5 for (int i = 1 ; i <= n; i++) { tree[i] += a[i]; int fa = i + lowbit (i); if (fa <= n) tree[fa] += tree[i]; }
因为从左到右枚举到i i i 时,tree[i] 节点 所管理区间内的值已经全部收集完成,可以直接把整段区间和加入父节点。
不过比赛中大多数基础题的O ( n log n ) O(n\log n) O ( n log n ) 初始化已经足够,而且不容易写错。线性建树知道即可,不必为了少一个对数强行增加出错的机会。
例题二:洛谷 P3368 树状数组 2
题目链接:洛谷 P3368 树状数组 2
题目需要支持:
将区间[ l , r ] [l,r] [ l , r ] 中的每个数增加k k k ;
查询第x x x 个数现在的值。
基础树状数组支持的是单点增加,而这里需要区间增加。看起来操作正好反过来了,但是加入差分数组以后,问题就会重新变成树状数组熟悉的样子。
差分数组
定义:
d i = a i − a i − 1 d_i=a_i-a_{i-1}
d i = a i − a i − 1
其中规定a 0 = 0 a_0=0 a 0 = 0 ,那么:
a x = d 1 + d 2 + ⋯ + d x a_x=d_1+d_2+\cdots+d_x
a x = d 1 + d 2 + ⋯ + d x
也就是说,原数组中的单点值,正好是差分数组的前缀和。
如果要让区间[ l , r ] [l,r] [ l , r ] 全部增加k k k ,区间内部相邻两个数都增加了k k k ,它们之间的差不会改变。真正发生变化的只有左右两个端点:
d l ← d l + k d_l\gets d_l+k
d l ← d l + k
d r + 1 ← d r + 1 − k d_{r+1}\gets d_{r+1}-k
d r + 1 ← d r + 1 − k
于是一次区间修改被转换成了两次单点修改。查询a x a_x a x 时,只需要查询差分数组的前缀和。
图片占位 5:差分数组完成区间增加的端点变化图
初始化
读入原数组时,可以直接计算相邻两项的差,并把差分值加入树状数组:
1 2 3 4 5 6 7 i64 lst = 0 ; for (int i = 1 ; i <= n; i++) { i64 x; cin >> x; add (i, x - lst); lst = x; }
区间修改与单点查询
1 2 void rangeAdd (int l, int r, i64 k) { add (l, k); add (r + 1 , -k); }i64 point (int x) { return prefix (x); }
当r = n r=n r = n 时,add(r+1,-k) 这次修改 会从n + 1 n+1 n + 1 开始。因为add 函数 中的条件是x<=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 35 36 37 38 #include <bits/stdc++.h> using namespace std;using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;constexpr int MAXN = 500005 ;int n, m;i64 tree[MAXN]; int lowbit (int x) { return x & -x; }void add (int x, i64 k) { for (; x <= n; x += lowbit (x)) tree[x] += k; }i64 prefix (int x) { i64 ans = 0 ; for (; x; x -= lowbit (x)) ans += tree[x]; return ans; }int32_t main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); cin >> n >> m; i64 lst = 0 ; for (int i = 1 ; i <= n; i++) { i64 x; cin >> x; add (i, x - lst); lst = x; } while (m--) { int op; cin >> op; if (op == 1 ) { int l, r; i64 k; cin >> l >> r >> k; add (l, k); add (r + 1 , -k); } else { int x; cin >> x; cout << prefix (x) << '\n' ; } } return 0 ; }
例题三:洛谷 P3372 线段树 1
题目链接:洛谷 P3372 线段树 1
题目的名字虽然叫“线段树 1”,但是它同样可以使用树状数组完成。需要支持:
将区间[ l , r ] [l,r] [ l , r ] 中的每个数增加k k k ;
查询区间[ l , r ] [l,r] [ l , r ] 的元素和。
P3368通过差分数组实现了区间修改,但是只能查询一个位置。现在如果还想求区间和,就需要继续推导原数组的前缀和。
仍然令:
d i = a i − a i − 1 d_i=a_i-a_{i-1}
d i = a i − a i − 1
那么原数组前x x x 项的和为:
S x = a 1 + a 2 + ⋯ + a x = d 1 + ( d 1 + d 2 ) + ⋯ + ( d 1 + d 2 + ⋯ + d x ) \begin{aligned}
S_x
&=a_1+a_2+\cdots+a_x\\
&=d_1+(d_1+d_2)+\cdots+(d_1+d_2+\cdots+d_x)
\end{aligned}
S x = a 1 + a 2 + ⋯ + a x = d 1 + ( d 1 + d 2 ) + ⋯ + ( d 1 + d 2 + ⋯ + d x )
观察每个d i d_i d i 出现的次数:d 1 d_1 d 1 出现x x x 次,d 2 d_2 d 2 出现x − 1 x-1 x − 1 次,d x d_x d x 只出现一次。因此:
S x = x d 1 + ( x − 1 ) d 2 + ⋯ + d x S_x=xd_1+(x-1)d_2+\cdots+d_x
S x = x d 1 + ( x − 1 ) d 2 + ⋯ + d x
把它整理一下:
S x = ∑ i = 1 x ( x − i + 1 ) d i = ( x + 1 ) ∑ i = 1 x d i − ∑ i = 1 x i ⋅ d i \begin{aligned}
S_x
&=\sum_{i=1}^{x}(x-i+1)d_i\\
&=(x+1)\sum_{i=1}^{x}d_i-\sum_{i=1}^{x}i\cdot d_i
\end{aligned}
S x = i = 1 ∑ x ( x − i + 1 ) d i = ( x + 1 ) i = 1 ∑ x d i − i = 1 ∑ x i ⋅ d i
这里出现了两个前缀和:
∑ d i \sum d_i ∑ d i ;
∑ i ⋅ d i \sum i\cdot d_i ∑ i ⋅ d i 。
所以我们建立两棵树状数组:
tree1 维护d i d_i d i ;
tree2 维护i ⋅ d i i\cdot d_i i ⋅ d i 。
于是原数组的前缀和可以写成:
1 i64 sum (int x) { return (x + 1 ) * prefix (tree1, x) - prefix (tree2, x); }
图片占位 6:双树状数组前缀和公式推导图
如何修改两棵树状数组?
当差分数组的d x d_x d x 增加k k k 时:
tree1[x] 的值 对应增加k k k ;
tree2[x] 的值 对应增加x ⋅ k x\cdot k x ⋅ k 。
1 void modify (int x, i64 k) { add (tree1, x, k); add (tree2, x, k * x); }
区间[ l , r ] [l,r] [ l , r ] 增加k k k ,仍然只修改差分数组的两个端点:
1 void rangeAdd (int l, int r, i64 k) { modify (l, k); modify (r + 1 , -k); }
最终区间和为:
sum ( l , r ) = S r − S l − 1 \operatorname{sum}(l,r)=S_r-S_{l-1}
sum ( l , r ) = S r − S l − 1
点击展开完整代码 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 <bits/stdc++.h> using namespace std;using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;constexpr int MAXN = 100005 ;int n, m;i64 tree1[MAXN], tree2[MAXN]; int lowbit (int x) { return x & -x; }void add (i64 tree[], int x, i64 k) { for (; x <= n; x += lowbit (x)) tree[x] += k; }i64 prefix (i64 tree[], int x) { i64 ans = 0 ; for (; x; x -= lowbit (x)) ans += tree[x]; return ans; }void modify (int x, i64 k) { add (tree1, x, k); add (tree2, x, k * x); }void rangeAdd (int l, int r, i64 k) { modify (l, k); modify (r + 1 , -k); }i64 sum (int x) { return (x + 1 ) * prefix (tree1, x) - prefix (tree2, x); }i64 query (int l, int r) { return sum (r) - sum (l - 1 ); }int32_t main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); cin >> n >> m; i64 lst = 0 ; for (int i = 1 ; i <= n; i++) { i64 x; cin >> x; modify (i, x - lst); lst = x; } while (m--) { int op, l, r; cin >> op >> l >> r; if (op == 1 ) { i64 k; cin >> k; rangeAdd (l, r, k); } else cout << query (l, r) << '\n' ; } return 0 ; }
到这里,树状数组常见的三组操作已经全部出现:
修改方式
查询方式
实现方法
单点修改
区间查询
普通树状数组
区间修改
单点查询
维护差分数组
区间修改
区间查询
维护d i d_i d i 和i ⋅ d i i\cdot d_i i ⋅ d i 两棵树状数组
例题四:洛谷 P1908 逆序对
题目链接:洛谷 P1908 逆序对
对于一个序列,如果i < j i<j i < j 并且a i > a j a_i>a_j a i > a j ,那么( i , j ) (i,j) ( i , j ) 就是一个逆序对。题目要求统计整个序列中逆序对的数量。
最直接的做法是枚举i , j i,j i , j ,复杂度为O ( n 2 ) O(n^2) O ( n 2 ) 。但是n n n 最大为5 × 10 5 5\times10^5 5 × 1 0 5 ,显然无法通过。
换一个角度统计
从左向右枚举a i a_i a i 。当枚举到当前位置时,前面的i − 1 i-1 i − 1 个数都已经加入树状数组。
记c i c_i c i 为前面小于等于a i a_i a i 的元素个数。前面一共有i − 1 i-1 i − 1 个数,因此当前位置新产生的逆序对数量为:
inv i = ( i − 1 ) − c i \operatorname{inv}_i=(i-1)-c_i
inv i = ( i − 1 ) − c i
这些大于a i a_i a i 的数都位于a i a_i a i 左侧,因此它们分别和当前a i a_i a i 组成一个逆序对。
这里树状数组维护的不再是“原数组每个位置的值”,而是:
每一种数值已经出现了多少次。
当树状数组维护出现次数时,查询某个值对应位置的前缀和,就表示“小于等于这个值的数字出现了多少个”。这种把数值当成下标、维护出现次数的树状数组,通常也叫权值树状数组 。
离散化
题目中的a i a_i a i 最大可以达到10 9 10^9 1 0 9 ,我们不可能开一个大小为10 9 10^9 1 0 9 的树状数组。
注意到这里并不关心数值之间具体相差多少,只关心它们的大小关系。因此可以排序去重,将每个数替换成它在所有不同数值中的排名,这个过程叫离散化。
例如:
1 2 3 原数组:5 2 6 2 1 去重并排序:1 2 5 6 离散化后:3 2 4 2 1
1 , 2 , 5 , 6 1,2,5,6 1 , 2 , 5 , 6 之间原本的距离消失了,但是它们的大小关系完全没有改变,所以逆序对数量也不会改变。
对于每个a i a_i a i ,可以使用lower_bound 找到排名:
1 int rank = lower_bound (b.begin (), b.end (), a[i]) - b.begin () + 1 ;
这里最后加1 1 1 ,仍然是因为树状数组不能使用下标0 0 0 。
重复数字的处理
逆序对的条件是严格大于,而不是大于等于。所以前面与a i a_i a i 相等的数不能计入答案。
prefix(rank) 的结果 是小于等于a i a_i a i 的数量,用已经处理的总数i − 1 i-1 i − 1 减去它,剩下的才全部严格大于a i a_i a i :
1 2 ans += (i - 1 ) - prefix (rank); add (rank, 1 );
一定要先统计答案,再把当前数加入树状数组。否则当前a i a_i a i 也会被算进“前面已经出现的数”中。
图片占位 7:离散化后扫描并统计逆序对的过程图
点击展开完整代码 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 #include <bits/stdc++.h> using namespace std;using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;constexpr int MAXN = 500005 ;int n, tree[MAXN];int lowbit (int x) { return x & -x; }void add (int x, int k) { for (; x <= n; x += lowbit (x)) tree[x] += k; }int prefix (int x) { int ans = 0 ; for (; x; x -= lowbit (x)) ans += tree[x]; return ans; }int32_t main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); cin >> n; vector<i64> a (n + 1 ) , b ; b.reserve (n); for (int i = 1 ; i <= n; i++) { cin >> a[i]; b.push_back (a[i]); } sort (b.begin (), b.end ()); b.erase (unique (b.begin (), b.end ()), b.end ()); i64 ans = 0 ; for (int i = 1 ; i <= n; i++) { int rank = lower_bound (b.begin (), b.end (), a[i]) - b.begin () + 1 ; ans += i - 1 - prefix (rank); add (rank, 1 ); } cout << ans << '\n' ; return 0 ; }
逆序对也可以从右向左统计。此时树状数组中存放的是当前位置右边的数,当前a i a_i a i 产生的逆序对数量就是右边严格小于它的数量:
1 2 ans += prefix (rank - 1 ); add (rank, 1 );
两种方向的本质完全相同。遇到类似计数题时,可以根据“不等号方向”和“哪一侧更方便统计”选择扫描方向。
例题五:Codeforces 1354D Multiset
题目链接:Codeforces 1354D - Multiset
题目需要维护一个可重复集合,操作分为两种:
插入数字x x x ;
删除集合中第k k k 小的数字。
所有数字都在[ 1 , n ] [1,n] [ 1 , n ] 范围内。可以让tree[x] 的值 表示数字x x x 的出现次数,插入x x x 就是:
假设集合为:
那么频率前缀和的意义如下:
x x x
prefix ( x ) \operatorname{prefix}(x) prefix ( x )
意义
1 1 1
2 2 2
有2 2 2 个数小于等于1 1 1
2 2 2
3 3 3
有3 3 3 个数小于等于2 2 2
4 4 4
5 5 5
有5 5 5 个数小于等于4 4 4
第k k k 小的数,就是满足下面条件的最小x x x :
prefix ( x ) ≥ k \operatorname{prefix}(x)\ge k
prefix ( x ) ≥ k
因为频率前缀和一定单调不减,可以对x x x 进行二分。每次二分又需要一次O ( log n ) O(\log n) O ( log n ) 的树状数组查询,总复杂度为O ( log 2 n ) O(\log^2 n) O ( log 2 n ) 。
普通数据下这样已经能用,但是这道题的n , q n,q n , q 都可能达到10 6 10^6 1 0 6 ,时间限制和内存限制也比较紧。我们可以直接在树状数组内部进行倍增,将寻找第k k k 小优化到O ( log n ) O(\log n) O ( log n ) 。
树状数组上倍增
我们从不超过n n n 的最大二的幂开始尝试,逐步缩小步长。
维护:
pos :当前确定的下标;
sum :当前位置之前已经累计的频率;
t :本轮尝试向右跳的距离。
如果跳到nxt 以后,累计频率仍然小于k k k ,说明第k k k 小一定还在右边,可以接受这次跳转:
1 2 3 4 if (nxt <= n && sum + tree[nxt] < k) { pos = nxt; sum += tree[nxt]; }
这里直接使用tree[nxt] ,而不是重新调用一次prefix(nxt) 。原因是我们始终按照二的幂从大到小试探,并且pos 表示已经完整跳过的前缀;此时tree[nxt]恰好对应紧接在这段前缀后面的一个树状数组区间。接受跳转,相当于把这一整段的频率并入 sum 。所有步长总共只会尝试O ( log n ) O(\log n) O ( log n ) 次,这正是它比“外层二分、内层查询”更快的地方。
循环结束时,pos 是“前缀和仍然小于k k k 的最后一个位置”,因此pos+1 就是第一个前缀和大于等于k k k 的位置。
1 2 3 4 5 6 7 8 9 int kth (int k) { int pos = 0 , sum = 0 , t = 1 ; while ((t << 1 ) <= n) t <<= 1 ; for (; t; t >>= 1 ) { int nxt = pos + t; if (nxt <= n && sum + tree[nxt] < k) { pos = nxt; sum += tree[nxt]; } } return pos + 1 ; }
这里的判断必须是严格小于k k k 。如果写成小于等于k k k ,就会跳过第一个前缀和恰好等于k k k 的位置。
找到第k k k 小的数以后,将其出现次数减一即可完成删除:
1 2 int pos = kth (k);add (pos, -1 );
图片占位 8:频率前缀和中寻找第 k 小的阶梯图
点击展开完整代码 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 #include <bits/stdc++.h> using namespace std;using i32 = int32_t ; using i64 = int64_t ; using i128 = __int128_t ;using u32 = uint32_t ; using u64 = uint64_t ; using u128 = __uint128_t ;constexpr int MAXN = 1000005 ;int n, q, tree[MAXN];int lowbit (int x) { return x & -x; }void add (int x, int k) { for (; x <= n; x += lowbit (x)) tree[x] += k; }int prefix (int x) { int ans = 0 ; for (; x; x -= lowbit (x)) ans += tree[x]; return ans; }int kth (int k) { int pos = 0 , sum = 0 , t = 1 ; while ((t << 1 ) <= n) t <<= 1 ; for (; t; t >>= 1 ) { int nxt = pos + t; if (nxt <= n && sum + tree[nxt] < k) { pos = nxt; sum += tree[nxt]; } } return pos + 1 ; } int32_t main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); cin >> n >> q; for (int i = 1 , x; i <= n; i++) { cin >> x; add (x, 1 ); } while (q--) { int x; cin >> x; if (x > 0 ) add (x, 1 ); else add (kth (-x), -1 ); } if (prefix (n) == 0 ) cout << 0 << '\n' ; else cout << kth (1 ) << '\n' ; return 0 ; }
这道题再次体现了权值树状数组的特点:下标代表数值,树状数组中保存的是出现次数,前缀和代表排名。
如果数值范围很大,也可以先把所有可能出现的数离散化,再维护对应排名的出现次数。不过在线处理时,必须保证需要离散化的值能够提前读到;如果数据真正动态产生,就需要考虑平衡树等其他数据结构。
总结与常见问题
树状数组能维护什么?
最常见的树状数组维护的是加法和,因为区间和可以由两个前缀和相减得到:
s u m ( l , r ) = s u m ( r ) − s u m ( l − 1 ) sum(l,r)=sum(r)-sum(l-1)
s u m ( l , r ) = s u m ( r ) − s u m ( l − 1 )
类似地,异或也有可逆性质,所以树状数组可以维护区间异或。
树状数组也可以在某些限制下维护前缀最大值或最小值,但是修改通常需要满足单调性。例如某个位置只会不断变大时,可以维护前缀最大值;如果一个位置既可能变大又可能变小,原有节点中的最大值可能失效,此时普通树状数组就很难处理。
简单地说:
单点修改、前缀查询以及可以通过两个前缀答案作差得到的区间信息,优先考虑树状数组;
需要任意区间最值、复杂区间修改、维护多种信息时,线段树通常更加合适;
需要维护动态有序集合,而值域较小或可以离散化时,可以考虑权值树状数组;
需要真正动态的键值、前驱后继、分裂合并等操作时,应考虑平衡树。
树状数组的优点是代码短、常数小、占用空间少;缺点也很明显,它能维护的信息不如线段树灵活。没有哪一种数据结构能够包办所有问题,重要的是先看清题目需要的修改和查询是什么。
常见错误
1. 使用下标0 0 0
会因为lowbit(0)=0 陷入死循环。外部下标从0 0 0 开始时,要先转换成树状数组内部的1 1 1 下标。
2. 忘记使用i64
单个a i a_i a i 没有超过int ,不代表区间和、逆序对数量或者i ⋅ d i i\cdot d_i i ⋅ d i 不会超过int 。本文统一把这些可能溢出的量声明为i64 ,不要让正确的思路最后输在数据范围上。
3. 把赋值修改直接当成增加修改
add(x,k) 的含义 是a x ← a x + k a_x\gets a_x+k a x ← a x + k 。
如果题目要求把a x a_x a x 修改为k k k ,需要先计算变化量:
1 2 add (x, k - a[x]);a[x] = k;
4. 区间边界写错
对于从1 1 1 开始的闭区间[ l , r ] [l,r] [ l , r ] :
1 prefix (r) - prefix (l - 1 );
对于从0 0 0 开始的左闭右开区间[ l , r ) [l,r) [ l , r ) ,转换到本文的内部下标后是:
写代码前先确定题目的下标和区间形式,不要把两套公式混在一起。
5. 逆序对把相等元素算进去
如果要求a i > a j a_i>a_j a i > a j ,相等元素不能计入。正序扫描时查询“小于等于当前值”的数量,倒序扫描时查询“严格小于当前值”的数量,二者不要混淆。
6. 第k k k 小的判断条件写成小于等于
我们要寻找第一个前缀和大于等于k k k 的位置,所以倍增时只能跳过前缀和严格小于k k k 的位置:
7. 多组测试忘记清空
如果题目有多组数据,上一组的树状数组不会自己消失。可以使用fill 或memset 清空实际使用的范围,也可以为每组数据重新建立vector 。
复杂度总结
操作
时间复杂度
空间复杂度
单点增加
O ( log n ) O(\log n) O ( log n )
O ( n ) O(n) O ( n )
前缀和查询
O ( log n ) O(\log n) O ( log n )
O ( n ) O(n) O ( n )
区间和查询
O ( log n ) O(\log n) O ( log n )
O ( n ) O(n) O ( n )
差分区间增加
O ( log n ) O(\log n) O ( log n )
O ( n ) O(n) O ( n )
双树状数组区间增加、区间查询
O ( log n ) O(\log n) O ( log n )
O ( n ) O(n) O ( n )
权值树状数组插入、删除
O ( log n ) O(\log n) O ( log n )
O ( n ) O(n) O ( n )
树状数组倍增求第k k k 小
O ( log n ) O(\log n) O ( log n )
O ( n ) O(n) O ( n )