Empirical-Cumulative-Distr-Fn
計算多元經驗分佈函數（ECDF）的算法？
一維ECDF相當容易計算。然而，當涉及到兩個維度及更高維度時，在線資源變得稀少且難以獲得。任何人都可以建議、定義和/或提出用於計算多元 ECDF 的有效算法（不是現成的實現）嗎？
在進一步研究中，以下論文給出了 kD ECDF 問題的有效算法：
本特利，JL（1980 年）。多維分而治之。ACM 通訊，23(4), 214-229。
引入的主要數據結構稱為範圍樹，有點類似於kd 樹，但使用空間換時間的權衡來實現更快的範圍查詢。上述論文的作者 Jon Bentley（以 Programming Pearls 聞名）是這兩種數據結構的發明者。
兩者都是遞歸劃分一組的二叉樹通過沿中值處的坐標軸分割來獲得維度點。在 kd 樹中，節點的子樹沿-th 維，其中循環通過沿著樹向下移動。在範圍樹中，子樹總是沿第一維拆分，但每個節點都增加了一個在剩余維度上定義的維度範圍樹。
在撰寫本文時，上面鏈接的“範圍樹”的 Wikipedia 頁面指向 CS 講座（Utrecht U.）比較了大約 2012 年的這兩種樹類型。這表明這些數據結構本質上仍然是“最先進的” ”。提到了範圍樹的改進“分數級聯”變體，但對於所有點 ECDF 問題，這僅允許通過範圍樹的重複查詢來實現 Bentley 算法的性能。