算法或设计模式的有效，随机访问累积和

Question

我正在修补地理空间数据，特别是轨道(由纬度和经度定义的地理位置的有序序列)。

大多数应用程序要求我计算从起点到给定点的累积距离。因此，如果我调用track.totalDistance[20]，例如，我将得到从起点到索引为20的点的距离。

目前，我通过预先计算每个连续距离，增加一个变量，并将值分配给每个点来解决这个问题，这不是一个好的行为，因为我计划编辑轨道(添加，删除和更新点)，并且"总距离"实际上不是轨道点的固有属性，而是在其包含轨道的上下文中的轨道点。

另一方面，如果我推迟getter函数的求值，比如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