- 博客(2)
- 收藏
- 关注
RSS订阅原创 Segment-Tree
Segment Tree 线段树(Segment Tree)是个用空间换时间的数据结构,可以用于区间的染色、查询、求和等操作。线段树从名字就可以看出是对于一个一维线段的操作，将原本逐个遍历的操作进行优化。 首先，线段树的构成其实是一种二叉树，树的根节点是一整个区间，而叶子则是区间的最小单位，每个父节点是两个子节点的合并区间，并且两个子节点区间是对半分的。 (1,4) / ...
2020-05-04 02:28:10
245
原创 RMQ
RMQ RMQ(Range Minimum/Maximum Query)是一种求区间内最大值或者最小值的算法，这里用st表来实现。 st表首先就是需要倍增算法，以此来降低时间复杂度，那么就先来了解一下倍增算法。众所周知，任何数都能很容易地表示成二进制，倍增就是以2为底数，因此在二进制中表现良好，只需要进行一次位运算的左移就行了。 我们先建立一个数组s[i][j]s[i][j]s[i][...
2020-03-31 13:51:29
119
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人