Algorighm或設計模式的高效隨機訪問累積和

Question

我正在修補地理空間數據，特別是軌道（由經度和緯度定義的有序地理位置序列）。

大多數應用程序要求我計算從開始到給定點的累積距離。因此，例如，如果我打電話給track.totalDistance[20]，例如，我將獲得從開始點到索引點20的距離。

目前我正在通過預先計算每個連續距離，增加一個變量並將值分配給每個點，這是不是一個好的行爲，因爲我打算編輯軌道（添加，刪除和更新點），並且「總距離」實際上不是一個軌跡點的內在屬性，而是它的上下文中的軌跡點的內在屬性跟蹤。另一方面，如果我推遲對吸氣劑功能的評估，比如說getTotalDistance(track, 20)，那麼會有很多重複的和實際上不必要的計算。

所以問題是：我怎樣才能以一種方式實現一個類，以便我可以在任何時候更有效地獲得任意索引的累積和，同時避免不必要的計算（完全初始化或重複）？

我使用的語言大多是Python，Javascript和C＃，但我想答案可能是可以用任何語言實現的一般結構。

Answer 1

你可以使用一個自我平衡的樹，像這樣的節點：

public class Node 
{ 
    public Node(Node leftChild, Node rightChild) 
    { 
     FirstPoint = leftChild.FirstPoint; 
     LastPoint = rightChild.LastPoint; 
     LeafCount = leftChild.LeafCount + rightChild.LeafCount; 
     BetweenDistance = leftChild.LastPoint.DistanceTo(rightChild.FirstPoint); 
     TotalDistanceSum = leftChild.TotalDistanceSum 
      + BetweenDistance 
      + rightChild.TotalDistanceSum; 
     IsLeaf = false; 
     LeftChild = leftChild; 
     RightChild = rightChild; 
    } 

    public Node(Point p) 
    { 
     FirstPoint = p; 
     LastPoint = p; 
     LeafCount = 1; 
     IsLeaf = true; 
    } 

    /// The point of the leftmost decendant. 
    public Point FirstPoint { get; set; } 
    /// The point of the rightmost decendant. 
    public Point LastPoint { get; set; } 

    /// Number of leaves. 
    public int LeafCount { get; set; } 
    /// The distance from FirstPoint to LastPoint along the path. 
    public double TotalDistanceSum { get; set; } 
    /// The distance between LeftChild and RightChild. 
    public double BetweenDistance { get; set; } 

    /// Flag wheter this is a node or a leaf. 
    public bool IsLeaf { get; set; } 
    /// Left child of this non-leaf node. 
    public Node LeftChild { get; set; } 
    /// Right child of this non-leaf node. 
    public Node RightChild { get; set; } 

    /// Calculates the distance between two point along the path. 'start' is inclusive. 'end' is exclusive. 
    public double DistanceSum(int start, int end) 
    { 
     if (IsLeaf || start >= LeafCount || end < 0 || start >= end) 
      return 0; 

     if (end > LeafCount) end = LeafCount; 
     if (start < 0) start = 0; 

     if (start == 0 && end == LeafCount) 
      return TotalDistanceSum; 

     int n = LeftChild.LeafCount; 
     return LeftChild.DistanceSum(start, end) 
      + BetweenDistance 
      + RightChild.DistanceSum(start - n, end - n); 
    } 
} 

public class Point 
{ 
    public double X { get; private set; } 
    public double Y { get; private set; } 

    public Point(double x, double y) 
    { 
     X = x; 
     Y = y; 
    } 

    public double DistanceTo(Point other) 
    { 
     double dx = other.X - X; 
     double dy = other.Y - Y; 
     return Math.Sqrt(dx*dx + dy*dy); 
    } 
} 

例子：

var tree = new Node(
    new Node(
     new Node(new Point(0,0)), 
     new Node(new Point(1,0)) 
    ), 
    new Node(
     new Node(new Point(1,1)), 
     new Node(new Point(0,1)) 
    ) 
); 
double dist = tree.DistanceSum(0,4); // returns 3.0