- 1软件测试工程师--面试题_uftuif
- 2用Python 开发植物大战僵尸游戏_python中怎么做植物大战僵尸
- 3在MAC系统中使用mysql，出现mysql: command not found的情况_command not found: mysql
- 4【点云论文速读】6D位姿估计
- 5共识问题：区块链如何确认记账权？_区块链候选记账权
- 6python sys os time random模块_pycharm安装sys os time 模块
- 7Git重修系列 ------ Git的使用和常用命令总结
- 8uniapp tabBar角标问题_uniapp再tabbar上添加动态的数字角标
- 915个超实用Python文本处理案例分享，快点码住！_python关于文件经典例子
- 10auditd 用户审计详解
树状数组的时间复杂度证明_构建树状数组的时间复杂度
赞
踩
#build
根据建立的方法可以容易的写出递推式：
T
(
n
)
=
T
(
n
−
1
)
+
h
e
i
g
h
t
(
n
)
T(n) = T(n-1) + height(n)
T(n)=T(n−1)+height(n)
height为该节点的高度，即
l
o
g
2
(
l
o
w
b
i
t
(
n
)
)
log_2(lowbit(n))
log2(lowbit(n));
可以对每层分开记贡献即可以得到：
T
(
n
)
=
∑
i
l
o
g
2
n
n
2
i
T(n) = \sum_i^{log_2n}\frac{n}{2^i}
T(n)=i∑log2n2in
所以:
1
<
=
T
(
n
)
n
<
=
2
1 <= \frac{T(n)}{n} <= 2
1<=nT(n)<=2
恒成立
所以树状数组建树时间复杂度为O(n)
#query/modify
不难想到对于任意数字，每一二进制位出现1的概率为
1
2
\frac{1}{2}
21,所以对于1-n的数字，期望出现
1
2
n
∗
l
o
g
2
n
\frac{1}{2}n*log_2n
21n∗log2n个1
所以树状数组的查询/修改时间复杂度为
O
(
n
∗
l
n
n
)
O(n*lnn)
O(n∗lnn)
