线段树与树状数组
树状数组与线段树都是非常强大的数据结构,在很多算法题中得到应用,因此需要进行掌握。
题目特征
- 单点更新
- 区间查询
一般来讲,需要求上述问题的解时,常常会用到线段树或树状数组
需要注意的是,区间求和问题还可以用前缀和来进行求解,但是前缀和的局限之处在于其前缀和数组在初始化之后就固定了,每当更新其中某一个点的信息时,需要重复更新整个前缀和数组,有过多的冗余计算,因此遇到动态更新区间内的点时,无法使用前缀和来进行求解。
树状数组
树状数组使用一维数组来表示,结构与操作十分简单,但是其原理证明十分复杂
树状数组在结构上将数据分为若干层: 数组下标从 1 开始,其二进制表示中有多少个 0 ,就视其为第几层
这种结构划分使得树状数组从原本普通的一维线性数组变成了一种具有树状层次的数据结构
而在此划分的基础上,所有第 0 层位置存储的是其原来的数据,所有大于 0 层的位置存放的数据是在此位置之前且尚未被统计过的数据之和
线段树
操作:
- push up: 利用子结点的信息来更新当前节点的信息
- build: 在一段区间上初始化线段树
- modify: 单点修改操作
- query: 区间查询操作
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.