树状数组(高级数据结构)-蓝桥杯

一、简介

• 树状数组 (Binary Indexed Tree,BIT)，利用数的二进制特征进行检索的一种树状结构。

• 一种真正的高级数据结构： 二分思想、二叉树、位运算、前缀和。

• 高效!

• 代码极其简洁!

二、基本应用

• 数列a1,a2,....,an，操作：

• 单点修改：修改元素add(k,x)： 把ak加上x。

• 求和：

sum (x) = a1 + ... + ax

区间和ai + ... + aj = sum(j) - sum(i-1)

三、不修改、只查询

• 数列aj, a2,..., an，求区间和： ai+ ...+aj

• 数列是静态的，用前缀和计算区间和，特别高效。

• 前缀和：sum[i]=a1+...+ ai

• 区间和： ai+...+aj = sum[j]-sum[i-1]

• 查询一次区间和，O(1)

• 代码

• 如果数列是动态的

• 修改元素add(k,x)：把a加上x。

复杂度O(1)

• 求区间和：sum(j) - sum(i-1)

复杂度：O(n)--------->效率低

四、动态修改、求区间和： 用树状数组

• 数列是动态的

• 修改元素add(k,x)：把ak加上x。

• 求区间和：sum(j) - sum(i-1)

• 复杂度都是： O(logn)

• 代码

五、从二叉树到树状数组

六、神奇的lowbit(x)操作

• 语法：lowbit(x)=x &-x

• 功能：找到x的二进制数的最后一个1

七、tree[ ]数组

• 从lowbit(x)推出tree[ ]数组，所有的计算都基于tree[ ]，令m =lowbit(x)。

• 定义tree[x]：把ax和它前面共m个数相加。

• 例： lowbit(6)=2，有tree[6] = a5+a6。

• 横线中的黑色表示tree[x]，等于横线上元素相加的和。

八、基于tree[ ]的计算

• 求和sum=a1 +...+ax

利用tree[ ]数组求sum，例如：

sum[8] = tree[8]

sum[7] = tree[7] + tree[6] + tree[4]

sum[9] = tree[9] + tree[8]

• 以上关系是如何得到的?借助lowbit(x)。

九、sum[ ]的计算

• 例： sum[7] = tree[7] + tree[6] + tree[4]

(1)从7开始，加上tree[7]；

(2) 7 -lowbit(7)= 6，加上tree[6]；

(3) 6 - lowbit(6) = 4，加上tree[4]；

(4) 4-lowbit(4)= 0，结束。

• sum()的复杂度?--------->O(logn)------非常好!

十、sum[ ]的更新

• 更改ax，和它相关的tree都会变化。

• 例如改变a3，那么tree[3]、tree[4]、tree[8]...都会改变。

• 影响哪些tree[ ]? 仍然利用lowbit(x)

(1) 更改tree[3]；

(2) 3 +lowbit(3)= 4，更改tree[4]；

(3) 4 +lowbit(4)=8，更改tree[8]；

(4)直到最后的tree[n]。

• 复杂度?--------->O(logn)------非常好!