线段树和树状数组例题两道 POJ2991 POJ3468

POJ 2991 Crane (线段树 + 计算几何)

这道题我想了很久. 首先是不明白为什么线段树可以做这样的题目, 然后看到”向量”一词想通了, 但是貌似是个涉及到区间修改的线段树, 我看到网上的题解也是这样, 维护一个区间内所有的向量之和, 修改某个结点的角度就要更新所有影响到的(就是这个结点以后的)结点. 但是看到《挑战》书里面不需要区间修改, 可惜他里面讲得太不详细, 对我这种..来说实在是理解了很久.

书里面的线段树维护以下内容

• 把对应的线段集合中第一条线段转至垂直方向之后, 从第一条线段的七点指向最后一条线段的终点的向量;
• (如果该节点有儿子结点)两个儿子结点对应的部分连接之后, 右儿子需要旋转的角度.

加粗的地方是把区间修改优化成为点修改的重要区别. 这样弄出来的向量可以说是”相对向量”而不是”绝对向量”, 避免了一次修改影响全部的麻烦. 然后旋转部分的公式其实是一个向量逆时针的旋转公式, 本来可以用矩阵相乘来表示. 为了用上这个公式, 需要知道两根相邻的线段之间当前的角度, 然后用目标角度减去当前角度, 就得出需要逆时针旋转的角度. 把这个角度带入公式计算得出新的相对向量值.

而且判断叶子结点的方式不是(l == r)而是(r – l == 1), 因为一个叶子需要两个线段组成.

POJ 3468 A Simple Problem with Integers (区间操作树状数组)

这道题本来是一个区间修改的线段树裸体. 我以前做过, 不过看<挑战>里面写的区间线段树的风格和杭电某神的风格不太一样, 和刘汝佳的风格也是不一样, 看看也是好的.

然后<挑战>给出了区间修改的树状数组的写法, 因为BIT是一个计算前缀和的工具, 所以用一些小技巧是可以用两个前缀和的数据来生成一个支持区间修改的数据结构.

这种小技巧第一我是在普通的用数组记录前缀和的区间操作(不修改)中看到. 因为树状数组支持高速修改前缀和中的某个点的数据, 所以把那个技巧运用过来就变成了支持区间修改的前缀和数据结构, 真是好玩.