四叉樹 - 多級分段樹

Question

我最近遇到一個叫做分段樹的新數據結構，然後讀到它也可以擴展到兩個維度，但是我找不到一個很好的資源來閱讀它的實現細節和其他東西。 我想從在編程競賽中使用它的角度來了解它，而不是在圖形領域。使用它可以解決的一些問題也是有用的。 有人可以請我指出一個很好的來源來閱讀它？ 謝謝

Answer 1

我不知道你是否會找到更多的來源。我認爲讓人們瞭解k維分割樹是如何工作的。在你的位置上，我會嘗試解決一個可以用它來完成的問題。簡單的例子（我知道這個查詢可以通過一些預處理在O（1）中完成）：矩形範圍和。即：給定一個填充數字的矩陣，回答詢問子矩陣之和的查詢。 在這裏，您可以使用一棵半樹來分割高度，然後在每個節點上爲基於寬度的總和創建一個附加分割樹。 如果你能做到這一點，那麼你知道一切有關2-dim的知識。分段樹。 接下來的挑戰是允許更新單個元素 - 這會變得更加困難，因爲您必須使用一些「藝術」來正確傳播更改（考慮段樹內的某種類型的緩存）。 :)

Answer 2

有一篇關於一維分段樹及其代碼示例的二維概括的好文章。但它在俄羅斯，所以你可能不得不把唯一的代碼示例=）

http://e-maxx.ru/algo/segment_tree

Answer 3

延伸段樹木多個維度，尤其是在程序設計大賽可以變成是非常困難和耗費時間。

如果您需要多個維度，您應該首先了解二進制索引樹，然後嘗試將它們擴展到多個維度。

二元索引樹是一種數據結構，在某些情況下，它比段樹更好地執行，而在另一些情況下，它僅僅是不合適的。

使用分段樹時，對多維的擴展是微不足道的。

在這裏可以找到an article about them。

在這裏您可以找到a problem that can help you test your implementation。