@zqbinggong
2018-03-13T10:14:02.000000Z
字数 2157
阅读 1056
顺序统计树
区间树
算法导论
对子树规模的维护
对于rotate操作,以左旋为例,只需增加y.size = x.size; x.size == x.left.size + x.right.size + 1
os-select(x,i)
r = x.left.size + 1
if i == r
return x
else if i < r
return os-select(x.left,i)
else return os-select(x.right,i)
os-rank(T,x)
r = x.left.size + 1
y = x
while y != T.root
if y = y.p.right
r = r + y.p.left.size + 1
y = y.p
return r
interval-search(T,i)
x = T.root
while x !+ T.root and i does not overlap x.int
if x.left != T.nil and i.low < x.left.max
x = x.left
else x = x.right
return x
如何在时间内计算大小为n的数组中的逆序对
思路:使用顺序统计树,过的每个元素的秩。根据关系式可得总的逆序对。
式中j表示的是数组下标,表示位于 之后的比j小的数个数
当然可以
--
mim-insert-search(T,i)
return mim-interval-search-from(T,T.root,i)
mim-interval-search-from(T,x,i)
if x.left != T.nil and i.low < x.left.max
y = mim-interval-search-from(T,x.left,i)#尽量往左下方找
if y != T.nil
return y
else if i overlaps x.int
returnx
else return mim-interval-search-from(T,x.right,i)
思路: 增加属性x.min-gap,x.min-val,x.max-val,分别是以x为结点的子树中的最小差值,最小关键字,最大关键字
关系式:
思路:
1. 选取所有矩形的x坐标,将其排序,并记录该坐标对应的矩形以及它是该矩形的左变坐标还是右边坐标
2. 从小到大便遍历这些x坐标,当遇到一个左边坐标时,检查它的y左边区间是否与区间树中的区间重叠,再将其插入区间树;
3. 当遇到一个右边坐标区间,删除对应的y区间
4. 一直遍历,知道遇到2中检查情况为真时,返回true,否则返回false
思路:
1. 总存在一个是端点的最大重叠点
2. 这里。把区间的端点作为单独的元素并创建一个二叉搜索树,并且给做端点增加属性p=1,右端点p=-1,注意在插入元素时,如果有端点值相等,则先插入左边端点
3. 反向,最大重叠点满足一个特殊的关系:对于已经排好序的端点序列来说,让他们的p按顺序相加,直到和sum最大,此时最后加入的端点就是最大重叠点
4. 根据3中的关系,给每个结点再增加属性v,m,i,分别表示以x为结点的子树中所有元素按序相加(3中所述)的sum,最大sum,最大sum对应的i
5. 关系式: ;
思路:
1. m为常数,
首先为没一个书指定一个order,再根据order按规则取数即可
m不是常数,
josephus(n,m)
initialize T to be empty
for j = 1 to n
create a noede x with x.key = j
os-insert(T,x)
k=n,j=m
while k > 2
x = os-select(T.root,j)
pritn x.key
os-delete(T.root,j)
k = k - 1
j = ((j+m-2)mod k) + 1
print os-select(T.root,1).key