type
status
date
slug
summary
tags
category
icon
password
comment
一维数组定义
二维数组定义
树状数组
- 普通树状数组维护的信息及运算要满足结合律且可差分,如加法(和)、乘法(积)、异或等。
- 树状数组能解决的问题是线段树能解决的问题的子集:树状数组能做的,线段树一定能做;线段树能做的,树状数组不一定可以。然而,树状数组的代码要远比线段树短,时间效率常数也更小,因此仍有学习价值。
- 区间长度:从 a[1] 开始构造数组,其中 c[x] 的数组代表 a[x-k+1] 到 a[x] 的信息,区间长度 k 为
lowbit(x)
- 区间查询:利用 前缀和 & 差分 的方式,以和为例贴出对应代码
- 三条性质:
- 对于,要么有
c[x]
和c[y]
不交,要么有c[x]
包含于c[y]
。 - 在
c[x]
真包含于c[x+lowbit(x)]
- 对于任意,有
c[x]
和c[y]
不交 - 总结: 事实上,树状数组的树形态是
x
向x+lowbit(x)
连边得到的图,其中x+lowbit(x)
是的x
父亲。
- 单点修改:修改c[x]和他的所有祖先
- 建树:转化为n次单点修改
Tricks:
方法一:每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。因此可以倒着考虑贡献,即每次确定完儿子的值后,用自己的值更新自己的直接父亲。
方法二:预处理前缀和,直接计算c数组
- 区间修改:建立了两个差分树状数组,所用函数不变,计算方式发生改变,详情见此博客 贴出我的python代码:
- Author:E1ainay
- URL:https://e1ainay.top/article/alogrithmwiki/BITree
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts