了解树状数组
树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。
基本概念
假设数组a[1..n],那么查询a[1]+...+a[n]的时间是log级别的,而且是一个在线的数据结构,支持随时修改某个元素的值,复杂度也为log级别。
来观察这个图:
令这棵树的结点编号为C1,C2...Cn。令每个结点的值为这棵树的值的总和,那么容易发现:
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
这里有一个有趣的性质:
设节点编号为x,那么这个节点管辖的区间为2^k(其中k为x二进制末尾0的个数)个元素。因为这个区间最后一个元素必然为Ax,
所以很明显:Cn = A(n – 2^k + 1) + ... + An
算这个2^k有一个快捷的办法,定义一个函数如下即可:
function lowbit(x:longint):longint;
begin
exit(x and -x);
end;
当想要查询一个SUM(n)(求a[n]的和),可以依据如下算法即可:
step1:令sum = 0,转第二步;
step2:假如n <= 0,算法结束,返回sum值,否则sum = sum + Cn,转第三步;
step3: 令n = n – lowbit(n),转第二步。
可以看出,这个算法就是将这一个个区间的和全部加起来,为什么是效率是log(n)的呢?以下给出证明:
n = n – lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1,所以查询效率是log(n)的。
那么修改呢,修改一个节点,必须修改其所有祖先,最坏情况下为修改第一个元素,最多有log(n)的祖先。
所以修改算法如下(给某个结点i加上x):
step1: 当i > n时,算法结束,否则转第二步;
step2: Ci = Ci + x, i = i + lowbit(i)转第一步。
i = i +lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。
对于数组求和来说树状数组简直太快了!
很容易知道C8表示A1~A8的和,但是C6却是表示A5~A6的和,为什么会产生这样的区别的呢?或者说发明她的人为什么这样区别对待呢?
答案是,这样会使操作更简单!看到这相信有些人就有些感觉了,为什么复杂度被log了呢?可以看到,C8可以看作A1~A8的左半边和+右半边和,而其左半边和是确定的C4,右半边其实也是同样的规则把A5~A8一分为二……继续下去都是一分为二直到不能分树状数组巧妙地利用了二分,树状数组并不神秘,关键是巧妙!
最后,我凭借两道洛谷上的模版题用代码让大家更深地了解树状数组。
P3374 【模板】树状数组 1
题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某一个数加上x
2.求出某区间每一个数的和
输入输出格式
输入格式:
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x k 含义:将第x个数加上k
操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和
输出格式:
输出包含若干行整数,即为所有操作2的结果。
输入输出样例
输入样例#1:
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出样例#1:
14
16
说明
时空限制:1000ms,128M
数据规模:
对于30%的数据:N<=8,M<=10
对于70%的数据:N<=10000,M<=10000
对于100%的数据:N<=500000,M<=500000
样例说明:
故输出结果14、16
Code:
var
a,tree:array[0..500005] of longint;
i,p,x,k,n,m:longint;
procedure add(k,p:longint);
begin
while k<=n do
begin
inc(tree[k],p);
k:=k+(k) and (-k);
end;
end;
function sum(k:longint):longint;
var ans:longint;
begin
ans:=0;
while k>0 do
begin
ans:=ans+tree[k];
k:=k-(k) and (-k);
end;
exit(ans);
end;
begin
readln(n,m);
for i:=1 to n do
begin
read(a[i]);
add(i,a[i]);
end;
for i:=1 to m do
begin
readln(p,x,k);
if p=1 then add(x,k) else
writeln(sum(k)-sum(x-1));
end;
end.
P3368 【模板】树状数组 2
题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数数加上x
2.求出某一个数的和
输入输出格式
输入格式:
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含2或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k
操作2: 格式:2 x 含义:输出第x个数的值
输出格式:
输出包含若干行整数,即为所有操作2的结果。
输入输出样例
输入样例#1:
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
输出样例#1:
6
10
说明
时空限制:1000ms,128M
数据规模:
对于30%的数据:N<=8,M<=10
对于70%的数据:N<=10000,M<=10000
对于100%的数据:N<=500000,M<=500000
样例说明:
故输出结果为6、10
Code:
var标签:begin,end,log,树状,longint,数组,ans From: https://blog.51cto.com/u_15888102/5878384
a,tree:array[0..500005] of longint;
y,i,p,x,k,n,m:longint;
procedure add(k,p:longint);
begin
while k<=n do
begin
inc(tree[k],p);
k:=k+(k) and (-k);
end;
end;
function sum(k:longint):longint;
var ans:longint;
begin
ans:=0;
while k>0 do
begin
ans:=ans+tree[k];
k:=k-(k) and (-k);
end;
exit(ans);
end;
begin
readln(n,m);
for i:=1 to n do
begin
read(a[i]);
add(i,a[i]-a[i-1]);
end;
for i:=1 to m do
begin
read(p);
if p=1 then
begin
readln(x,y,k);
add(x,k);
add(y+1,-1*k);
end else
begin
readln(k);
writeln(sum(k));
end;
end;
end.