在OI赛事中,数据结构是非常重要的一个内容,更是有人说过,算法+数据结构=程序:
A l g o r i t h m + D a t a Algorithm+Data Algorithm+Data S t r u c t u r e = P r o g r a m m i n g Structure=Programming Structure=Programming
接下来,我们就来介绍一些经典重要的数据结构。
首先是树状数组。
实际上,数据结构就相当于一种算法,是在某种结构上实现某算法。
树状数组是一个查询和修改复杂度都为 O ( l o g 2 n ) O(log_2 n) O(log2n) 的数据结构,运用树状数组可以实现很多算法问题,
比如单点修改,区间求和,求逆序对等等。
比如区间求和,若 n n n 为数列长度, m m m 为查询次数,那么普通查询总和的最坏时间复杂度为 O ( n m ) O(nm) O(nm),假设 n n n 和 m m m < = <= <= 1 0 5 10^{5} 105,时间复杂度就接受不了了,所以很多数据结构比如树状数组,RMQ问题的ST,线段树以及倍增(不太算是数据结构,偏向于 A l g o r i t h m Algorithm Algorithm)之类的,多数情况下都是为了压缩时间复杂度,尽量达到 O ( 1 0 5 − 1 0 7 ) O(10^5-10^7) O(105−107)左右,使程序能在 1 s 1s 1s 的时间内求解。
而树状数组的代码效率远远高于线段树,树状数组代码比较少,但线段树代码量特别大
基本思想:
根据任意正整数关于 2 2 2 的不重复次幂的唯一分解性质,若一个正整数 x x x 的二进制表示为 1010 1 ( 2 ) 10101_{(2)} 10101(2),其中 1 1 1 的位是 0 , 2 , 4 0,2,4 0,2,4 ,则 x x x 可以被“二进制分解”成 2 4 + 2 2 + 2 0 2^{4}+2^{2}+2^{0} 24+22+20,进一步,区间 [ 1 , x ] [1,x] [1,x],可以分成 l o g 2 x log_2 x log2x个小区间:
- 长度为 2 4 2^4 24 的小区间 [ 1 , 2 4 ] [1,2^{4}] [1,24]
- 长度为 2 2 2^2 22 的小区间 [ 2 4 + 1 , 2 4 + 2 2 ] [2^{4}+1,2^{4}+2^{2}] [24+1,24+22]
- 长度为 1 1 1 的小区间 [ 2 4 + 2 2 + 1 , 2 4 + 2 2 + 1 ] [2^{4}+2^{2}+1,2^{4}+2^{2}+1] [24+22+1,24+22+1]
树状数组就是基于上述思想的数据结构,基本作用是维护序列的前缀和。
对于区间 [ 1 , x ] [1,x] [1,x],树状数组将其分为 l o g 2 x log_2 x log2x 个小区间, l o g 2 x log_2 x log2x 个子区间的累加和就是 [ 1 , x ] [1,x] [1,x] 的区间和。
基本算法:
由上文可知,这些子区间的共同特点是,若区间结尾为 R R R,则区间长度就等于 R R R 的“二进制分解”下最小的 2 2 2 的次幂,我们设为 l o w b i t ( R ) lowbit(R) lowbit(R)
l o w b i t lowbit lowbit的计算很简单, l o w b i t ( n ) = n lowbit(n)=n lowbit(n)=n & ( − n ) (-n) (−n),表示 n n n在二进制表示下最低位的 1 1 1 以及后面的 0 0 0 构成的数。如 l o w b i t ( 10110 0 ( 2 ) ) = 10 0 ( 2 ) = 4 ( 10 ) lowbit(101100_{(2)})=100_{(2)}=4_{(10)} lowbit(101100(2))=100(2)=4(10)
我们就可以写一个子程序函数 l o w b i t lowbit lowbit 来实现:
int lowbit(int x) {return x&(-x);
}
对于序列 A A A,我们建立一个数组 C C C,其中 C C C [ x ] [x] [x] 保存序列 A A A 的区间 [ x − l o w b i t ( x ) + 1 , x ] [x-lowbit(x)+1,x] [x−lowbit(x)+1,x] 中所有数之和。
我们构造上图所示的结构,满足以下性质:
- C C C [ x ] [x] [x] 等于以 x x x 为根的子树中所有叶节点的和。
- C C C [ x ] [x] [x] 的叶节点个数等于 l o w b i t ( x ) lowbit(x) lowbit(x)。
- C C C [ x ] [x] [x] 的父亲节点是 C C C [ x + l o w b i t ( x ) ] [x+lowbit(x)] [x+lowbit(x)]。
- 深度为 l o g 2 N log_2 N log2N
如图我们可以知道:
C C C [ 1 ] [1] [1] = A [ 1 ] A[1] A[1]
C C C [ 2 ] [2] [2] = A [ 1 ] A[1] A[1] + A [ 2 ] A[2] A[2]
C C C [ 3 ] [3] [3] = A [ 3 ] A[3] A[3]
C C C [ 4 ] [4] [4] = A [ 1 ] A[1] A[1] + A [ 2 ] A[2] A[2] + A [ 3 ] A[3] A[3] + A [ 4 ] A[4] A[4]
C C C [ 5 ] [5] [5] = A [ 5 ] A[5] A[5]
C C C [ 6 ] [6] [6] = A [ 5 ] A[5] A[5] + A [ 6 ] A[6] A[6]
C C C [ 7 ] [7] [7] = A [ 7 ] A[7] A[7]
C C C [ 8 ] [8] [8] = A [ 1 ] A[1] A[1] + A [ 2 ] A[2] A[2] + A [ 3 ] A[3] A[3] + A [ 4 ] A[4] A[4] + A [ 5 ] A[5] A[5] + A [ 6 ] A[6] A[6] + A [ 7 ] A[7] A[7] + A [ 8 ] A[8] A[8]
对某个单点的元素进行修改
就先讲加法操作
树状数组支持单点加法操作,根据树状数组的结构特性,节点 x x x 及其所有祖先节点的 C C C 值会受到操作的影响,而任意一个节点的祖先最多有 l o g 2 N log_2 N log2N 个,逐一对 C C C 值进行加法就行了。时间复杂度为 O ( l o g 2 N ) O(log_2 N) O(log2N)。
Code:
void update(int x,int y) { //将第x个数加上yfor(;x<=N;x+=lowbit(x)) c[x]+=y;
}
而要将某个单点的元素直接改成 y y y,则需要如下代码:
void update(int x,int y) { //将第x个数改成yfor(int i=x;i<=N;i+=lowbit(i)) c[i]+=(y-a[i]);
}
查询前缀和
树状数组支持查询前缀和,较为简单,时间复杂度为 O ( l o w 2 N ) O(low_2 N) O(low2N) 直接给出
Code:
long long ask_sum(int x) { //函数名各式各样//查询前x个数的和long long ans=0;for(;x;x-=lowbit(x)) ans+=c[x];return ans;
}
接下来,我们用一道简单的例题来详细讲解一下树状数组
例题
单点修改区间查询
[题目描述]
已知一个数列,你需要进行下面两种操作:
- 将某个数加上 x x x;
- 求出某区间所有数的和。
输入格式
第一行两个整数 n , m n,m n,m, 分别表示该数列长度和操作个数
第二行 n n n 个整数,表示原数列。
接下来 m m m 行每行包含 3 3 3 个整数,表示一个操作,具体如下:
第一个整数为opt,有下列两种输入情况
1 x k: 将第 x x x 个数加上 k k k
2 x y: 询问区间 [ x , y ] [x,y] [x,y] 所有数的和
输出格式
对于每个opt=2,输出一行一个整数,表示相应的结果。
数据范围
1 1 1 < = <= <= n , m n,m n,m < = <= <= 1 0 6 , 10^{6}, 106, 0 0 0 < = <= <= ∣ a [ i ] ∣ , x |a[i]|,x ∣a[i]∣,x < = <= <= 1 0 6 10^{6} 106
树状数组模板题,只是操作2不是求前缀和,是某个区间 [ x , y ] [x,y] [x,y] 的和,我们用 a s k _ s u m ( y ) − a s k _ s u m ( x − 1 ) ask \_ sum(y)-ask \_ sum(x-1) ask_sum(y)−ask_sum(x−1) 就可以了。
Code:
#include<bits/stdc++.h>
int n,q,opt;
long long a[10000001],c[10000001];
long long x,y;
inline int lowbit(int x) { //lowbit函数return x&(-x);
}
inline void update(int x,long long k) {for(;x<=n;x+=lowbit(x)) c[x]+=k;
}
inline long long ask_sum(int x) {long long ans=0;for(;x;x-=lowbit(x)) ans+=c[x];return ans;
}
int main() {std::cin>>n>>q;for(int i=1;i<=n;i++) scanf("%lld",a+i),update(i,a[i]); //输入while(q--) {scanf("%d %lld %lld",&opt,&x,&y);switch(opt) {case 1: //当opt=1时将某个单点元素加上yupdate(x,y); break;case 2: //当等于2时查询某个区间所有数的和printf("%lld\n",ask_sum((int)y)-ask_sum((int)x-1)); break;}}
}
树状数组的模板是非常重要的,虽然说理解也很重要,但在背诵的同时理解的效率会更高。
这篇介绍树状数组的文章到此结束了,如有bug请指出,不胜感激!
下一篇数据结构的文章介绍线段树