女娲补天之树状数组与线段树
树状数组
主要解决的问题:在$O(logn)$的时间复杂度内完成单点修改和区间查询(前缀和),这里的修改只能让某个位置上的数增加。
图片参考于:小呆呆
主要的操作:
1.lowbit(x)
,$x$的二进制表示末尾有$k$个$0$,返回$2^k$(返回$x$的最后一位$1$)
def lowbit(x):
return x & -x
2.add(x, v)
,在$x$的位置上加上$v$,并且将后面相关联到的位置也加上$v$(从$x$一直向后加lowbit(x)
直到最大值$N$)
def add(x, v):
while x < N:
tr[x] += v
x += lowbit(x)
3.query(x)
,求出从$1$开始到$x$位置的前缀和(从$x$向前减去lowbit(x)
直到$0$)
def query(x):
res = 0
while x > 0:
res += tr[x]
x -= lowbit(x)
return res
这里以query(x)
的递推为例
add(x, v)
则整好相反,是向后递推的,可以看到参考于小呆呆图中绿色标记的原数组第七个元素,如果修改他,那么需要修改哪些位置tr
数组的值。
只要记住query
和add
一个向前减lowbit(x)
,一个向后加lowbit(x)
,二者相反。
注意坐标都要从$1$开始
刷题列表
AcWing 1264. 动态求连续区间和
经典模板题
AcWing 1265. 数星星
本题很神奇,坐标系是正常坐标系和以前算法里用到的坐标系不一样。
坐标是先按$y$的增序给出的(若相同的话按$x$的增序给出),并且本题要求的是左下方所有的星星数量。
对于某一个位置上的星星(坐标为[$x$,$y$]),需要统计的星星坐标应该都小于$x$且小于$y$的,由于星星坐标是按$y$的增序给出的,则当前这个点就是之前所有点中$y$坐标最大的一个,所以只需要找到所有横坐标小于$x$的星星统计即可。
这样就会发现,$y$坐标根本没有用,就将二维转化为了一维。
再仔细思考,相当于把每个星星都投影到了横坐标上,每次统计从$1-x$的前缀和,然后在该横坐标上加$1$即可。‘
可以发现是经典树状数组,单点修改和区间查询。
注意点:
1. 本题是统计不同星级的星星数量,所以每次求和后在对应的星级上加$1$。
2. 由于统计时不包括自身,所以先query
再add
。
3. 本题坐标从$0$开始的,树状数组下标从$1$开始,所以输入时应该x += 1
。
线段树
相比于树状数组,线段树能完成更多复杂的操作,但耗费较大的时间复杂度,同样是维护一个序列,支持单点修改和区间查询操作,二者都是通过递归完成的。
图片参考于:小呆呆
前情提要:
线段树中的每个结点都是一个结构体,在py中用一个类来表示,使用__init__()
初始化,注意是两个_
tr = [0] * (N * 4)
class Node:
def __init__(self, l = 0, r = 0, s = 0):
self.l = l
self.r = r
self.s = s
主要的操作:
1.pushup(u)
:用子节点的信息跟新当前节点的信息
以动态求区间和为例
def push_up(u):
tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s
2.build(u, l, r)
:在一段区间上初始化线段树,u
是根节点,l
是左端点,r
是右端点
以动态求区间和为例
def build(u, l, r):
if l == r:
tr[u] = Node(l, r, w[r])
else:
tr[u] = Node(l, r)
mid = l + r >> 1
build(u << 1, l, mid)
build(u << 1 | 1, mid + 1, r)
tr[u].m = max(tr[u << 1].m, tr[u << 1 | 1].m);
3.query(u, l, r)
:查询某段区间(可能是和,可能是最值),u
是根节点,l
是左端点,r
是右端点
以动态求区间和为例
def query(u, l, r):
if tr[u].l >= l and tr[u].r <= r:
return tr[u].s
mid = (tr[u].l + tr[u].r) >> 1
sum_ = 0
if l <= mid:
sum_ += query(u << 1, l, r)
if r > mid: # r >= mid + 1
sum_ += query(u << 1 | 1, l, r)
return sum_
4.modify(u, x, v)
:修改操作,在结点u
中,x
结点加上或者减去v
以动态求区间和为例
def modify(u, x, v):
if tr[u].l == tr[u].r:
tr[u].s += v
else:
mid = (tr[u].l + tr[u].r) >> 1
if x <= mid:
modify(u << 1, x, v)
else:
modify(u << 1 | 1, x, v)
push_up(u)
修改操作:
递归修改所有影响到的区间
图片参考于:小呆呆
查询操作:
递归找到所有包含的区间进行查询
图片参考于:小呆呆
注意点:
1.线段树的节点要开$4n$
2.线段树的存储是按照堆的存储,父节点为x // 2
,左孩子:$2x$,即x << 1
,左孩子:$2x + 1$,即x << 1 | 1
3.py中结构体(类)的构造与初始化
刷题列表
AcWing 1264. 动态求连续区间和
经典模板题
AcWing 1270. 数列区间最大值
本题不涉及修改操作,只需要将递归求和改为递归求左右子树的最大值即可,这里pushup
操作用一句话就能直接概括
tr[u].m = max(tr[u << 1].m, tr[u << 1 | 1].m)