树状数组C++——算法设计与分析，附详细解析-创新互联
- 什么是树状数组
- lowbit(x)
- 树状数组的构建
- 如何求区间和呢
- 如何更新一个元素呢
- 二话不说上代码
树状数组可以快速求出数组任意区间的和，具体来说是在
O
(
l
o
g
N
)
O(log\ N)
O(log N)的时间内求出一段区间的和，而更新单个元素的值也需要
O
(
l
o
g
N
)
O(log\ N)
O(log N)时间来维护。首先对树状数组留下一个简单的印象，如下图所示，
A
A
A数组是原数组，
C
C
C数组是树状数组，我们要查询
1
−
6
1-6
1−6区间的和，我们只需要求出
C
6
+
C
4
=
21
C6 + C4 = 21
C6+C4=21的值即可，是不是很快速，那如何实现这样的结构呢？
对于序列
A
A
A，我们设置一个数组
C
C
C与
A
A
A有同样的大小，
C
[
i
]
C[i]
C[i]的求法如下：
C
[
i
]
=
a
[
i
−
2
k
+
1
]
+
⋯
+
a
[
i
]
C[i]=a[i-2^k+1]+\cdots+a[i]
C[i]=a[i−2k+1]+⋯+a[i]
其中，
k
k
k表示
i
i
i 末尾连续
0
0
0 的个数，而
2
k
2^k
2k 就表示
i
i
i 最右边的第一个
1
1
1 和右边连续的
0
0
0 组成的数，就那拿
12
12
12 打比方，
12
=
(
1100
)
2
12=(1100)_2
12=(1100)2，右边连续的零有两个，则
k
=
2
k=2
k=2，
2
k
=
2
2
=
(
100
)
2
2^k=2^2=(100)_2
2k=22=(100)2，就是
i
i
i 保留最右边的
1
1
1 ，其余位全变成
0
0
0，
C
C
C即为树状数组。
那么给定一个 i i i ，如何来求出 k k k 呢？
lowbit(x)l o w b i t ( x ) lowbit(x) lowbit(x)表示的就是保留 x x x 最后一个 1 1 1，其余全变为 0 0 0 的数。
我们假设一个二进制数表示为
x
x
x
x
100
⋯
00
xxxx100\cdots00
xxxx100⋯00，
x
x
x表示
0
0
0 或者
1
1
1，我们将它减一，得到
x
x
x
x
011
⋯
11
xxxx011\cdots11
xxxx011⋯11，注意
x
x
x
x
xxxx
xxxx表示的数没有变，只有最后一位
1
1
1 和右边变化了，我们将这两个数异或
x
x
x
x
100
⋯
00
⊕
x
x
x
x
011
⋯
11
=
0000
111
⋯
11
\ \ \ \ xxxx100\cdots00\\ \oplus xxxx011\cdots11\\ \rule[+3pt]{4.3cm}{0.05em}\\ = 0000\ 111\cdots11
xxxx100⋯00⊕xxxx011⋯11=0000 111⋯11
就得到一个
m
a
s
k
mask
mask，最右边第一个
1
1
1 的左边全
0
0
0，右边全
1
1
1，我们再将这个数与原来的
i
i
i 相与，就可以得到
l
o
w
b
i
t
(
x
)
lowbit(x)
lowbit(x)了。
0000
111
⋯
11
a
n
d
x
x
x
x
100
⋯
00
=
0000
100
⋯
00
\ \ \ \ \ \ \ \ 0000\ 111\cdots11\\ and\ xxxx100\cdots00\\ \rule[+3pt]{4.3cm}{0.05em}\\ \ \ =\ 0 0 0 0 \ 100\cdots00
0000 111⋯11and xxxx100⋯00 = 0000 100⋯00
由此，我们可以推出
l
o
w
b
i
t
(
x
)
lowbit(x)
lowbit(x) 函数的求法：
l
o
w
b
i
t
(
x
)
=
x
&
[
x
⊕
(
x
−
1
)
]
lowbit(x)=x\&[x\oplus (x-1)]
lowbit(x)=x&[x⊕(x−1)]
而
x
⊕
(
x
−
1
)
=
−
x
x\oplus(x-1)=-x
x⊕(x−1)=−x，化简上式可得：
l
o
w
b
i
t
(
x
)
=
x
&
(
−
x
)
lowbit(x)=x\&(-x)
lowbit(x)=x&(−x)
我们可以定义一个宏来求
l
o
w
b
i
t
(
x
)
lowbit(x)
lowbit(x)：
#define lowbit(x) ((x)&(-(x)))回到
C
C
C 数组的定义，我们可以将其改写为
C
[
i
]
=
a
[
i
−
l
o
w
b
i
t
(
i
)
+
1
]
+
⋯
+
a
[
i
]
C[i]=a[i-lowbit(i)+1]+\cdots+a[i]
C[i]=a[i−lowbit(i)+1]+⋯+a[i]
那么，我们可以得出：
树状数组成员变量包含元素个数 n n n 以及树状数组 c [ M A X ] c[MAX] c[MAX]，下面的代码展示了构建树状数组的过程，首先求出 s u m sum sum 数组， s u m [ i ] sum[i] sum[i] 表示 1 − i 1-i 1−i 的和，再根据树状数组的定义求出 C C C，构建树状数组的时间复杂度为 O ( N ) O(N) O(N)。
private:
int n;
int c[MAX];//树状数组
public:
treeArray(int arr[], int num){n = num;
int sum[n + 1]; //sum[i]表示1-i的和
for(int i = 1; i<= n; i++) sum[i] = sum[i-1] + arr[i-1];
for(int i = 1; i<= n; i++) c[i] = sum[i] - sum[i - lowbit(i)]; //按照C的定义，构建树状数组
}我们现在已知了
C
[
i
]
C[i]
C[i]，如何求出
s
u
m
(
k
)
=
A
[
1
]
+
A
[
2
]
+
⋯
+
A
[
k
]
sum(k)=A[1]+A[2]+\cdots+A[k]
sum(k)=A[1]+A[2]+⋯+A[k]呢，打个比方，现在要求
s
u
m
(
7
)
sum(7)
sum(7)，有上述
C
C
C 的定义，可以看出
s
u
m
(
7
)
=
C
7
+
C
6
+
C
4
=
(
A
7
)
+
(
A
5
+
A
6
)
+
(
A
1
+
A
2
+
A
3
+
A
4
)
sum(7)=C7+C6+C4=(A7)+(A5+A6)+(A1+A2+A3+A4)
sum(7)=C7+C6+C4=(A7)+(A5+A6)+(A1+A2+A3+A4)，我们通过一定的规律，可以找出来一个通用公式
s
u
m
(
k
)
=
C
[
n
1
]
+
C
[
n
2
]
+
⋯
+
C
[
n
m
]
n
m
=
k
,
n
i
−
1
=
n
i
−
l
o
w
b
i
t
(
n
i
)
sum(k)=C[n_1]+C[n_2]+\cdots+C[n_m]\\ n_m=k,\quad n_{i-1}=n_i-lowbit(n_i)
sum(k)=C[n1]+C[n2]+⋯+C[nm]nm=k,ni−1=ni−lowbit(ni)
就拿
7
7
7 打比方，
n
n
n来表示
C
C
C的下标，初始值为
7
7
7，直到减到 $0 $为止：
n
=
7
,
s
u
m
(
7
)
+
=
C
[
7
]
,
n
=
7
−
l
o
w
b
i
t
(
7
)
=
6
n
=
6
,
s
u
m
(
7
)
+
=
C
[
6
]
,
n
=
6
−
l
o
w
b
i
t
(
6
)
=
4
n
=
4
,
s
u
m
(
7
)
+
=
C
[
4
]
,
n
=
4
−
l
o
w
b
i
t
(
4
)
=
0
n=7,\quad sum(7)+=C[7],\quad n=7-lowbit(7)=6\\ n=6,\quad sum(7)+=C[6],\quad n=6-lowbit(6)=4\\ n=4,\quad sum(7)+=C[4],\quad n=4-lowbit(4)=0
n=7,sum(7)+=C[7],n=7−lowbit(7)=6n=6,sum(7)+=C[6],n=6−lowbit(6)=4n=4,sum(7)+=C[4],n=4−lowbit(4)=0
具体证明如下，感兴趣的可以看一看
现在回到 C [ i ] C[i] C[i]含义的理解上， C [ i ] = a [ i − l o w b i t ( i ) + 1 ] + ⋯ + a [ i ] C[i]=a[i-lowbit(i)+1]+\cdots+a[i] C[i]=a[i−lowbit(i)+1]+⋯+a[i]，其实 i − l o w b i t ( i ) + 1 i-lowbit(i)+1 i−lowbit(i)+1就是把 i i i 最右边的 1 1 1 去掉，然后再加 1 1 1，从这个下标开始一直加到 i i i，因为 k k k 的二进制最多有 l o g 2 k log_2k log2k 个 1 1 1 ，所以 s u m ( k ) sum(k) sum(k)最多有 l o g 2 k log_2k log2k 项，求区间和的时间复杂度就是 l o g 2 k log_2k log2k。
接下来，如果要求区间 [ a , b ] [a,b] [a,b] 的和，只需要用 s u m ( b ) − s u m ( a − 1 ) sum(b)-sum(a-1) sum(b)−sum(a−1) 即可表示。
下面就是求区间和的两个函数，一个参数的函数表示求 [ 1 − i ] [1-i] [1−i] 的和，两个参数的函数表示求 [ a − b ] [a-b] [a−b] 的和
int getsum(int i){//求A[1-i]的和
int res=0;
while(i >0){res += c[i];
i -= lowbit(i);
}
return res;
}
int getsum(int a, int b){//求A[a-b]的和
return getsum(b) - getsum(a-1);
} 假设我要更新
A
[
2
]
A[2]
A[2] ，那么树状数组需要更新对应的
C
[
2
]
,
C
[
4
]
,
C
[
8
]
,
C
[
16
]
C[2], C[4],C[8],C[16]
C[2],C[4],C[8],C[16] ，我们也可以从中找到规律，如果要更新
A
[
i
]
A[i]
A[i] ，那么下面几项也需要更新：
C
[
n
1
]
,
C
[
n
2
]
,
⋯
,
C
[
n
m
]
n
1
=
i
,
n
i
+
1
=
n
i
+
l
o
w
b
i
t
(
n
i
)
C[n_1],C[n_2],\cdots,C[n_m]\\ n_1=i,\quad n_{i+1}=n_i+lowbit(n_i)
C[n1],C[n2],⋯,C[nm]n1=i,ni+1=ni+lowbit(ni)
同理拿
2
2
2 做为例子，用
n
n
n 表示树状数组
C
C
C 的下标，初始值为
2
2
2，直到
n
n
n 大于数组的大小为止
n
=
2
,
u
p
d
a
t
e
C
[
2
]
,
n
=
2
+
l
o
w
b
i
t
(
2
)
n
=
4
,
u
p
d
a
t
e
C
[
4
]
,
n
=
4
+
l
o
w
b
i
t
(
4
)
n
=
8
,
u
p
d
a
t
e
C
[
8
]
,
n
=
8
+
l
o
w
b
i
t
(
8
)
n
=
16
,
u
p
d
a
t
e
C
[
16
]
,
n
=
16
+
l
o
w
b
i
t
(
16
)
n=2,\quad update\ C[2],\quad n=2+lowbit(2)\\ n=4,\quad update\ C[4],\quad n=4+lowbit(4)\\ n=8,\quad update\ C[8],\quad n=8+lowbit(8)\\ n=16,\quad update\ C[16],\quad n=16+lowbit(16)\\
n=2,update C[2],n=2+lowbit(2)n=4,update C[4],n=4+lowbit(4)n=8,update C[8],n=8+lowbit(8)n=16,update C[16],n=16+lowbit(16)
最后
n
n
n 大于
16
16
16 ，更新结束，同理，更新一个元素总的时间也是
O
(
l
o
g
N
)
O(log N)
O(logN)，但是如果想要更新一个区间的元素就要
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN) 的时间复杂度了，可以考虑另一种结构——线段树会更好，这里不具体介绍。
下面是在位置 i i i 上加 k k k 的代码
void add(int i, int k){//在位置i上加k
while(i<= n){c[i] += k;
i += lowbit(i);
}
}这样以来，我们就学会了树状数组啦，代码是不是很精简，但是功能却很强大哇。
#includeusing namespace std;
#define lowbit(x) ((x)&(-(x)))
#define MAX 10005
class treeArray{private:
int n;
int c[MAX];//树状数组
public:
treeArray(){};
treeArray(int arr[], int num){n = num;
int sum[n + 1]; //sum[i]表示1-i的和
for(int i = 1; i<= n; i++) sum[i] = sum[i-1] + arr[i-1];
for(int i = 1; i<= n; i++) c[i] = sum[i] - sum[i - lowbit(i)]; //按照C的定义，构建树状数组
}
void add(int i, int k){//在位置i上加k
while(i<= n){ c[i] += k;
i += lowbit(i);
}
}
int getsum(int i){//求A[1-i]的和
int res=0;
while(i >0){ res += c[i];
i -= lowbit(i);
}
return res;
}
int getsum(int a, int b){//求A[a-b]的和
return getsum(b) - getsum(a-1);
}
void show(){for(int i = 1; i<= n; i++) cout<< c[i]<< ' ';cout<< endl;}
};
int main(void){int n = 10;
int a[n] = {1,2,3,4,5,6,7,8,9,10}; //定义数组一开始的值
treeArray arr(a, n);
cout<< "4到10的和为："<< arr.getsum(4,10)<< endl; //求数组4-10的和
cout<< "1到4的和为："<< arr.getsum(4)<< endl; //求数组1-4的和
cout<< "将4的值加5"<< endl;
arr.add(4,5); //将4的值加5
cout<< "1到4的和变为："<< arr.getsum(4,10)<< endl;
arr.show();
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享名称：树状数组C++——算法设计与分析，附详细解析-创新互联
URL标题：http://scyanting.com/article/dohjgd.html
