曼哈顿距离和切比雪夫距离
转自 曼哈顿距离与切比雪夫距离及其相互转化 - 自为风月马前卒
本文只讨论二维空间中的曼哈顿距离与切比雪夫距离
曼哈顿距离
定义
设平面空间内存在两点，它们的坐标为
则
即两点横纵坐标差之和
煮个栗子
如图所示，图中两点的曼哈顿距离为
切比雪夫距离
定义
设平面空间内存在两点，它们的坐标为
则
即两点横纵坐标差的最大值
再煮个栗子
两者之间的关系
两者的定义看上去好像毛线关系都没有，但实际上，这两种距离可以相互转化！
我们考虑最简单的情况，在一个二维坐标系中，设原点为
如果用曼哈顿距离表示，则与原点距离为的点会构成一个边长为的正方形
如果用切比雪夫距离表示，则与原点距离为的点会构成一个边长为的正方形
事实上,
将一个点
的坐标变为
后,原坐标系中的曼哈顿距离 $
$ 新坐标系中的切比雪夫距离
将一个点
的坐标变为
后,原坐标系中的切比雪夫距离 新坐标系中的曼哈顿距离
用处
切比雪夫距离在计算的时候需要取，往往不是很好优化，对于一个点，计算其他点到该的距离的复杂度为
而曼哈顿距离只有求和以及取绝对值两种运算，我们把坐标排序后可以去掉绝对值的影响，进而用前缀和优化，可以把复杂度降为